14 Reductions, The Halting Problem, and Emptiness

Lecture from: 31.10.2025 | Video: Videos ETHZ

Recap: The Landscape of Undecidability

We have established a hierarchy of languages based on their solvability.

• ${\mathcal{L}}_R$ (Recursive): The problem is decidable. A Turing Machine exists that always halts and gives the correct Yes/No answer.
• ${\mathcal{L}}_{RE}$ (Recursively Enumerable): The problem is semi-decidable. A Turing Machine exists that will eventually accept a Yes-instance, but for a No-instance, it might run forever.
• Outside ${\mathcal{L}}_{RE}$: The problem is not even recognizable.

We proved that the Diagonal Language ($L_{diag}$) lies outside ${\mathcal{L}}_{RE}$. Its complement, $\overline{L_{diag}}$, lies inside ${\mathcal{L}}_{RE}$ but outside ${\mathcal{L}}_R$. We also introduced the Universal Language ($L_u$), which asks if a given machine $M$ accepts a given string $w$. By reducing $\overline{L_{diag}}$ to $L_u$, we proved that $L_u$ is also undecidable.

The Halting Problem ($L_H$)

We now turn to a problem even more fundamental than acceptance: Halting. When we run a program, we often want to know: “Will this code eventually finish, or is it stuck in an infinite loop?”

Formal Definition

$L_H=\{(⟨M⟩,x)\mid M\text{ halts on input }x\}$ Here, “halts” means the machine reaches either the $q_{accept}$ or $q_{reject}$ state. If the machine loops, it never reaches either.

Undecidability via Recursive Reduction

Is $L_H$ decidable? Intuitively, no. If we could solve it, we could solve the Universal Language $L_u$. Let’s verify this using a Recursive Reduction ($L_u{\le }_R{L}_H$).

Imagine we have a hypothetical “Black Box” (Oracle) that solves $L_H$. We can use it to build a decider for $L_u$ (Acceptance):

1. Input: A pair $(⟨M⟩,x)$. We want to know if $M$ accepts $x$.
2. Ask the Oracle: “Does $M$ halt on $x$?”
3. Case NO: If the Oracle says $M$ does not halt, then $M$ loops forever. Consequently, it can never reach $q_{accept}$. We reject.
4. Case YES: If the Oracle says $M$ does halt, we are safe to simulate $M$ on $x$. We know the simulation will not run forever.
   • If the simulation lands in $q_{accept}$, we accept.
   • If the simulation lands in $q_{reject}$, we reject.

Since this algorithm would decide $L_u$, and we know $L_u$ is undecidable, the Oracle for $L_H$ cannot exist. Thus, $L_H$ is undecidable.

Many-One Reductions (${\le }_{ee}$) and Equivalence

While recursive reduction is powerful, complexity theory often relies on the stricter Many-One Reduction (or Input-to-Input Reduction, ${\le }_{ee}$). Here, we cannot use the Oracle as a subroutine or invert its output. We must transform the input of Problem A directly into the input of Problem B.

$A{\le }_{ee}B⟺\exists \text{ computable }f:x\in A⟺f(x)\in B$

Let’s examine the relationship between Acceptance ($L_u$) and Halting ($L_H$) using this stricter tool. It turns out they are equivalent: we can reduce them to each other.

Direction 1: Reducing Acceptance to Halting ($L_u{\le }_{ee}{L}_H$)

We want to transform a question about acceptance (“Does $M$ accept $w$?”) into a question about halting (“Does $M^{\prime }$ halt on $w$?”).

The Transformation

We construct a new machine $M^{\prime }$ that wraps the original machine $M$.

• If $M$ reaches $q_{acc}$, $M^{\prime }$ should halt. (This is natural behavior).
• If $M$ reaches $q_{rej}$, $M^{\prime }$ should NOT halt.
• If $M$ loops, $M^{\prime }$ should NOT halt. (This is natural behavior).

Construction of $M^{\prime }$

We modify the transition function of $M$. We locate every transition that points to the reject state $q_{rej}$. Instead of letting the machine reject and halt, we redirect these transitions to a new state, $q_{loop}$, which simply transitions to itself forever.

Outcome

• $M$ accepts $w⟹M^{\prime }$ halts.
• $M$ rejects $w⟹M^{\prime }$ enters the infinite loop (does not halt).
• $M$ loops on $w⟹M^{\prime }$ loops (does not halt).

Thus, $M\text{ accepts }w⟺M^{\prime }\text{ halts on }w$. We have successfully reduced $L_u$ to $L_H$.

Direction 2: Reducing Halting to Acceptance ($L_H{\le }_{ee}{L}_u$)

Now let’s go the other way. We want to transform a question about halting (“Does $M$ halt on $w$?”) into a question about acceptance (“Does $M^{\prime }$ accept $w$?”).

The Transformation

We need to ensure that whenever $M$ stops (regardless of whether it said Yes or No), our new machine $M^{\prime }$ says “Yes” (Accepts).

Construction of $M^{\prime }$

We again modify the transition function of $M$.

• We look at the $q_{acc}$ state. It stays as it is.
• We look at the $q_{rej}$ state. We redirect all transitions that would have gone to $q_{rej}$ so that they now go to $q_{acc}$ instead.

Outcome

• $M$ halts (accepts) $⟹M^{\prime }$ accepts.
• $M$ halts (rejects) $⟹M^{\prime }$ accepts (because we bent the pointer).
• $M$ loops $⟹M^{\prime }$ loops (does not accept).

Thus, $M\text{ halts on }w⟺M^{\prime }\text{ accepts }w$.

This proves that $L_u$ and $L_H$ are computationally equivalent under Many-One reduction. They reside in the same degree of unsolvability.

The Emptiness Problem ($L_{\varnothing }$) and Its Complement

We now move beyond properties of simulation (like Halting) to semantic properties of the language a machine accepts.

The Emptiness Problem asks: Given a Turing Machine $M$, is the language it accepts empty? In other words, does it reject or loop on every possible input? $L_{\varnothing }=\{⟨M⟩\mid L(M)=\varnothing \}$

Conversely, we have the Non-Emptiness Problem (or the complement of Emptiness): $\overline{L_{\varnothing }}=\{⟨M⟩\mid L(M)\ne \varnothing \}$ This asks: Does the machine accept at least one input?

Is $\overline{L_{\varnothing }}$ Recursively Enumerable?

The transcript discusses two ways to see this.

Method 1: Dovetailing (Deterministic)

We want to find one witness string $w$ that $M$ accepts. We cannot check strings sequentially ($w_1,w_2,\dots$) because if $M$ loops on $w_1$, we never get to check $w_2$. Instead, we use Dovetailing (Schwalbenschwanz-Methode). We simulate $M$ on all inputs in parallel slices:

• Phase 1: Run $M$ on $w_1$ for 1 step.
• Phase 2: Run $M$ on $w_1$ for 2 steps; Run $M$ on $w_2$ for 2 steps.
• …
• Phase $k$: Run $M$ on $w_1,\dots ,w_k$ for $k$ steps.

If there is any word that is accepted, it will be accepted in a finite number of steps. Our dovetailing procedure will eventually reach that depth and halt with an “Accept”.

Method 2: Nondeterminism (The “Magical” Solution)

The lecture highlights a much faster, conceptual way to see this using a Nondeterministic Turing Machine (NTM). We know that DTMs and NTMs are equivalent in power (${\mathcal{L}}_{RE}={\mathcal{L}}_{NRE}$).

We can build an NTM, let’s call it $N$, that recognizes $\overline{L_{\varnothing }}$:

1. Input: $⟨M⟩$ (the encoding of the machine we want to check).
2. Guess: Nondeterministically write a binary string $w$ on the tape. Because of nondeterminism, one branch of the computation will “guess” the correct witness string if it exists.
3. Verify: Simulate $M$ on $w$.
4. Accept: If the simulation accepts, then $N$ accepts.

If there exists any word $w\in L(M)$, the NTM has a computation path that guesses $w$ and accepts. Therefore, $N$ recognizes $\overline{L_{\varnothing }}$. Since NTMs are equivalent to DTMs, $\overline{L_{\varnothing }}$ is in ${\mathcal{L}}_{RE}$.

Proving Undecidability of $\overline{L_{\varnothing }}$

We know $\overline{L_{\varnothing }}$ is recognizable. Is it decidable? We suspect not. To prove it, we will use a Many-One Reduction (${\le }_{ee}$) from the Universal Language $L_u$. $L_u{\le }_{ee}\overline{L_{\varnothing }}$

The Goal

We need a computable function (a transformation) that takes an instance of $L_u$ (a pair $(⟨M⟩,w)$) and produces an instance of $\overline{L_{\varnothing }}$ (a new machine $⟨B_x⟩$) such that: $M\text{ accepts }w⟺L(B_x)\ne \varnothing$

Constructing the Machine $B_x$

This is a clever construction where we build a machine that ignores its own input. The machine $B_x$ is hardcoded with the descriptions of $M$ and $w$.

Here is the code for $B_x$ (on input $y$):

1. Delete the input $y$. $B_x$ wipes its tape clean. It doesn’t care what input it received.
2. Write $w$ on the tape. $B_x$ writes the hardcoded string $w$ (from our $L_u$ instance) onto its tape.
3. Simulate $M$ on $w$. $B_x$ runs the code of $M$ on this specific input $w$.
4. Accept if $M$ accepts. If the simulation reaches $q_{acc}$, $B_x$ accepts.

Analysis of $L(B_x)$

The behavior of $B_x$ depends entirely on the result of the fixed simulation of $M$ on $w$. It does not depend on its own input $y$.

• Case 1: $M$ accepts $w$. The simulation in step 3 succeeds. Therefore, $B_x$ proceeds to step 4 and accepts. Since this logic holds for any input $y$ (because $y$ was deleted at the start), $B_x$ accepts every possible string. $L(B_x)={\Sigma }^{\ast }$ Is this language non-empty? Yes. So $⟨B_x⟩\in \overline{L_{\varnothing }}$.

• Case 2: $M$ does not accept $w$ (rejects or loops). The simulation in step 3 never reaches an accepting state (it either rejects or runs forever). Therefore, $B_x$ never reaches step 4. It accepts nothing. $L(B_x)=\varnothing$ Is this language non-empty? No. So $⟨B_x⟩\notin \overline{L_{\varnothing }}$.

Conclusion

We have successfully reduced $L_u$ to $\overline{L_{\varnothing }}$. $(⟨M⟩,w)\in L_u⟺⟨B_x⟩\in \overline{L_{\varnothing }}$ Since deciding $L_u$ is impossible, deciding $\overline{L_{\varnothing }}$ must also be impossible.

The Fate of $L_{\varnothing }$

Since $\overline{L_{\varnothing }}$ is undecidable, its complement $L_{\varnothing }$ (the Emptiness Problem) is also undecidable. Furthermore, since $\overline{L_{\varnothing }}$ is in ${\mathcal{L}}_{RE}$ (recognizable), its complement $L_{\varnothing }$ cannot be in ${\mathcal{L}}_{RE}$ (unless it were recursive, which we just proved it isn’t).

Thus, we have placed these problems on our map:

• $\overline{L_{\varnothing }}$ (Non-Emptiness): RE but Undecidable.
• $L_{\varnothing }$ (Emptiness): Not RE (completely unrecognizable).

Summary

We have successfully used reductions to expand our list of undecidable problems.

1. Halting ($L_H$): Undecidable. We can reduce Acceptance to Halting ($q_{rej}\to q_{loop}$) and Halting to Acceptance ($q_{rej}\to q_{acc}$).
2. Non-Emptiness ($L_{\ne \varnothing }$): Undecidable. We reduced Acceptance to Non-Emptiness by constructing a machine $B_x$ that ignores its input and runs the specific test case $M$ on $x$.

This last proof technique, wrapping a specific computation inside a machine that ignores its input, is a powerful pattern. It hints at a much broader truth: Rice’s Theorem, which states that any non-trivial property of the language recognized by a Turing Machine is undecidable. We will explore this in the next lecture.