13 Theory of Undecidability and Reductions

Lecture from: 28.10.2025 | Video: Videos ETHZ

We have previously established the boundaries of what is computable. We defined the Turing Machine as our model for any algorithm, and we discovered that there are strict limits to this model. Specifically, we used diagonalization to find a specific language, the Diagonal Language ($L_{diag}$), which cannot be solved by any Turing Machine.

However, $L_{diag}$ is an artificial construction. It was built specifically to break the machine. To prove that “real world” problems (like analyzing code) are unsolvable, we need a more general tool. We cannot invent a new diagonalization argument for every single problem. This tool is Reduction.

The Method of Reduction

Reduction is the central engine of complexity theory and computability. The core philosophy is: “If I can solve problem B, I can surely solve problem A.”

Recursive Reduction (${\le }_R$)

Imagine we have two languages (decision problems), $L_1$ and $L_2$. We want to understand the difficulty of $L_1$.

We say that $L_1$ is recursively reducible to $L_2$ (denoted $L_1{\le }_R{L}_2$) if the following scenario holds: Assume we possess a hypothetical “Black Box” (or Oracle) that solves $L_2$ instantly and correctly. Even if we don’t know how the Black Box works, we assume it exists. If we can write an algorithm (a Turing Machine) that solves $L_1$ by using this Black Box as a subroutine, then $L_1$ reduces to $L_2$.

The Implication for Undecidability

This relationship implies that $L_2$ is at least as hard as $L_1$.

• If we know $L_1$ is undecidable (impossible to solve), and we show that $L_1{\le }_R{L}_2$, then $L_2$ must also be undecidable.
• Why? Because if $L_2$ were solvable, our reduction algorithm would effectively solve the unsolvable problem $L_1$, which is a contradiction.

Many-One Reduction (${\le }_m$)

We often use a more specific, “stricter” version of reduction called Many-One Reduction (or Input-to-Input Reduction). Instead of using the Black Box as a general subroutine (calling it multiple times, processing its output), we simply transform the input.

We say $L_1{\le }_m{L}_2$ if there exists a computable function $f$ (a Turing Machine that halts and produces an output) that maps inputs from the domain of $L_1$ to the domain of $L_2$ such that: $x\in L_1⟺f(x)\in L_2$

The Reduction Machine

If we have this function $f$, and a hypothetical machine $M_2$ that decides $L_2$, we can build a machine $M_1$ for $L_1$:

1. Take input $x$.
2. Compute $y=f(x)$.
3. Feed $y$ into machine $M_2$.
4. Output exactly what $M_2$ outputs.

If $x$ is a “Yes” instance for $L_1$, $f(x)$ must be a “Yes” instance for $L_2$. If $x$ is a “No” instance, $f(x)$ must be a “No” instance. The answer is preserved perfectly.

Key Relationship: If $L_1{\le }_m{L}_2$, then $L_1{\le }_R{L}_2$. Many-one reduction is a special case of recursive reduction where the oracle is called exactly once at the very end.

Classes of Languages and Complements

To understand which problems are solvable, we must look at the relationship between a language and its complement.

Recursive Languages (${\mathcal{L}}_R$)

A language $L$ is Recursive (Decidable) if there exists a TM that accepts all $w\in L$ and rejects all $w\notin L$. The machine always halts.

Theorem

If $L$ is Recursive, then its complement $L^c$ is also Recursive.

Proof: Take the machine $M$ for $L$. Construct a new machine $M^{\prime }$ that simulates $M$.

• If $M$ accepts, $M^{\prime }$ rejects.
• If $M$ rejects, $M^{\prime }$ accepts. Since $M$ always halts, $M^{\prime }$ always halts. Thus $L^c$ is decidable.

Recursively Enumerable Languages (${\mathcal{L}}_{RE}$)

A language $L$ is Recursively Enumerable (RE) if there exists a TM that accepts all $w\in L$. If $w\notin L$, the machine may reject or loop forever.

The Trap of Complements in ${\mathcal{L}}_{RE}$

If $L$ is RE but not Recursive, what about $L^c$? We cannot simply swap the “accept” and “reject” states. If the original machine $M$ loops forever on an input $w\notin L$, the swapped machine will still loop forever. It will never reach a state where it can say “Accept”.

Therefore, for a language $L\in {\mathcal{L}}_{RE}\setminus {\mathcal{L}}_R$:

1. $L$ is RE (semi-decidable).
2. $L^c$ is not RE (completely unrecognizable).

If both $L$ and $L^c$ were RE, we could run both machines in parallel. One of them would eventually accept, telling us definitively whether $x\in L$ or $x\in L^c$. This would make $L$ recursive (decidable).

The Diagonal Language and its Complement

Recall the Diagonal Language $L_{diag}$, which consists of binary strings $w$ such that the machine encoded by $w$ does not accept $w$. $w_i\in L_{diag}⟺M_i\text{ does not accept }{w}_i$ We proved previously that $L_{diag}\notin {\mathcal{L}}_{RE}$. No Turing Machine can recognize this language.

Now consider the complement, $\overline{L_{diag}}$: $\overline{L_{diag}}=\{w_i\mid M_i\text{ accepts }{w}_i\}$ Is this language recognizable?

Yes. We can build a Universal Turing Machine $U$. Given input $w_i$:

1. Decode $w_i$ (find out what canonical index $i$ it belongs to) to find the description of machine $M_i$ (by enumerating Turing machines…).
2. Simulate $M_i$ on input $w_i$.
3. If $M_i$ accepts, $U$ accepts.

If $M_i$ loops, $U$ loops, but that is allowed for RE languages.

Conclusion: $\overline{L_{diag}}$ is in ${\mathcal{L}}_{RE}$, but it is not in ${\mathcal{L}}_R$ (because if it were, its complement $L_{diag}$ would be RE, which we know is false).

The Universal Language ($L_u$)

The artificial nature of the diagonal language ($L_{diag}$) might make it seem like an edge case. However, we can immediately identify a very natural language that is closely related. Turing introduced the concept of a machine that can simulate any other machine: the Universal Turing Machine ($U$).

The corresponding decision problem is the Universal Language ($L_u$). It asks whether a given Turing Machine accepts a given input word.

$$L_u=\{(⟨M⟩,w)\mid M\text{ is a TM that accepts }w\}$$

Constructing the Universal Turing Machine

We can prove that $L_u$ is recursively enumerable (RE) by actually building a machine $U$ that recognizes it. This machine $U$ is an interpreter.

Encoding and Input: The machine $U$ takes a single input string $z$.

1. It first checks if $z$ is a valid encoding of a pair $(⟨M⟩,w)$, typically separated by a delimiter like #. If the syntax is wrong, it rejects.
2. If valid, $z$ contains the “blueprint” of a machine $M$ and the input data $w$.

Simulation Process: To keep things simple, let’s imagine $U$ as a 3-tape machine (which we know is equivalent to a 1-tape machine):

• Tape 1: Stores the description of $M$ (its states, transitions $\delta$, etc.).
• Tape 2: Stores the “current” tape content of the simulated machine $M$. Initially, this is just $w$.
• Tape 3: Stores the current state of $M$ (e.g., a number like 0 for $q_0$, 27 for $q_{27}$).

The Universal Machine $U$ operates in a loop:

1. Read State & Symbol: It looks at Tape 3 to find $M$‘s current state (e.g., $q_5$) and looks at the head position on Tape 2 to see the symbol being read (e.g., 1).
2. Find Transition: It scans Tape 1 (the description of $M$) to find the transition rule that matches state $q_5$ and symbol 1.
   • Example Rule: (q_5, 1) -> (q_9, 0, R)
3. Execute Transition:
   • Update State: Overwrite Tape 3 with the new state index 9.
   • Write Symbol: Overwrite the symbol on Tape 2 with 0.
   • Move Head: Move the head on Tape 2 one step to the Right.
4. Check Halting:
   • If the new state is $q_{acc}$, $U$ halts and Accepts.
   • If the new state is $q_{rej}$, $U$ halts and Rejects.
   • If the transition cannot be found (or $M$ loops), $U$ continues the simulation indefinitely.

This machine $U$ accepts exactly those pairs $(⟨M⟩,w)$ where $M$ accepts $w$. Therefore, $L_u$ is Recursively Enumerable.

Undecidability of $L_u$

While $U$ can recognize YES instances, it cannot solve the decision problem. If $M$ runs forever on $w$, $U$ will simply simulate it forever. It will never stop to say “No.”

Theorem

$L_u$ is not Recursive (it is undecidable).

Proof by Reduction ($\overline{L_{diag}}{\le }_m{L}_u$)

We know that the complement of the diagonal language ($\overline{L_{diag}}$) is undecidable. We will show that if we could decide $L_u$, we could decide $\overline{L_{diag}}$.

Recall: $w\in \overline{L_{diag}}⟺M_w\text{ accepts }w$. (Here $M_w$ is the machine whose encoding corresponds to the index of word $w$).

The Reduction Algorithm

We construct a Turing Machine $f$ that translates questions about $\overline{L_{diag}}$ into questions about $L_u$.

1. Input: A word $x$. We want to know if $x\in \overline{L_{diag}}$.
2. Compute Index: Calculate the index $i$ such that $x$ is the $i$-th word ($w_i$) in the standard enumeration.
3. Generate Machine: Construct the encoding of the $i$-th Turing Machine, $M_i$. This is computable because we have a standard lexicographical enumeration of all valid TM strings.
4. Output: The pair $(⟨M_i⟩,w_i)$.

Verification:

• If $x\in \overline{L_{diag}}$, then by definition $M_i$ accepts $w_i$. Thus, the pair $(⟨M_i⟩,w_i)$ is in $L_u$.
• If $x\notin \overline{L_{diag}}$, then $M_i$ does not accept $w_i$. Thus, the pair is not in $L_u$.

This function $f$ is a valid Many-One reduction. Since $\overline{L_{diag}}$ is undecidable, $L_u$ must also be undecidable.

The Halting Problem ($L_H$)

This leads us to the Halting Problem ($L_H$ or $H$). This is subtly different from $L_u$.

• $L_u$ asks: “Does $M$ reach the Accept state?”
• $L_H$ asks: “Does $M$ reach ANY halting state ($q_{acc}$ or $q_{rej}$)?”

$$L_H=\{(⟨M⟩,w)\mid M\text{ halts on input }w\}$$

We will prove $L_H$ is undecidable by reducing $L_u$ to it ($L_u\le L_H$). The logic is: “If I could determine whether a machine stops, I could determine whether it accepts.”

Method 1: Recursive Reduction ($L_u{\le }_R{L}_H$)

This method uses a hypothetical “Halting Oracle” as a subroutine.

The Algorithm for Deciding $L_u$

Input: A pair $(⟨M⟩,w)$.

1. Call Oracle: Ask the Halting Oracle “Does $M$ halt on $w$?”
2. Case NO: The Oracle says $M$ runs forever.
   • Since it never stops, it can never reach the $q_{acc}$ state.
   • Therefore, $M$ does not accept.
   • Output: REJECT.
3. Case YES: The Oracle says $M$ halts eventually.
   • We don’t know if it accepts, only that it stops.
   • But because we know it stops, it is safe to simulate it!
   • Run $U(⟨M⟩,w)$. The simulation is guaranteed to finish.
   • If the simulation ends in $q_{acc}$, Output: ACCEPT.
   • If the simulation ends in $q_{rej}$, Output: REJECT.

This algorithm would perfectly decide $L_u$. But $L_u$ is undecidable. Therefore, the Halting Oracle cannot exist.

Method 2: Many-One Reduction ($L_u{\le }_m{L}_H$)

We can also achieve this by transforming the machine itself, avoiding the need for an “Oracle” concept. We want a computable function $f$ that takes an instance of $L_u$ and creates an instance of $L_H$. $(⟨M⟩,w)\stackrel{f}{\to }(⟨M^{\prime }⟩,w^{\prime })$ such that $M$ accepts $w⟺M^{\prime }$ halts on $w^{\prime }$.

The Construction of $M^{\prime }$

Given the input code for $M$, we can write the code for a new machine $M^{\prime }$ that modifies the behavior of $M$.

• $M^{\prime }$ runs exactly like $M$ on input $w$, with one crucial change to its transition function.
• Redirection: We identify all transitions in $M$ that lead to the reject state ($q_{rej}$). We redirect these transitions to point to a new state that enters an infinite loop.
  • Original rule: (q_5, a) -> (q_rej, b, L)
  • New rule in $M^{\prime }$: (q_5, a) -> (q_loop, b, L)
  • Loop rule: (q_loop, any) -> (q_loop, any, N)

Behavior Analysis

1. If $M$ accepts $w$: $M^{\prime }$ simulates $M$, reaches $q_{acc}$, and halts. → $M^{\prime }$ Halts.
2. If $M$ rejects $w$: $M^{\prime }$ simulates $M$, would have gone to $q_{rej}$, but is redirected to $q_{loop}$. It runs forever. → $M^{\prime }$ Loops.
3. If $M$ loops on $w$: $M^{\prime }$ simulates $M$ and just loops naturally. → $M^{\prime }$ Loops.

Conclusion

$M^{\prime }$ halts $⟺$ $M$ accepts.

We have successfully reduced $L_u$ to $L_H$. Since $L_u$ is undecidable, the Halting Problem is undecidable.

Summary of the Undecidability Landscape

We have built a hierarchy of impossible problems, each proof resting on the previous one.

1. $L_{diag}$ (Diagonal Language): Not Recursively Enumerable (Not RE).
   • Proof: Cantor’s Diagonalization on the table of all TMs.
2. $\overline{L_{diag}}$ (Complement of Diagonal): RE but Undecidable.
   • Proof: It is RE because we can simulate $M_i$ on $w_i$. It is undecidable because if it were, its complement ($L_{diag}$) would be RE.
3. $L_u$ (Universal Language): RE but Undecidable.
   • Proof: Undecidable by reduction from $\overline{L_{diag}}$. Solving $L_u$ allows us to solve $\overline{L_{diag}}$.
4. $L_H$ (Halting Problem): RE but Undecidable.
   • Proof: Undecidable by reduction from $L_u$. Solving Halting allows us to solve Acceptance.

This chain of reductions is the standard methodology for proving undecidability. We start with a known hard problem and show that our new problem is “at least as hard.”