The halting problem: why it is undecidable

It would be handy to have a tool that, given any program and an input for it, tells us whether the program eventually finishes or loops forever. Such a tool would automatically find every infinite loop, and much more. The halting problem asks exactly this, and the theory's answer is blunt: such an algorithm cannot exist. Not for lack of computing power, but because of a logical contradiction.

The precise formulation

The halting language is:

HALT_TM = {⟨M, w⟩ : M is a Turing machine that halts on input w}

Closely related is the acceptance language:

A_TM = {⟨M, w⟩ : M accepts w}

The theorem states that both are undecidable: there is no Turing machine that, on every input ⟨M, w⟩, always halts and answers correctly. Both are, however, recognizable: just simulate M on w with the universal machine and wait.

The proof for A_TM

We first prove that A_TM is undecidable, by contradiction.

Suppose there is a decider H such that:

• H(⟨M, w⟩) accepts if M accepts w;
• H(⟨M, w⟩) rejects if M does not accept w (because it rejects or because it never halts).

H always halts, by assumption.

Build a new machine D that takes as input the description ⟨M⟩ of a machine:

1. it runs H on the input ⟨M, ⟨M⟩⟩, asking whether M accepts its own description;
2. if H accepts, D rejects;
3. if H rejects, D accepts.

D always halts, because H always halts. It does the opposite of what M would do on itself.

Now give D its own description, ⟨D⟩:

• if D accepts ⟨D⟩, then H(⟨D, ⟨D⟩⟩) accepted, so by construction D rejects ⟨D⟩;
• if D rejects ⟨D⟩, then H(⟨D, ⟨D⟩⟩) rejected, so by construction D accepts ⟨D⟩.

Either way we get a contradiction. So H cannot exist, and A_TM is undecidable.

Why it is called diagonalization

Picture an infinite table. The rows are all Turing machines M₁, M₂, M₃, …, which we know are countable. The columns are their descriptions ⟨M₁⟩, ⟨M₂⟩, ⟨M₃⟩, … In cell (i, j) we write "accepts" if Mᵢ accepts ⟨Mⱼ⟩, otherwise "does not accept".

Machine D is built to behave, on column i, opposite to what the diagonal cell (i, i) says. So D differs from every machine Mᵢ on at least one input, ⟨Mᵢ⟩. But D is a Turing machine, so it should appear in some row: contradiction. It is the same pattern used to prove that the real numbers are uncountable.

From acceptance to halting

Now we show that HALT_TM is undecidable too, with a reduction. Suppose there were a decider R for HALT_TM. Then we could decide A_TM like this, on input ⟨M, w⟩:

1. run R on ⟨M, w⟩;
2. if R says M does not halt on w, reject: M certainly does not accept;
3. if R says M halts, simulate M on w, knowing the simulation will end, and answer as M does.

We would have a decider for A_TM, which does not exist. So R does not exist.

A language that is not even recognizable

A language is decidable if and only if both it and its complement are recognizable: run the two recognizers in parallel and wait for one of them to accept. Since A_TM is recognizable but not decidable, its complement is not even recognizable. So there are problems for which we cannot even guarantee to confirm all the positive answers.

What it really means, and what it does not

Undecidability is often misunderstood. A few clarifications:

• It does not mean we cannot know whether a specific program halts. For a great many concrete programs this is easy to prove.
• It means there is no single algorithm that gives the right answer for every program.
• Real static analysis tools work around the limit honestly: they answer "halts", "does not halt" or "don't know", or they restrict the language analysed, or they accept false alarms.
• A timeout does not solve the problem: if a program has not finished yet, we do not know whether it will finish in a second or never.

In my work this limit shows up clearly when analysing suspicious code: no tool can establish with certainty, in every case, what a program will do on all inputs. So we rely on a combination of static analysis, controlled execution and human judgement.

In short

• The halting problem asks whether a machine halts on an input; no algorithm decides it in every case.
• The proof builds a machine D that contradicts itself when given its own description.
• It is a diagonalization argument, the same one that shows the reals are uncountable.
• A_TM and HALT_TM are recognizable but not decidable; their complements are not even recognizable.
• Undecidability concerns a universal algorithm, not individual programs.