Computability and the Halting Problem

Computers seem able to do almost anything, but in 1936 a 23-year-old mathematician named Alan Turing proved that some problems can never be solved by any computer, no matter how fast. His most famous example, the halting problem, asks whether a program will eventually stop. This article tells the story behind that discovery and walks through the proof carefully, with examples you can try yourself.

The Question That Started It All

In 1928 the German mathematician David Hilbert, with Wilhelm Ackermann, posed the Entscheidungsproblem ("decision problem"): is there a mechanical procedure that can decide, for any statement in formal logic, whether it is provable? Hilbert hoped the answer was yes, which would make mathematics, in principle, fully mechanical.

To answer "no", someone first had to define precisely what a "mechanical procedure" is. Two people did so independently in 1936:

• Alonzo Church at Princeton, using his lambda calculus.
• Alan Turing at Cambridge, using imaginary devices now called Turing machines, in his paper "On Computable Numbers, with an Application to the Entscheidungsproblem".

Both showed the answer to Hilbert's question is no. Turing later went to Princeton to complete his PhD under Church.

Turing Machines

A Turing machine is a remarkably simple model:

• An infinite tape divided into cells, each holding a symbol.
• A head that reads and writes one cell and moves left or right.
• A finite set of states and a table of rules: "in state \( q \), reading symbol \( s \), write \( s' \), move left or right, go to state \( q' \)".

Despite its simplicity, a Turing machine can carry out any algorithm a modern computer can. Turing also described a universal machine that reads the description of any other machine from its tape and simulates it, the theoretical blueprint of the stored-program computer.

The Church-Turing Thesis

Lambda calculus and Turing machines turned out to compute exactly the same functions. This led to the Church-Turing thesis: anything that can be computed by an effective step-by-step procedure can be computed by a Turing machine. It is a thesis rather than a theorem, because "effective procedure" is an informal idea, but no counterexample has ever been found. Every programming language you know, from Python to C++, is equivalent in power to a Turing machine.

The Halting Problem

The halting problem asks:

Is there a program \( H \) that, given any program \( P \) and input \( x \), always correctly answers "yes, \( P \) halts on \( x \)" or "no, \( P \) runs forever"?

Testing by running the program does not work. If it halts, you see it; but if it has not halted after a million steps, it might stop after a billion.

Worked Example 1: Why Running Is Not Enough

Consider this simple program, based on the Collatz rule: start with a positive integer \( n \); if \( n \) is even, halve it; if odd, replace it with \( 3n + 1 \); stop when you reach 1.

Trace for \( n = 6 \):

$$ 6 \to 3 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1 $$

It halts after 8 steps.

Trace for \( n = 27 \): the sequence rises as high as 9232 before finally reaching 1 after 111 steps.

The lesson: nobody has ever proved that this program halts for every starting value. The Collatz conjecture, posed by Lothar Collatz in 1937, has been checked by computer for enormous numbers, yet remains unproven. A general halting-checker would settle it instantly, which hints at how powerful, and suspicious, such a checker would be.

Turing's Proof: Diagonalisation

Turing proved that no such \( H \) can exist. The proof is by contradiction and borrows Georg Cantor's diagonal argument from the 1890s.

Worked Example 2: The Proof Step by Step

Step 1. Assume a halting decider exists. Suppose \( H(P, x) \) always returns "halts" or "loops" correctly, and always finishes.

Step 2. Build a troublemaker program. Using \( H \), write a new program \( D \) that takes a program \( P \) as input:

D(P): if H(P, P) == "halts": loop forever else: halt

\( D \) asks what \( P \) does when given its own code as input, and then does the opposite.

Step 3. Feed \( D \) to itself. What does \( D(D) \) do?

• If \( D(D) \) halts, then \( H(D, D) \) says "halts", so by its own code \( D \) loops forever. Contradiction.
• If \( D(D) \) loops forever, then \( H(D, D) \) says "loops", so \( D \) halts. Contradiction.

Step 4. Conclude. Every possibility leads to a contradiction, so the assumption in Step 1 is false. No program can decide the halting problem for all programs and inputs. We say the halting problem is undecidable.

The Diagonal Picture

Imagine a table where row \( i \) is program \( P_i \), column \( j \) is input \( P_j \), and each entry says H (halts) or L (loops):

\( D \) is built to differ from every row on the diagonal: it loops where the diagonal says H and halts where it says L, giving L, H, L. So \( D \) cannot be any row of the table, yet the table lists every program. That is the contradiction, seen visually.

Reductions: Spreading Undecidability

Once one problem is known to be undecidable, others follow by reduction: show that solving the new problem would let you solve the halting problem.

Worked Example 3: Does a Program Ever Print "Hello"?

Suppose a tool \( Q \) could decide whether any program ever prints "Hello".

Step 1. Given any \( P \) and \( x \), build a new program \( P' \): "run \( P \) on \( x \) (with all its own output suppressed); when it finishes, print Hello".

Step 2. \( P' \) prints "Hello" exactly when \( P \) halts on \( x \).

Step 3. So \( Q(P') \) would answer the halting question for \( P \) and \( x \). Since that is impossible, \( Q \) cannot exist.

Rice's theorem, proved by Henry Gordon Rice around 1951, generalises this: every non-trivial question about what a program's output or behaviour is, as opposed to its code's appearance, is undecidable. This is why no antivirus or compiler can perfectly detect all malicious or buggy behaviour; they rely on approximations and heuristics.

Did You Know?

• The "Busy Beaver" function grows faster than any computable function. In 2024, an online collaboration called bbchallenge proved that the fifth busy beaver value is 47,176,870 steps, a result verified with the Coq proof assistant.
• Kurt Gödel's incompleteness theorems of 1931, which showed that some true statements cannot be proved, are closely related to the halting problem.

Key Takeaways

• Turing machines give a precise definition of "algorithm", and the Church-Turing thesis says they capture all effective computation.
• The halting problem asks whether a program will stop, and no algorithm can answer it for all programs.
• Turing's proof uses self-reference and Cantor's diagonal argument to reach a contradiction.
• Reductions spread undecidability to many other problems, as Rice's theorem shows.
• Real software tools therefore rely on approximations rather than perfect analysis.

If theory of computation proofs feel tricky, Amathify's subject experts and PhD scholars can provide step-by-step solutions and assignment help; just message us on WhatsApp or use the Ask a Question form.