Undecidability

PDF of Prof. Santosh’s handwritten notes are here.

What is computation?

We think of computation as being by a device such as calculator, phone, laptop, etc…something that actually computes something. However, we could also view computation from a different perspective. In fact, we can look at the universe as a giant computational device, where the laws of nature takes some input (the current state of the universe) and produce an output (the universe at a future state). For a more concrete example, we could consider the weather on Earth to be a computational device, which produces the current temperature in a specific location.

Nearly anything could be formulated as a computational device. To help in our study of what is computable, we will formulate a couple simple, well-defined computational devices: a finite state machine and a Turing machine.

Finite state machine (automaton)

  • Q, finite set of possible states
  • \Gamma, alphabet, which we assume includes a “blank” symbol
  • \delta: Q \times \Gamma \rightarrow Q \times \Gamma, a transition function
  • q_{accept}, accept state
  • q_{reject}, reject state
  • q_0, start state

The above set of rules can develop systems that will recognize certain languages. For example, we could design a finite state machine that determines whether a string is in the language L=\{0^*11^*00\}.

Question: What is the set of languages recognized by finite state machines?

Is it all languages? How do we rule out that language is not computable by a finite state machine? If something is not computable by a finite state machine, is it not computable by any device?

More concretely, can we construct a finite state machine to recognize the language L = \{0^n1^n, n \in \mathbb{N}\}? We can easily write a program on a modern computer to recognize this language: just count the number of zeros, then count the number of ones, and check if they’re equal. But for a finite state machine, we don’t have the luxury of a counter. In fact, it turns out that no finite state machine can recognize this language.

Turing Machine

We now consider a more powerful model of computation, known as a Turing Machine (TM), which is essentially a finite state machine where we additionally get access to a read/write tape where we can store information.

  • Q, set of states
  • \Sigma, input alphabet (does not include a blank character)
  • \Gamma, tape alphabet (includes a blank character and all of \Sigma)
  • read/write tape, which we assume to have infinite length
  • \delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{ L,R \}, transition function.

It is clear that a TM can compute things that finite state machines cannot by considering our previous example: L = \{0^n1^n, n \in \mathbb{N}\}. But what all can a TM compute?

Church-Turing thesis: Anything computable can be computed by a TM.

Suppose a TM M accepts a set of strings, i.e., a language L_M. Now, we know that

  • the set of languages is uncountable
  • the set of TM’s is countable
    • \langle M\rangle: description of a TM, Q,\delta, which can be encoded as a single string. Recall the set of finite strings over a finite alphabet is countable.

Therefore, not all languages can be recognized by a TM.

Question: What is a language that cannot be decided by a TM?

Consider L_A = \{(\langle M\rangle,w):\langle M\rangle \text{ is a valid TM}, M \text{ accepts } w\}.

Theorem 1. There does not exist a TM A such that

  • A accepts x if x \in L_A
  • A does not accept x if x \not \in L_A

Proof: Suppose, for a contradiction, that such an A exists. Define a TM D on input \langle M\rangle as follows:

  • Run A on (\langle M\rangle,\langle M\rangle).
  • D accepts if A rejects.
  • D rejects if A accepts.

Now, does D accept \langle D\rangle? From the definition of D,

  • D accepts \langle D\rangle if D rejects \langle D\rangle
  • D rejects \langle D\rangle if D accepts \langle D\rangle

Therefore, we have a contradiction and must conclude that TM A cannot possibly exist.

Theorem 2. Define

L_{HALT} = \{(\langle M\rangle,w) | M \text{ is a TM}, M \text{ halts on } w\}. The language L_{HALT} is undecidable.

Proof: Suppose there exists a TM H that decides L_{HALT}. Then, we can decide L_{ACCEPT} with the following TM:

  • Run H on (\langle M\rangle,w).
  • If H says M does not halt, then reject.
  • Else run M on w; accept if M accepts and reject if M rejects.

by simply running the TM M on the inputs which halt. This contradicts Theorem 1.

We also have the following similar theorems about undecidability.

Theorem 3. Determining whether two TM’s M_1, M_2 accept the same language L is undecidable.

Theorem 4. Determining if a TM M accepts any string is undecidable.

Proof: Suppose there exists a TM B that decides the language L_\emptyset = \{\langle M\rangle:L_M = \emptyset\}.

Define a TM M_w on input x:

  • if x \neq w, reject
  • if x = w, then run M on w

Now define a TM A on input (\langle M\rangle,w):

  • Run B on the TM \langle M_w\rangle
  • Reject if B accepts, and accept if B rejects

Then,

  • B accepts if L_{M_w}=\emptyset, which implies that M does not accept w
  • B rejects if L_{M_w}\neq \emptyset and thus M_w accepts w

Thus we have decided if M accepts w, contradicting Theorem 1.

Advertisements