Indexing the archive…
Your Universe of Digital Possibilities
Ask a machine whether any program will ever stop. Build the console H that answers — and it works, honestly, on a gallery of small programs. Then build the one program H cannot survive: D, which asks H about itself and does the opposite. Feed D its own listing and the verdict lamp strobes without end — HALT forces LOOP forces HALT. Turing proved in 1936 that no program decides halting for all programs; every decider you can write ships with its own nemesis. The one door is exact — clamp the tape to a finite length and halting becomes decidable by sweep — and it shuts again the moment you unclamp. This instrument ends at the wall.
A read/write head on an unbounded tape, steered by a finite table of rules — and that is the whole of what is computable. The universal machine reads another machine’s table off the tape and runs it: the first proof that one device can do anything any device can.
Will program p, run on input x, ever stop? Turing’s diagonal argument proves no single program can answer for all p — the first problem shown to have no algorithm. The busy beaver is its shadow: knowing S(n) would solve halting.
Cantor’s trick, aimed at machines. Suppose H decides halting for every program. Build D that asks H about itself and does the opposite. Then D(D) halts iff H says it doesn’t — H(D,D) = ¬H(D,D), a flat contradiction. No total H exists; every decider ships with its own nemesis.
Turing defined the machine in 1936 in order to prove what machines cannot do. Suppose a program H could decide, for every program and input, whether it halts. Then assemble D: it asks H about itself and does the opposite — halts when H predicts it loops, loops when H predicts it halts. Run D on its own description and H(D, D) must equal its own negation. The contradiction is total, so H cannot exist. This is Cantor’s 1891 diagonal — build the object that differs from every row at its own place — aimed at computation; the same trick returns at The Sentence, aimed at proof. Rice (1953) widens it: every non-trivial property of what a program computes is undecidable. The door is exact and dated: bound the tape and the state space is finite, so halting is decided by sweep — and the busy beaver marks where the fence’s price explodes. The impossibility is the finding.