The Halting Problem and Computability

One of the most profound results in the whole of Computer Science is that there exist problems which no computer can ever solve — not because our machines are too slow or our memory too small, but because no algorithm to solve them can possibly exist. The flagship example is the halting problem, which Alan Turing proved undecidable in 1936, in the very same paper that introduced the Turing machine. This lesson lays out the halting problem carefully, walks through Turing's proof-by-contradiction in an accessible but rigorous form, and draws the sharp distinction between problems that are merely hard and problems that are genuinely impossible. The result is humbling: it tells us that the dream of a perfect, fully automatic program-analyser — one that could decide for any program whether it will crash, loop, or behave correctly — is not just difficult but provably unattainable.

---

Spec Mapping

This lesson addresses the Theory of Computation strand of the AQA A-Level Computer Science specification (7517), in the area concerned with a model of computation and its limits (around section 4.4.5). You are expected to understand the halting problem — its precise statement, and the idea that it is undecidable; to follow and reproduce, in an accessible form, the proof by contradiction that no algorithm can solve it; to distinguish computable from non-computable problems and functions, and decidable from undecidable problems; and to appreciate the consequences of undecidability for real software (perfect debuggers, virus scanners and verifiers are impossible in general). The treatment below is descriptive and conceptual rather than a verbatim quotation of the specification.

---

Computable and Non-Computable: the Central Distinction

Before the halting problem itself, we need the vocabulary precisely.

Classification	Definition	Example
Decidable problem	A yes/no problem for which there is an algorithm (equivalently, a Turing machine) that, on every possible input, halts and gives the correct answer	"Is this whole number prime?"
Undecidable problem	A yes/no problem for which no such algorithm exists — for any proposed algorithm there are inputs on which it gives a wrong answer or never halts	The halting problem
Computable function	A function for which an algorithm exists that computes its output for every input and always halts	$f(n) = n^2$f(n)=n2; the greatest common divisor of two numbers
Non-computable function	A function for which no algorithm can produce the correct output for all inputs	The function that, given a program, returns 1 if it halts and 0 otherwise

The phrase "an algorithm exists" is made exact by the Church-Turing thesis from the previous lesson: it means precisely "a Turing machine exists". So when we prove that no Turing machine can solve the halting problem, we have proved that no algorithm whatsoever can — on any present or future hardware. A decidable problem is one whose algorithm has two guarantees: it always halts, and it always gives the right answer. Drop either guarantee and the problem may slip into undecidability. The halting problem will turn out to fail the first guarantee in an unavoidable way.

It is worth stressing at the outset what undecidable does not mean. It does not mean "we have not found an algorithm yet"; it means we have proved that none can exist. And it does not mean "no instance can be answered" — for plenty of individual programs we can easily see whether they halt. What is impossible is a single general method that works for every program-and-input pair.

---

The Halting Problem

Statement

Given a description of a program $P$P and an input $I$I for it, decide whether $P$P will eventually halt (terminate) when run on $I$I, or whether it will run forever.

Phrased as a demand for an algorithm: does there exist an algorithm $H$H such that, for every program $P$P and every input $I$I,

• $H(P, I)$H(P,I) returns "halts" if $P$P halts on input $I$I, and
• $H(P, I)$H(P,I) returns "loops" if $P$P runs forever on input $I$I,

with $H$H itself always terminating and giving the correct verdict? The crucial subtlety is that $H$H must answer for all programs and inputs, and must do so without simply running $P$P — because if $P$P loops forever, naively running it would mean $H$H never returns, and then $H$H would not be the always-halting decider we require. Turing's theorem is that no such $H$H exists.

Why "just run it and see" does not work

The tempting amateur answer is: "to find out whether $P$P halts on $I$I, simply run $P$P on $I$I and watch." This semi-works in one direction only. If $P$P does halt, then running it will eventually reveal that — after some finite number of steps it stops, and we can report "halts". But if $P$P runs forever, watching it never lets us conclude "loops": at every moment we have only seen finitely many steps, and we can never be sure it will not halt on the very next one. There is no point at which "it has not halted yet" becomes "it will never halt". So "run and watch" is not a decider — it fails to halt precisely on the looping inputs, which are exactly the ones where we needed a definite "loops" answer.

---

Turing's Proof by Contradiction

Turing proved that no decider $H$H can exist using a proof by contradiction built on a self-reference / diagonalisation trick. The argument is short, and worth following slowly because it is a classic examined topic.

Step 1 — Assume the decider exists. Suppose, for contradiction, that an always-halting algorithm $H(P, I)$H(P,I) exists that correctly answers "halts" or "loops" for every program $P$P and input $I$I.

Step 2 — Build a deliberately contrary program $D$D. Using $H$H as a building block, construct a new program $D$D that takes a single program $P$P as its input and does the opposite of what $H$H predicts about $P$P run on itself:

PROGRAM D(P):
    IF H(P, P) = "halts" THEN
        loop forever            # if H says P(P) halts, D deliberately loops
    ELSE
        halt                    # if H says P(P) loops, D deliberately halts
ENDPROGRAM

Here H(P, P) asks the perfectly legitimate question "does program $P$P halt when given its own description as input?". Since $H$H is assumed to decide every program-input pair, it certainly decides this one, so $D$D is a well-defined program: it always consults $H$H (which always halts) and then either loops or halts accordingly.

Step 3 — Feed $D$D its own description. Now ask the fatal question: what does $D$D do when run on $D$D itself — that is, what is the behaviour of D(D)? Inside that call, the test evaluated is H(D, D), which by definition reports whether D(D) halts. There are only two possibilities, and we examine each.

Suppose $H$H reports...	Then by $D$D's code, $D(D)$D(D) actually...	But $H$H had claimed $D(D)$D(D)...	Result
H(D, D) = "halts"	enters the infinite loop → does not halt	halts	Contradiction
H(D, D) = "loops"	takes the halt branch → halts	loops	Contradiction

Step 4 — Conclude. In both cases $D(D)$D(D) does the exact opposite of what $H$H predicted, so $H$H is wrong about D(D) — contradicting the assumption that $H$H is always correct. The only assumption we made was that $H$H exists, so that assumption must be false. Therefore no algorithm $H$H that decides the halting problem can exist; the halting problem is undecidable. $\blacksquare$■

The heart of the trick is self-reference: by letting a program operate on its own description, we engineer a question that any supposed all-knowing decider must get wrong. It is the computational cousin of the liar paradox ("this sentence is false") and of Cantor's diagonal argument that the real numbers are uncountable — the same logical machine, applied to programs.

---

A Worked Reduction: Proving Another Problem Undecidable

Once the halting problem is known to be undecidable, we rarely repeat the diagonalisation from scratch. Instead we use reduction: to show a new problem $X$X is undecidable, we assume an algorithm for $X$X exists and show it could be used to build a halting-problem decider — which we know is impossible, so the algorithm for $X$X cannot exist either. The schematic is always the same:

1. Assume $X$X is decidable — some algorithm $A_X$AX​ solves it.
2. Show how to use $A_X$AX​ as a component to construct a decider for the halting problem.
3. Since the halting problem has no decider, $A_X$AX​ cannot exist.
4. Conclude $X$X is undecidable.

Worked example: the "does it ever produce output?" problem

Problem $X$X: given any program $P$P and input $I$I, decide whether $P$P ever produces any output when run on $I$I.

Assume an algorithm $A_X(P, I)$AX​(P,I) exists that returns "yes" if $P$P produces output on $I$I and "no" otherwise, always halting. We use it to solve the halting problem as follows. Given an arbitrary program $P$P and input $I$I whose halting we wish to decide, construct a modified program $P'$P′ that behaves exactly like $P$P but is silent throughout — it produces no output at all — except that, immediately before $P$P would terminate, $P'$P′ prints a single character, say "done":

PROGRAM P'(I):
    run the body of P on I, suppressing any output it would make
    # control only reaches the next line if P halts
    print "done"
ENDPROGRAM

Now run $A_X(P', I)$AX​(P′,I). Because $P'$P′ produces output only if and when $P$P halts:

• if $A_X$AX​ says "yes" (output is produced), then $P$P must have halted on $I$I;
• if $A_X$AX​ says "no" (no output ever), then $P$P never reached the print, i.e. $P$P runs forever on $I$I.

So $A_X$AX​ would let us decide whether $P$P halts on $I$I — a halting-problem decider. Since none can exist, our assumed $A_X$AX​ cannot exist either, and "does it ever produce output?" is undecidable. This reduction pattern — wrap the unknown program so that some easy-to-test event happens exactly when it halts — is the workhorse for proving undecidability, and a manageable version of it is a realistic exam task.

A Second Reduction: the "Prints Hello" Problem

It is worth seeing the same technique applied once more, because recognising the pattern is what makes reduction questions approachable. Problem $Y$Y: given any program $P$P, decide whether $P$P (run on empty input) ever prints the exact string "hello". Assume a decider $A_Y$AY​ exists. Given an arbitrary program $P$P and input $I$I whose halting we want to decide, build a wrapper $P''$P′′ that ignores its own input, runs $P$P on $I$I with all of $P$P's normal output suppressed, and — only if $P$P halts — prints "hello" and stops:

PROGRAM P''():
    run the body of P on I, suppressing all of P's output
    # reached only if P halts
    print "hello"
ENDPROGRAM

Then $P''$P′′ prints "hello" exactly when $P$P halts on $I$I. Running $A_Y(P'')$AY​(P′′) therefore decides the halting problem — impossible — so $A_Y$AY​ cannot exist and "does it ever print hello?" is undecidable. The mechanics are identical to the previous reduction; only the "easy-to-spot event" has changed (from any output to a specific string). Once you see that any observable behaviour can be rigged to coincide with halting, it becomes intuitive why essentially every behavioural question is undecidable — which is precisely what Rice's theorem, next, asserts in full generality.

"Undecidable" versus "Decidable but Astronomically Hard"

A subtle distinction sharpens understanding here. Undecidability is about whether an algorithm exists at all, not about how long an algorithm takes. Consider the question "does this program halt within one million steps on this input?" — superficially close to the halting problem. This bounded version is perfectly decidable: simply simulate the program for up to a million steps and report whether it stopped. The simulation always terminates (after at most a million steps), so an algorithm exists. The unbounded halting problem is undecidable precisely because removing the step limit removes the guaranteed stopping point of any "simulate and watch" approach. The general lesson is that adding a finite bound to a resource (steps, memory, time) very often turns an undecidable question into a decidable — though possibly intractable — one. Keeping this straight prevents the common error of assuming any halting-flavoured question must be undecidable: it is specifically the unbounded, all-inputs version that is impossible.

---

Rice's Theorem: Undecidability Is the Rule, Not the Exception

The previous reduction is not a lucky one-off. Rice's theorem generalises the situation dramatically:

Any non-trivial property of the function (the input-output behaviour) computed by a program is undecidable.

"Non-trivial" means simply that the property is true of some programs and false of others (a property true of every program, or of none, is trivially decidable). So essentially every interesting semantic question you might ask about what an arbitrary program does is undecidable in general:

• Does this program ever output the string "hello"?
• Does this program always return a positive number?
• Does this program ever attempt to access the network?
• Are these two programs functionally equivalent (same output on every input)?

Key insight: We can always determine such a property for a specific program by analysis or by running it. What is impossible is a single general algorithm that correctly answers the question for every possible program. The undecidability is about the demand for universality, not about any individual case.

Rice's theorem reframes our whole intuition: undecidability is not a rare pathology lurking only in a contrived halting question — it is the default status of questions about program behaviour. Decidable behavioural questions are the exceptions.

---

Decidable, Recognisable, and the Status of the Halting Problem

Turing machines let us refine "solvable" into finer grades, and the halting problem sits revealingly between them.