# 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.