Math Detours · Grade 12 · Around the corner · 22

The program that cannot exist

Suppose a program could decide whether any program halts. Feed it itself, twisted, and it contradicts itself. Turing's diagonal.

Name ____________________Date ____________

Tonight's idea

A program is a finite text. So is its input. Nothing stops you feeding one program the text of another; compilers do it all day. Some programs halt and some run forever. Could a clever enough program say, for every program \(P\) and input \(x\), whether \(P\) halts on \(x\)?

Suppose HALTS(P, x) does exactly that: it always finishes, saying "halts" or "loops". Then write this:

D(P): if HALTS(P, P) says "halts": loop forever else: stop

\(D\) asks what \(P\) does on its own text, then does the opposite. Run \(D\) on itself. If \(D(D)\) halts, HALTS(D, D) said "halts", so \(D\) looped. If \(D(D)\) loops, HALTS said "loops", so \(D\) stopped. Both branches contradict the answer HALTS was guaranteed to get right. The only way out: HALTS was never a program. This is the halting problem, proved by Alan Turing in 1936, before any electronic computer existed.

It is Cantor's diagonal in disguise (grade 10, b13). List every program \(P_1, P_2, \dots\) and record in row \(i\), column \(j\) whether \(P_i\) halts on input \(P_j\). The row for \(D\) is the diagonal, flipped. It differs from row \(i\) in column \(i\), for every \(i\), so \(D\) is not in the table. Yet every program has a row.

input program P₁P₂P₃P₄ P₁P₂P₃P₄ HLHH LLHL HHLH LHHH D LHHL flipped diagonal
H: halts, L: loops forever. Row \(D\) disagrees with row \(i\) in column \(i\), so it is no row of the table.

Watch one: a conjecture as a halting question

Goldbach's conjecture says every even number from 4 up is a sum of two primes. It is unproved (grade 8, b14). Write a program \(G\): for \(n = 4, 6, 8, \dots\), test whether \(n\) is a sum of two primes; if not, stop. \(G\) halts exactly when Goldbach is false, so one call to HALTS(G) would settle a centuries-old problem. The same works for any conjecture with a checkable counterexample. That one program would settle all of them at once is a hint it cannot exist. The diagonal is the proof.

Your turn

  1. Trace this program by hand. Does it halt, and after how many steps? n = 7; while n ≠ 1: if n is even, n = n/2, else n = 3n + 1.
  2. A program is allowed at most \(k\) bits of memory in total, including its place in the code. Show that it either halts within \(2^k\) steps or never halts. Halting is therefore decidable for such programs. Why does this not contradict Turing?
  3. Someone offers a weaker program, LOOPS(P, x), which prints "loops" whenever \(P\) runs forever on \(x\) and otherwise runs forever itself, saying nothing. Show that LOOPS would let you build HALTS, so LOOPS cannot exist either. Hint: run two things at once, one step each in turn.
  4. Show that no program EQUAL(P, Q) can decide whether two programs behave identically on every input. Hint: compare a suitable program with one that always loops, and make HALTS out of the answer.

Stretch: the busiest program

Among the finitely many programs of exactly \(n\) characters, some halt. Let \(\mathrm{BB}(n)\) be the largest number of steps any of them runs before halting. Show that no program can compute \(\mathrm{BB}(n)\) from \(n\).

Answers

  1. 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1: it halts after 16 steps. Whether it halts for every starting value is the Collatz problem, which is open; a halting decider would settle it.
  2. A state is the entire contents of memory, and there are at most \(2^k\) of them. A run of \(2^k\) steps visits \(2^k + 1\) states, so two coincide (pigeonhole, grade 10, b3). The program is deterministic, so from the repeated state it repeats the same loop forever. To decide, simulate \(2^k\) steps. No contradiction: the decider needs the \(k\) simulated bits plus a counter to \(2^k\), so it uses more than \(k\) bits and is not one of the programs it judges. Turing's argument needs HALTS to be a program of the same kind as \(D\), with no memory limit.
  3. Given \(P\) and \(x\), run \(P\) on \(x\) and LOOPS(P, x) alternately, one step each. If \(P\) halts, the first run finishes; if \(P\) loops, LOOPS eventually says so. Exactly one of these happens, and reporting it is HALTS. Since HALTS cannot exist, neither can a reliable LOOPS.
  4. Given \(P\) and \(x\), write a program \(P_x\) that ignores its input and runs \(P\) on \(x\). Let \(\mathrm{LOOP}\) be the program that always runs forever. EQUAL\((P_x, \mathrm{LOOP})\) says "same" exactly when \(P_x\) never produces an output, that is when \(P\) does not halt on \(x\). So EQUAL would give HALTS. The same move kills almost every question about what a program does, as opposed to how it is written.

Stretch. Suppose a program computes \(\mathrm{BB}\). Given \(P\) and \(x\), write them into one program \(Q\) of some length \(m\) that runs \(P\) on \(x\). Compute \(\mathrm{BB}(m)\) and run \(Q\) for that many steps. If it has stopped, answer "halts". If not, it never will, because \(\mathrm{BB}(m)\) is the longest any halting program of length \(m\) runs. That is HALTS, so \(\mathrm{BB}\) is not computable. It grows faster than any function a program can compute.

← PreviousNext: Hall's marriage theorem →