The halting problem.

Step 1 of 6

Halts or not

The adder and the busy beaver halt. But not every machine halts: Program is set to Ping-pong, which steps right, back, right, back.

Step 2 of 6

A proof that it never halts

How do you know a machine will not halt? Waiting does not help: after any number of steps it might halt on the next. You need a reason.

A machine’s picture is its state, the position of its head and everything written on the tape. The next step depends only on the picture and the card. Move Steps run and compare pictures.

Step 3 of 6

A machine that has halted

On the Busy beaver, Steps run stands at 500, but a machine that has halted takes no more steps.

Step 4 of 6

A halt checker

Suppose someone built H, a halt checker: it takes a rule card and always, after finite time, says correctly whether that machine will halt. Move Look inside to Halt checker: the sealed cabinet takes a copy of the card and lights HALTS or RUNS FOREVER. On the four cards here it is right.

Step 5 of 6

Turing’s argument

Turing showed that such an H cannot exist. Move Look inside to No checker: on the glass board a new machine, D, is built from H. D takes a rule card, asks H what that machine will do when fed its own card, and does exactly the opposite. Then D is given D’s card.

Step 6 of 6

What it means

This is the halting problem: no algorithm decides, for every program, whether it will halt. It is not a claim about today’s computers: it holds for any machine that follows exact steps, because every computer can be imitated by a Turing machine. Many more questions follow that no algorithm answers, for example whether two programs always do the same thing.