Undecidability through Reductions from the Halting Problem

The Proof Template Revisited

Let's quickly review the structure of a proof by reduction. To prove a language $P$ is undecidable, we follow these steps:

1. Assume (for contradiction) that $P$ is decidable by some Turing Machine, let's call it $R$.
2. Goal: Use $R$ as a subroutine to construct a decider, let's call it $S$, for the known undecidable language $A_{TM}$.
3. Construction: The decider $S$ takes an input $⟨M,w⟩$ for $A_{TM}$. Its key step is to define an algorithm that transforms $⟨M,w⟩$ into a new string $⟨M^{\prime }⟩$ that is a valid input for our hypothetical decider $R$.
4. Logic: The machine $M^{\prime }$ is specially constructed so that its properties, which $R$ can decide, are linked to the outcome of $M$ on $w$. Specifically:
   $⟨M,w⟩\in A_{TM}⟺⟨M^{\prime }⟩\in P$
5. Execution: $S$ runs $R$ on $⟨M^{\prime }⟩$. If $R$ accepts, $S$ accepts. If $R$ rejects, $S$ rejects.
6. Contradiction: Because $S$ correctly decides the undecidable language $A_{TM}$, we have a contradiction. Therefore, our initial assumption that the decider $R$ for problem $P$ exists must be false.

A common point of confusion is keeping track of the different machines involved. The following document makes this crystal clear.

The key insight is that the reduction itself is a constructor algorithm. Your experience designing APIs and data pipelines is analogous here: the reduction is a function that takes a description of one computational process ($M$ on $w$) and generates the description of a new, related computational process ($M^{\prime }$).

Example 1: The Emptiness Problem ($E_{TM}$)

Let's start with a classic undecidable problem: determining if a Turing Machine's language is empty.

The language is defined as:
$E_{TM}=\{⟨M⟩\mid M\text{ is a TM and }L(M)=\varnothing \}$

We will prove $E_{TM}$ is undecidable by reducing $A_{TM}$ to it. More precisely, it's often easier to reduce $A_{TM}$ to the complement, $\overline{E_{TM}}$, which is the language of TMs that accept at least one string. Since a language is decidable if and only if its complement is, proving $\overline{E_{TM}}$ is undecidable is sufficient.

The following video provides an excellent, detailed walkthrough of this proof. The construction used is a classic "input-filtering" technique.

Let's summarize the construction from the video.

Proof that $E_{TM}$ is undecidable:
Assume $E_{TM}$ is decidable by a TM, R. We will construct a decider S for $A_{TM}$.

On input $⟨M,w⟩$, S does the following:

1. Construct the description of a new TM, $M^{\prime }$. This $M^{\prime }$ is designed as follows:
   On input $x$:
   a. If $x\ne w$, reject.
   b. If $x=w$, run the original machine $M$ on the input $w$. Accept if $M$ accepts; reject if $M$ rejects.
2. Run the hypothetical decider R on $⟨M^{\prime }⟩$.
3. If R rejects (meaning $L(M^{\prime })$ is not empty), then S accepts.
4. If R accepts (meaning $L(M^{\prime })$ is empty), then S rejects.

Proof of Correctness:
Let's analyze the language of $M^{\prime }$:

• If $M$ accepts $w$: The only input $M^{\prime }$ doesn't immediately reject is $w$. When given $w$, $M^{\prime }$ runs $M$ on $w$ and accepts. Therefore, $L(M^{\prime })=\{w\}$. This language is not empty.
• If $M$ does not accept $w$ (it rejects or loops): $M^{\prime }$ will never accept any input. If the input is not $w$, it rejects. If the input is $w$, it simulates $M$ on $w$ and also never accepts. Therefore, $L(M^{\prime })=\varnothing$. This language is empty.

So, we have the crucial connection:
$M\text{ accepts }w⟺L(M^{\prime })\ne \varnothing$
$⟨M,w⟩\in A_{TM}⟺⟨M^{\prime }⟩\in \overline{E_{TM}}$

Our decider S uses R to check if $L(M^{\prime })$ is empty and inverts the answer, correctly deciding if $⟨M,w⟩\in A_{TM}$. This is a contradiction, so $E_{TM}$ is undecidable.

Example 2: The Regularity Problem ($REGULA{R}_{TM}$)

Let's tackle a more complex property. Is the language of a given TM regular?

The language is:
$REGULA{R}_{TM}=\{⟨M⟩\mid M\text{ is a TM and }L(M)\text{ is a regular language}\}$

The proof strategy is the same, but the machine we construct must be more clever. We need to design an $M^{\prime }$ whose language is regular if $M$ does not accept $w$, and non-regular if it does.

The following resource provides a concise, visual walkthrough of this proof.

Proof that $REGULA{R}_{TM}$ is undecidable:
Assume $REGULA{R}_{TM}$ is decidable by a TM, R. We build a decider S for $A_{TM}$.

On input $⟨M,w⟩$, S does the following:

1. Construct the description of a new TM, $M^{\prime }$.
   On input $x$:
   a. First, run the original machine $M$ on the input $w$.
   b. If $M$ accepts $w$, then proceed to check if the input $x$ has the form $0^n{1}^n$ for $n\ge 0$. If it does, accept $x$. Otherwise, reject.
   c. If $M$ does not accept $w$, $M^{\prime }$ immediately rejects $x$ (or simply never proceeds past step 1a).
2. Run the hypothetical decider R on $⟨M^{\prime }⟩$.
3. If R accepts (meaning $L(M^{\prime })$ is regular), then S rejects.
4. If R rejects (meaning $L(M^{\prime })$ is not regular), then S accepts.

Proof of Correctness:
Let's analyze the language of $M^{\prime }$:

• If $M$ accepts $w$: The check in step 1a passes. $M^{\prime }$ then proceeds to accept any string of the form $0^n{1}^n$. Therefore, $L(M^{\prime })=\{0^n{1}^n\mid n\ge 0\}$. We know from the Pumping Lemma that this language is not regular.
• If $M$ does not accept $w$ (it rejects or loops): The simulation in step 1a never finishes with an "accept". Thus, $M^{\prime }$ never accepts any input $x$. Therefore, $L(M^{\prime })=\varnothing$. The empty language is regular.

The logic holds:
$M\text{ accepts }w⟺L(M^{\prime })\text{ is not regular}$
$⟨M,w⟩\in A_{TM}⟺⟨M^{\prime }⟩\notin REGULA{R}_{TM}$
Our decider S inverts the answer from R to decide $A_{TM}$, leading to a contradiction. We conclude that $REGULA{R}_{TM}$ is undecidable.

Conclusion

Today we've seen how the single undecidable problem we proved from scratch, $A_{TM}$, can be used as a foundation to prove that a whole class of other problems are also undecidable. By mastering the art of constructing a new machine $M^{\prime }$ whose properties are tied to the behavior of $⟨M,w⟩$, we can systematically show the limits of computation.

Key Takeaways:

• Reductions from $A_{TM}$ are a versatile tool for proving other TM-related problems undecidable.
• The core of the proof is designing a constructor algorithm that builds a new TM, $M^{\prime }$, from the input $⟨M,w⟩$.
• The language of $M^{\prime }$ must have a specific property (e.g., being empty, regular, etc.) if and only if $M$ accepts $w$.
• Common construction techniques include input filtering (where $M^{\prime }$ only cares about one specific input) and input ignoring (where $M^{\prime }$'s behavior is completely independent of its own input).

Preview of the Next Lesson:
The patterns we've seen today—proving that non-trivial properties of a TM's language are undecidable—are not a coincidence. They are instances of a powerful generalization called Rice's Theorem, which we will explore next. After that, we will look at undecidable problems that don't directly involve Turing Machines, such as the Post's Correspondence Problem (PCP), to see how far these limitations on computation extend.