Undecidability

From Computability, Complexity & Algorithms — Charles Brubaker and Lance Fortnow

Introduction

Some problems are simply impossible to solve algorithmically — no compiler, no computer, no quantum machine can decide them. The halting problem is the canonical example: determining whether arbitrary code terminates on a given input is undecidable.

---

Diagonalization

The diagonalization technique constructs undecidability proofs by generating self-referential paradoxes.

Motivating Example: Heterological Words

An English adjective is autological if it describes itself (e.g., “short” is short) and heterological if it does not (e.g., “long” is not long).

Table of adjectives — rows are adjectives, columns are properties. A 1 means the adjective possesses that property.

Paradox: Is the word “heterological” itself heterological?

• If yes (it is heterological) → it describes itself → it is autological — contradiction.

• If no (it is autological) → it does not describe itself → it is heterological — contradiction.

The diagonal entry for “heterological” produces the paradox.

Application to Turing Machines

Enumerate all Turing machines \(M_1, M_2, \ldots\) and all their encodings \(\langle M_1 \rangle, \langle M_2 \rangle, \ldots\)

Build a table where entry \((i, j) = 1\) if \(M_i\) accepts \(\langle M_j \rangle\).

Turing machine acceptance table — rows are machines, columns are encodings.

Define the diagonal language:

\[L = \{ \langle M \rangle \mid \langle M \rangle \notin L(M) \}\]

Suppose machine \(M_L\) recognises \(L\). Is \(\langle M_L \rangle \in L(M_L)\)?

• If yes → \(\langle M_L \rangle \in L\) → \(\langle M_L \rangle \notin L(M_L)\) — contradiction.

• If no → \(\langle M_L \rangle \notin L\) → \(\langle M_L \rangle \in L(M_L)\) — contradiction.

The diagonal element for \(M_L\) yields the contradiction — \(M_L\) cannot exist.

Conclusion: \(L\) is not recognisable (not even semi-decidable).

Quiz: Does the argument apply to other computational models?

---

The Diagonal Language \(D_{TM}\)

Define the complement:

\[D_{TM} = \{ \langle M \rangle \mid \langle M \rangle \in L(M) \}\]

Since \(L\) (its complement) is unrecognisable, \(D_{TM}\) is not decidable. (A language is decidable iff both it and its complement are recognisable.)

---

Mapping Reductions

Definition: Language \(A\) is mapping-reducible to language \(B\), written \(A \leq_m B\), if there exists a computable function \(f\) such that:

\[w \in A \iff f(w) \in B\]

Mapping reduction: a computable \(f\) translates membership in \(A\) to membership in \(B\).

Consequences

Composing a reduction with a decider / recogniser for \(B\) gives one for \(A\).

If \(A \leq_m B\) then:

1. \(B\) decidable \(\Rightarrow\) \(A\) decidable.

2. \(B\) recognisable \(\Rightarrow\) \(A\) recognisable.

3. \(A\) undecidable \(\Rightarrow\) \(B\) undecidable. (contrapositive of 1)

4. \(A\) unrecognisable \(\Rightarrow\) \(B\) unrecognisable. (contrapositive of 2)

Quiz: Which decidability / recognisability conclusions follow from given reductions?

Simple Reduction Pattern

To show language \(B\) is undecidable, reduce \(D_{TM} \leq_m B\):

Code structure for the reduction: given \(\langle M \rangle\), construct an input \(f(\langle M \rangle)\) for \(B\).

Proof that \(B\) is undecidable via the reduction.

Quiz: Which reduction directions are valid for the given problems?

---

The Halting Problem

Formal definition:

\[H_{TM} = \{ \langle M \rangle \mid M \text{ halts on } \varepsilon \}\]

Theorem: \(H_{TM}\) is undecidable.

Proof (reduction \(D_{TM} \leq_m H_{TM}\)):

Given \(\langle M \rangle\), construct machine \(N\):

N on input w:
    ignore w
    run M on ⟨M⟩
    if M accepts ⟨M⟩: accept
    if M rejects ⟨M⟩: reject

Then \(\langle M \rangle \in D_{TM}\) iff \(M\) accepts \(\langle M \rangle\) iff \(N\) halts on \(\varepsilon\) iff \(\langle N \rangle \in H_{TM}\).

So \(f(\langle M \rangle) = \langle N \rangle\) is the required computable reduction.

Reduction machine \(N\) demonstrating the undecidability of \(H_{TM}\).

Significance: No algorithm — on any hardware, including quantum computers — can decide whether an arbitrary program halts on an arbitrary input.

Filtering

Some reductions cannot simply accept or reject everything; they must inspect the input and conditionally simulate another machine:

Filtering technique: the reduction machine examines its input before deciding which computation to simulate.

---

Rice’s Theorem

Setup: A semantic property of Turing machines is a set \(L\) of TM encodings such that \(L(M_1) = L(M_2) \Rightarrow (\langle M_1 \rangle \in L \iff \langle M_2 \rangle \in L)\). In other words, \(L\) depends only on what a machine computes, not how it computes it.

Theorem (Rice): Every non-trivial semantic property of Turing machines is undecidable.

Non-trivial means \(L\) is neither empty nor the set of all TM encodings — there exist machines both inside and outside \(L\).

Formal statement of Rice’s theorem.

Proof Sketch (two cases)

Let \(M_\emptyset\) be a TM that immediately rejects everything (\(L(M_\emptyset) = \emptyset\)).

Case 1: \(\langle M_\emptyset \rangle \notin L\). Let \(M_A \in L\) (exists by non-triviality). Given \(\langle M \rangle\), construct \(N\):

N on input x:
    run M on ⟨M⟩
    if M accepts ⟨M⟩: run M_A on x and return its answer
    else: reject

If \(\langle M \rangle \in D_{TM}\), then \(N\) simulates \(M_A\), so \(L(N) = L(M_A)\) and \(\langle N \rangle \in L\). Otherwise \(L(N) = \emptyset\) and \(\langle N \rangle \notin L\).

Case 1 of Rice’s theorem proof.

Case 2: \(\langle M_\emptyset \rangle \in L\). Apply Case 1 to the complement \(\overline{L}\) (also a non-trivial semantic property), concluding \(\overline{L}\) is undecidable, hence \(L\) is undecidable.

Case 2 of Rice’s theorem proof — apply Case 1 to the complement.

Practical implication: Any property of a program’s behaviour — does it accept the empty string? does it halt on all inputs? does it output “hello”? — is undecidable.

Quiz: Apply Rice’s theorem to classify properties as decidable or undecidable.

Concluding remarks.

---

Proof Strategy Summary

To show language \(B\) is undecidable:

1. Choose a known undecidable language \(A\) (typically \(D_{TM}\) or \(H_{TM}\)).

2. Construct a computable function \(f\) such that \(w \in A \iff f(w) \in B\).

3. Argue correctness: if a decider for \(B\) existed, composing with \(f\) would decide \(A\) — contradiction.

---

Key Definitions

Term	Definition
Decidable	A TM halts and accepts/rejects every input correctly.
Recognisable (semi-decidable)	A TM accepts every string in the language; may loop on strings not in it.
\(A \leq_m B\)	Computable \(f\) with \(w \in A \iff f(w) \in B\).
Semantic property	Depends only on the language recognised, not the TM’s implementation.
Non-trivial property	Holds for some TMs and fails for others.

---

Key Results

\[L = \{ \langle M \rangle \mid \langle M \rangle \notin L(M) \} \quad \text{— unrecognisable (diagonalisation)}\]

\[D_{TM} = \{ \langle M \rangle \mid \langle M \rangle \in L(M) \} \quad \text{— undecidable}\]

\[H_{TM} = \{ \langle M \rangle \mid M \text{ halts on } \varepsilon \} \quad \text{— undecidable}\]

\[A \leq_m B,\ A \text{ undecidable} \;\Longrightarrow\; B \text{ undecidable}\]

\[\text{Rice's Theorem: every non-trivial semantic property is undecidable}\]

---

Further Reading

• Post Correspondence Problem — another natural undecidable problem

• Reducibility and the arithmetical hierarchy (\(\Sigma_1\), \(\Pi_1\), …)

• Gödel’s incompleteness theorems — undecidability in formal logic