Undecidability

Not all problems can be solved by algorithms. Some are undecidable — no Turing machine exists that always halts and correctly answers the question.

---

Diagonalization

Cantor's diagonalization showed: The set of all languages over $\{0,1\}$ is uncountable, but the set of all Turing machines is countable.

Countability of TMs

Every TM can be encoded as a finite binary string $⟨M⟩$. The set of all finite strings over $\{0,1\}$ is countable (lexicographic order). Therefore, TMs are countable — but the powerset of $\{0,1{\}}^{\ast }$ (all languages) is uncountable.

Conclusion: There exist languages that are not RE (most languages, in fact).

---

$A_{TM}$ is Undecidable

$$A_{TM}=\{⟨M,w⟩\mid M\text{ is a TM and }M\text{ accepts }w\}$$

Theorem: $A_{TM}$ is RE but not recursive (not decidable).

Proof by diagonalization: Suppose there is a decider $H$ for $A_{TM}$:

$$H(⟨M,w⟩)=\{\begin{array}{ll}\text{accept}& \text{if }M\text{ accepts }w\\ \text{reject}& \text{if }M\text{ does not accept }w\end{array}$$

Construct the "diagonal" TM $D$:

D(<M>):
    Run H(<M, <M>>)
    If H accepts, reject
    If H rejects, accept

Now, what does $D$ do on input $⟨D⟩$?

• If $D$ accepts $⟨D⟩$, then $H(⟨D,⟨D⟩⟩)$ accepts, meaning $D$ rejects $⟨D⟩$ — contradiction
• If $D$ rejects $⟨D⟩$, then $H$ rejects, meaning $D$ accepts $⟨D⟩$ — contradiction

Therefore, $H$ cannot exist. $A_{TM}$ is undecidable.

---

The Halting Problem

$$HAL{T}_{TM}=\{⟨M,w⟩\mid M\text{ halts on input }w\}$$

Theorem: $HAL{T}_{TM}$ is undecidable.

Proof by reduction from $A_{TM}$: Assume $R$ decides $HAL{T}_{TM}$. Construct $S$ to decide $A_{TM}$:

S(<M, w>):
    Run R(<M, w>)
    If R rejects, reject   (M doesn't halt, so can't accept)
    If R accepts, simulate M on w until it halts
        If M accepts, accept
        If M rejects, reject

$S$ would be a decider for $A_{TM}$ — but we just proved $A_{TM}$ is undecidable. Contradiction. So $HAL{T}_{TM}$ is undecidable.

---

Proving Undecidability by Reduction

To prove problem $P$ is undecidable, reduce a known undecidable problem to $P$:

$$A{\le }_{m}B\text{ (mapping reduction) and }A\text{ undecidable }⟹B\text{ undecidable}$$

A mapping reduction from $A$ to $B$ is a computable function $f$ such that:

$$w\in A⟺f(w)\in B$$

---

Notable Undecidable Problems

$E_{TM}$: Emptiness of TM Language

$$E_{TM}=\{⟨M⟩\mid L(M)=\mathrm{\varnothing }\}$$

Undecidable (not even RE). Reduction from $A_{TM}$.

$E{Q}_{TM}$: Equivalence of TMs

$$E{Q}_{TM}=\{⟨M_1,M_2⟩\mid L(M_1)=L(M_2)\}$$

Undecidable (not RE). Reduction from $E_{TM}$: fix $M_2$ as a TM that rejects everything.

$REGULA{R}_{TM}$: Is $L(M)$ Regular?

$$REGULA{R}_{TM}=\{⟨M⟩\mid L(M)\text{ is regular}\}$$

Undecidable (not RE). Rice's Theorem applies.

$CF{L}_{TM}$: Is $L(M)$ Context-Free?

Similarly undecidable.

---

Rice's Theorem

Any nontrivial property of the RE languages is undecidable.

A property $P$ of RE languages is nontrivial if:

• There exists a TM $M_1$ such that $L(M_1)\in P$
• There exists a TM $M_2$ such that $L(M_2)\notin P$

Formal Statement

Let $P$ be any nontrivial subset of RE languages. Then:

$$L_P=\{⟨M⟩\mid L(M)\in P\}$$

is undecidable.

Consequences

Almost every semantic question about programs is undecidable:

• Does the program halt on all inputs?
• Does the program compute $f(x)=x^2$?
• Is the program's output always positive?
• Are two programs equivalent?
• Does the program contain a virus?

Rice's Theorem says: you cannot algorithmically determine any nontrivial behavioral property of programs by inspecting their code.

---

Post's Correspondence Problem (PCP)

Given two lists of strings $A=(a_1,\dots ,a_k)$ and $B=(b_1,\dots ,b_k)$, does there exist a sequence of indices $i_1,i_2,\dots ,i_m$ ($m\ge 1$) such that:

$$a_{i_1}{a}_{i_2}\dots a_{i_m}=b_{i_1}{b}_{i_2}\dots b_{i_m}$$

Theorem: PCP is undecidable.

PCP is a powerful tool for proving undecidability — many problems (ambiguity of CFGs, emptiness of intersection of CFLs, etc.) reduce to PCP.

---

The Recursion Theorem

For any computable function $f$ that transforms TM descriptions, there exists a TM $M$ such that:

$$L(M)=L(f(⟨M⟩))$$

In other words: TMs can obtain and use their own description.

Consequences:

• There exists a TM that prints its own description (a "quine")
• Used to prove Rice's Theorem elegantly
• Underpins self-referential constructions in computability theory

---

Hierarchy of Undecidability

$$\text{Decidable}⊊\text{RE}⊊\text{co-RE}⊊{\mathrm{\Sigma }}_2⊊{\mathrm{\Pi }}_2⊊\cdots$$

• RE (${\mathrm{\Sigma }}_1$): Semi-decidable — TM halts and accepts on YES instances
• co-RE (${\mathrm{\Pi }}_1$): Complement is RE — TM halts and accepts on NO instances
• ${\mathrm{\Delta }}_1$ = Recursive = RE $\cap$ co-RE
• Higher levels correspond to problems with alternating quantifiers

$A_{TM}$ is RE-complete. $E_{TM}$ is co-RE-complete. $E{Q}_{TM}$ is ${\mathrm{\Pi }}_2$-complete.