The Halting Problem: Undecidability Proof

What Is the Halting Problem?

From a practical standpoint, you've likely encountered a version of the Halting Problem in your own coding experience. Have you ever written a program that accidentally fell into an infinite loop? Debugging such issues can be tricky. It raises a natural question: couldn't we build a perfect debugging tool, a program that analyzes any other program and its input, and tells us definitively whether it will run forever or eventually halt?

This is the essence of the Halting Problem. To discuss it formally, we define it as a language.

The Acceptance Problem for Turing Machines, denoted $A_{TM}$, is the language:
$A_{TM}=\{⟨M,w⟩\mid M\text{ is a Turing Machine and }M\text{ accepts string }w\}$

This language represents the set of all pairs of a TM and a string where the TM accepts that string.

Why is this the "Halting Problem"?
A machine that decides $A_{TM}$ would have to halt on all inputs.

• If $M$ accepts $w$, the decider would halt and accept.
• If $M$ rejects $w$, the decider would halt and reject.
• If $M$ loops on $w$, the decider must still halt and reject.

Therefore, a decider for $A_{TM}$ would need to be able to detect infinite loops. Solving the decision problem for $A_{TM}$ is equivalent to solving the Halting Problem.

In a previous lesson, we established that $A_{TM}$ is Turing-recognizable. We can build a Universal Turing Machine (UTM) that simulates $M$ on $w$. If $M$ accepts, the UTM accepts. The catch is that if $M$ loops, the UTM also loops, which is why it's only a recognizer, not a decider. The question we will answer today is whether a true decider can exist.

The following short video provides an excellent, intuitive introduction to the problem and the logic of its proof.

Proving the Undecidability of $A_{TM}$

As the video showed, the proof that $A_{TM}$ is undecidable is a proof by contradiction that uses the diagonalization argument you are now familiar with.

The Strategy

1. Assume that $A_{TM}$ is decidable.
2. This assumption means there must exist a Turing Machine—let's call it $H$—that always halts and correctly decides $A_{TM}$.
3. Construct a new, paradoxical Turing Machine—let's call it $D$—that uses $H$ as a subroutine.
4. Show that when $D$ is run on its own description, its behavior leads to a logical contradiction.
5. Conclude that our initial assumption must be false, meaning no such decider $H$ can exist. Therefore, $A_{TM}$ is undecidable.

The following video from MIT OpenCourseWare features Professor Michael Sipser (author of a key textbook in this field) presenting the formal proof.

Deconstructing the Proof

Let's summarize the key steps from the video with our formal notation.

Step 1: Assume a Decider $H$ Exists
We begin by assuming $A_{TM}$ is decidable. This implies the existence of a TM, $H$, that is a decider for $A_{TM}$. Its behavior is defined as:

The crucial property of $H$ is that it always halts.

Step 2: Construct the Diagonal Machine $D$
Now we build a new TM, $D$, which uses $H$ as a subroutine.
The machine $D$ takes as input the encoding of a single TM, $⟨M⟩$.

Here is the specification for $D$:
On input $⟨M⟩$:

1. Run the decider $H$ on the input $⟨M,⟨M⟩⟩$. This step involves feeding a machine its own description as input. This might seem strange, but it's a valid operation—for instance, a C compiler (a program) written in C can compile its own source code (its description).
2. Act on $H$'s output:
   • If $H$ accepts, then $D$ rejects.
   • If $H$ rejects, then $D$ accepts.

In short, $D$ accepts $⟨M⟩$ if and only if $M$ does not accept $⟨M⟩$. $D$ does the opposite of whatever the machine on the diagonal does.

Step 3: The Contradiction
Since $D$ is a Turing Machine, it must have its own encoding, $⟨D⟩$. What happens when we feed $⟨D⟩$ as input to $D$ itself?

Let's analyze $D(⟨D⟩)$:

• Case 1: Assume $D$ accepts $⟨D⟩$.
  Looking at the definition of $D$, it only accepts its input ($⟨D⟩$) if the subroutine $H$ rejected on the input $⟨D,⟨D⟩⟩$. According to the definition of $H$, this means that $D$ does not accept $⟨D⟩$.
  This leads to: $D$ accepts $⟨D⟩⟹D$ does not accept $⟨D⟩$. A contradiction.

• Case 2: Assume $D$ does not accept $⟨D⟩$.
  Again, by $D$'s definition, it would only reject its input ($⟨D⟩$) if the subroutine $H$ accepted on the input $⟨D,⟨D⟩⟩$. According to $H$, this means that $D$ does accept $⟨D⟩$.
  This leads to: $D$ does not accept $⟨D⟩⟹D$ accepts $⟨D⟩$. Another contradiction.

Both possibilities result in a logical impossibility. The only thing we assumed was the existence of the decider $H$. Therefore, that assumption must be false.

For a formal, written version of this argument, the following notes are an excellent resource.

Conclusion

Today, we have formally proven that no algorithm can ever exist that solves the Halting Problem for all possible program-input pairs. This is not a limitation of our current technology or programming languages; it is a fundamental, mathematical limit on what computation can achieve.

Key Takeaways:

• The Halting Problem (formalized as the language $A_{TM}$) asks whether a given Turing Machine will accept a given string.
• $A_{TM}$ is Turing-recognizable, but it is undecidable.
• The proof of undecidability is a classic proof by contradiction that uses diagonalization. It assumes a decider $H$ exists, then constructs a paradoxical machine $D$ that does the opposite of what $H$ predicts about $D$'s behavior on its own code, leading to an inescapable contradiction.

Preview of the Next Lesson:
Now that we have established our first, canonical undecidable problem ($A_{TM}$), we have a powerful foothold. We no longer need to construct intricate diagonalization proofs from scratch every time. In the next lesson, we will learn about mapping reducibility, a technique for proving that other problems are undecidable by showing that they are "at least as hard as" the Halting Problem. This will allow us to quickly prove the undecidability of a wide range of other problems about Turing Machines.