12 Undecidability and Reductions

Lecture from: 24.10.2025 | Video: Videos ETHZ

We pick up where we left off: Nondeterministic Turing Machines (NTMs). It is crucial to dispel a common myth immediately: Nondeterminism is not randomness.

In a randomized algorithm, you flip a coin, and we analyze the probability of getting the right answer. In Nondeterminism, the machine has a “magical” ability to guess the correct path among many options. If there exists any sequence of choices that leads to the accept state, the NTM finds it.

The Computation Tree

For a Deterministic TM (DTM), the computation is a straight line: Configuration $C_0\to C_1\to C_2\dots$. For an NTM, because the transition function $\delta$ maps to a set of possible moves, the computation forms a tree.

• Root: Start configuration.
• Branches: Different choices made at each step.
• Acceptance: An input $w$ is accepted if at least one node in the entire tree is an accepting configuration.
• Rejection: An input is rejected only if every branch ends in a rejecting state.

Example: The Traveling Salesperson Problem (TSP)

To see the power of this model, consider TSP: Given a graph, is there a tour that visits every node exactly once?

• Deterministic approach: We must iterate through all $n!$ permutations of nodes and check them. This is incredibly slow ($O(n!)$).
• Nondeterministic approach:
  1. Guess: The NTM nondeterministically writes a permutation of numbers $1\dots n$ on the tape. Because of the branching nature, effectively every permutation is generated on some branch of the computation tree.
  2. Verify: The machine deterministically checks if the sequence on the tape is a valid tour in the graph. This verification takes polynomial time.

If a Hamiltonian cycle exists, one branch will guess it correctly and accept. Thus, the NTM solves TSP efficiently. This leads to the complexity class NP (Nondeterministic Polynomial time), which we will discuss later.

Equivalence of NTM and DTM

Since NTMs seem so powerful (solving TSP instantly!), do they allow us to solve problems that are fundamentally impossible for DTMs? The answer is no.

Theorem: For every Nondeterministic Turing Machine $N$, there exists an equivalent Deterministic Turing Machine $D$. $L(N)=L(D)$

The Simulation Problem

How do we simulate the NTM $N$ using a DTM $D$? If we simply use Depth-First Search (DFS) on the computation tree of $N$, we might fail. Why? Because a specific branch of $N$ might run forever (infinite loop). If $D$ follows that path, it will never return to check the other branches, potentially missing an accepting state elsewhere.

The Solution: Breadth-First Search (BFS)

We must simulate the tree layer by layer.

1. Check all computations of 1 step.
2. Check all computations of 2 steps.
3. …and so on.

Construction of $D$: We use a 3-tape DTM (which we know is equivalent to a 1-tape DTM):

1. Input Tape: Stores the original input $w$.
2. Simulation Tape: Used to simulate one specific branch of $N$.
3. Address Tape: Stores a sequence of numbers (e.g., 1-3-2) telling $D$ which choices to make in the tree.

The Algorithm:

1. Generate the next “address” string in canonical order (lexicographically: $ϵ,0,1,00,01,\dots$).
2. Clear the simulation tape and copy $w$ onto it.
3. Run $N$ on the simulation tape. Whenever $N$ needs to make a nondeterministic choice, look at the next digit on the Address Tape to decide which move to make.
4. If the simulation reaches $q_{acc}$, Accept.
5. If the simulation rejects or runs out of address digits (meaning this branch is valid but hasn’t accepted yet), abort this branch and loop back to Step 1.

If $N$ accepts $w$, the accepting configuration exists at some finite depth. Our BFS enumeration will eventually generate the address string that leads to that node, and $D$ will accept. Thus, nondeterminism does not increase computability, only efficiency.

Countability: The Size of Infinity

To prove that there are problems computers cannot solve, we must compare the number of possible programs vs. the number of possible problems.

Countable Sets

A set is countable if we can list its elements: $a_1,a_2,a_3,\dots$.

• $\mathbb{N}$ (Natural numbers) is countable.
• ${\Sigma }^{\ast }$ (All binary strings) is countable (Canonical order: $\lambda ,0,1,00,01,\dots$).
• $\mathbb{N}\times \mathbb{N}$ (Pairs of numbers) is countable. (Cantor’s “zigzag” or anti-diagonal argument proves we can map 2D coordinates to a 1D list).

The Set of Turing Machines is Countable

Every Turing Machine can be encoded as a finite binary string.

• We assume a standardized encoding (e.g., encoding states, transitions, and alphabets into binary).
• Therefore, the set of all Turing Machines is a subset of $\{0,1{\}}^{\ast }$.
• Since $\{0,1{\}}^{\ast }$ is countable, the set of all Turing Machines is countable. We can enumerate them: $M_1,M_2,M_3,\dots$.

The Set of Problems is Uncountable

A “problem” is a language (a set of strings). The set of all possible languages over $\{0,1\}$ is the power set $\mathcal{P}(\{0,1{\}}^{\ast })$.

Using Cantor’s Diagonalization argument (similar to proving the real numbers are uncountable), we can show that the set of all languages is uncountable.

Conclusion: There are countably many algorithms (${\aleph }_0$), but uncountably many problems ($2^{{\aleph }_0}$). $|\text{Algorithms}|\ll |\text{Problems}|$ Therefore, there are infinitely many problems that cannot be solved by any algorithm.

The Diagonal Language ($L_{diag}$)

We know unsolvable problems exist. Now, we will construct one explicitly using Diagonalization.

Let’s define an infinite boolean matrix $A$ where:

• Rows ($i$) represent the enumeration of all Turing Machines: $M_1,M_2,M_3\dots$
• Columns ($j$) represent the enumeration of all input strings: $w_1,w_2,w_3\dots$

The entry $A_{ij}=1$ if machine $M_i$ accepts word $w_j$. It is $0$ otherwise (rejects or loops).

We define the Diagonal Language $L_{diag}$ to be the set of strings that “flip” the behavior on the diagonal:

$$L_{diag}=\{w_i\in \{0,1{\}}^{\ast }\mid M_i\text{ does NOT accept }{w}_i\}$$

If $M_i$ accepts $w_i$, then $w_i\notin L_{diag}$. If $M_i$ does not accept $w_i$, then $w_i\in L_{diag}$.

Theorem

$L_{diag}$ is not Recursively Enumerable (RE). Meaning: No Turing Machine exists that recognizes this language.

Proof by Contradiction

1. Assume $L_{diag}$ is RE. Then there exists some TM $M$ such that $L(M)=L_{diag}$.
2. Since we enumerated all TMs, this machine $M$ must appear in our list at some index $k$. So, $M=M_k$.
3. Consider the input string $w_k$ (the $k$-th word). Is $w_k\in L_{diag}$?
4. Case A: Assume $w_k\in L_{diag}$.
   • By definition of $L_{diag}$, this means $M_k$ does not accept $w_k$.
   • But since $L(M_k)=L_{diag}$, if $w_k$ is in the language, $M_k$ must accept it.
   • Contradiction.
5. Case B: Assume $w_k\notin L_{diag}$.
   • By definition of $L_{diag}$, this means $M_k$ accepts $w_k$.
   • But since $L(M_k)=L_{diag}$, if $M_k$ accepts it, it must be in the language.
   • Contradiction.

Both cases lead to a contradiction. Therefore, the machine $M_k$ cannot exist. $L_{diag}$ is undecidable and not even RE.

The Method of Reduction

We have successfully constructed one specific language, $L_{diag}$, that is provably not recursively enumerable. This is a massive breakthrough, we’ve found a crack in the foundation of computability. But constructing diagonalization arguments from scratch for every new problem is tedious and difficult.

To explore the landscape of undecidable problems further, we need a scalable tool. That tool is Reduction.

The Core Intuition

Reduction is a method of converting one problem into another. It’s a concept you use constantly in programming: “I don’t want to write a sorting algorithm from scratch; I’ll just transform my data into a list and call the standard library’s .sort() function.”

In theoretical computer science, we use this logic in reverse to prove hardness:

“If I had a machine that could solve Problem B, I could easily use it to solve Problem A. But I already know Problem A is impossible to solve. Therefore, the machine for Problem B cannot exist.”

This implies that Problem B is at least as hard as Problem A.

Recursive Reduction (${\le }_R$)

The most general form of this idea is Recursive Reduction.

Imagine we have two languages, $L_1$ and $L_2$. We want to know if we can solve $L_1$. We don’t know how, but let’s pretend we have a magic “Black Box” (or Oracle) for $L_2$. We don’t know how the Black Box works, but we know that if we feed it a string $y$, it instantly and correctly tells us whether $y\in L_2$.

Definition: We say $L_1$ is recursively reducible to $L_2$ (written $L_1{\le }_R{L}_2$) if we can construct a Turing Machine $M$ that decides $L_1$, provided $M$ is allowed to query the Oracle for $L_2$.

The Logic Chain:

1. We want to prove $L_{new}$ is undecidable.
2. We take a known undecidable problem, like $L_{diag}$.
3. We show $L_{diag}{\le }_R{L}_{new}$. (i.e., “If I could solve $L_{new}$, I could solve $L_{diag}$”).
4. Since solving $L_{diag}$ is impossible, solving $L_{new}$ must also be impossible.

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

While recursive reduction is powerful, we often use a stricter, more structured version called Many-One Reduction (or Input-to-Input Reduction). This is the standard tool for proving undecidability.

Instead of a general algorithm that can call the Oracle multiple times, we demand a simple translation. We want a function that translates instances of Problem A directly into instances of Problem B.

Definition: Language $L_1$ is Many-One reducible to $L_2$ (denoted $L_1{\le }_m{L}_2$) if there exists a computable function $f:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ such that for every input string $x$:

$$x\in L_1⟺f(x)\in L_2$$

What this means

• computable function: There is a Turing Machine that, given input $x$, halts and leaves just $f(x)$ on its tape. The translation process itself must be doable!
• $⟺$ condition: The translation must preserve the answer.
  • If $x$ is a “Yes” instance of $L_1$, then $f(x)$ must be a “Yes” instance of $L_2$.
  • If $x$ is a “No” instance of $L_1$, then $f(x)$ must be a “No” instance of $L_2$.

The Reduction Machine

If $L_1{\le }_m{L}_2$, and we had a hypothetical decider $M_2$ for $L_2$, we could build a decider $M_1$ for $L_1$ like this:

1. Input: $x$.
2. Run the translator: Compute $y=f(x)$.
3. Run the oracle: Run $M_2$ on input $y$.
4. Output: Return whatever $M_2$ returns.

Because $x\in L_1⟺y\in L_2$, this machine $M_1$ correctly decides $L_1$.

The Contradiction Strategy

To prove $L_{new}$ is undecidable:

1. Start with $L_{diag}$ (which we know is undecidable).
2. Construct a computable function $f$ that transforms any string $w$ into a string $f(w)$.
3. Prove that $w\in L_{diag}⟺f(w)\in L_{new}$.
4. This establishes $L_{diag}{\le }_m{L}_{new}$.
5. If $L_{new}$ were decidable, the machine described above would solve $L_{diag}$.
6. This is impossible. Therefore, $L_{new}$ is undecidable.

Lemma 5.3 (Connection)

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 we call the oracle exactly once at the very end and return its answer directly. For proving basic undecidability, this “simple” translation is almost always what we use.

This framework is the sledgehammer of theoretical computer science. Once we have $L_{diag}$, we never have to use diagonalization again. We just keep reducing: $L_{diag}{\le }_{m}H{\le }_m{L}_{universal}{\le }_m\dots$ Every problem in this chain inherits the “unsolvability” of the ones before it.