Season 1, Act V: Decidability & The Limits of Machines

Introduction

So far, we’ve met the giants. Gödel showed us that math is incomplete. Church and Turing gave us two different, yet equivalent, definitions of what is computable. They drew a line in the sand, defining the absolute boundaries of what algorithms can ever solve.

This leads to a crucial question: If we have a problem, how do we know if it’s solvable by an algorithm? This is the idea of decidability.

A problem is decidable if there exists an algorithm (a Turing machine) that, for any possible input, is guaranteed to finish and give a clear “yes” or “no” answer.

• Decidable Problem: “Is this number even?” You can easily write an algorithm that takes any number, divides it by two, checks for a remainder, and halts with a “yes” or “no.”
• Undecidable Problem: A problem for which no such “always-halts” algorithm can ever be created.

It seems abstract, but Alan Turing discovered the most famous undecidable problem of all, and it lies at the very heart of programming.

The Ultimate Bug-Checker: The Halting Problem

Every programmer has accidentally written an infinite loop. The program gets stuck, running forever, and never produces an answer.

Turing asked a simple question: Can we write a program that can look at any other program and its input, and tell us if it will ever stop (halt) or if it will run forever?

Let’s call this hypothetical program HaltsChecker. It would be the ultimate debugging tool. You’d feed it any program and its potential input, and it would spit out a simple TRUE (it will halt) or FALSE (it will run forever).

HaltsChecker(program, input) -> TRUE or FALSE

Turing proved, with devastating logic, that creating HaltsChecker is impossible.

The Proof is a Paradox

Turing’s proof is a beautiful piece of logic that works by contradiction. It goes like this:

1. Assume the Impossible: Let’s pretend for a moment that some genius did manage to create HaltsChecker. It exists, and it works perfectly.

2. Build a Troublemaker: Now, using HaltsChecker as a component, we’re going to build a new, mischievous program. Let’s call it Paradox. Paradox takes another program’s code as its only input. Here’s what it does:

   • It uses HaltsChecker to analyze the input program. Specifically, it asks HaltsChecker: “What would happen if this program were run with itself as its own input?”
   • Based on the answer, Paradox does the exact opposite:
     • If HaltsChecker says, “Yes, that program will halt,” then Paradox intentionally throws itself into an infinite loop.
     • If HaltsChecker says, “No, that program will run forever,” then Paradox immediately halts and prints “Done.”

3. Ask the Killer Question: Now for the moment that breaks logic. What happens if we feed the Paradox program to itself? What is the result of Paradox(Paradox)?

   Let’s trace the logic:

   • The Paradox program starts running. Its first step is to use HaltsChecker to analyze its own code. It asks: “Will Paradox halt when given Paradox as input?”
   • Scenario A: HaltsChecker answers “Yes, it will halt.” If this is the answer, then the Paradox program, following its rules, must do the opposite and enter an infinite loop. But that means the original answer was wrong.
   • Scenario B: HaltsChecker answers “No, it will run forever.” If this is the answer, then the Paradox program, following its rules, must do the opposite and immediately halt. But that also means the original answer was wrong.

We have a logical impossibility - a contradiction. The Paradox program cannot exist. And since the only magical ingredient we used to build it was HaltsChecker, our initial assumption must be false.

No program can ever exist that can solve the Halting Problem. It is fundamentally, provably undecidable.

This discovery wasn’t just a party trick for logicians. It established that there are concrete, important problems that computers will never be able to solve, no matter how powerful they become. It’s a permanent wall, a hard limit on the power of computation.

With these theoretical limits established, our story now pivots. The focus shifts from pure logic to the physical world. How do we actually represent and manipulate information? The answer would come from a man named Claude Shannon, who was about to invent the future.