Turing Machines: How a Simple Machine Shattered Hilbert's Dream

In 1928 David Hilbert posed a challenge he believed would crown centuries of mathematical progress. He called it the Entscheidungsproblem, the decision problem: is there a mechanical procedure that takes any statement of first-order logic and determines, in finite time, whether it is provable?

Hilbert expected yes. He famously declared "Wir müssen wissen, wir werden wissen": we must know, we shall know. His vision was a kind of mathematical machine. Feed in a conjecture, turn the crank, out comes a proof or a refutation. No creativity required. No intuition. Just mechanism.

But the question had a hidden dependency. Before you can ask whether a procedure exists, you have to say what a procedure is. What does it mean for a process to be mechanical? In 1936 a twenty-three-year-old Alan Turing submitted a paper that answered both questions at once. To make "mechanical procedure" precise, he invented an abstract machine, not a physical device but a mathematical object, defined rigorously enough to prove theorems about. Then he used it to show that Hilbert's procedure cannot exist.

Let's build the machine.

Tape, head, table#

A Turing machine operates on a tape: an infinite sequence of cells stretching in both directions, each holding exactly one symbol from a finite alphabet. Three symbols suffice here: zero, one, and blank. The blank fills the tape initially, like empty space; the input sits somewhere on the tape and everything else is blank.

A head sits over one cell at a time. It can read the symbol in the current cell, write a new symbol to the current cell, and move one step left or one step right. That is all. One cell at a time. No jumping ahead, no reading several cells at once.

The machine also has a finite set of internal states, its frame of mind. At any moment it is in exactly one. There is a designated start state and one or more halt states; entering a halt state stops the machine. The entire behavior is governed by the transition function, a table of rules of the form: if you are in state $q$ reading symbol $s$, then write $s^{\prime }$, move left or right, and switch to state $q^{\prime }$. Each step, the machine consults the table, applies the matching rule, and repeats. That is the whole execution model. Nothing else is happening.

A palindrome checker#

Let's watch one work. We build a machine that checks whether a binary string is a palindrome, the same forwards and backwards.

The strategy: read the leftmost symbol and remember it, not on the tape but in your state. Blank it out, sweep all the way right to the last symbol, and compare. If they don't match, halt and reject. If they match, blank that one too, sweep back left to the new first symbol, and repeat. Run out of symbols without a mismatch and you halt and accept.

Trace it on 101. The head reads a one, remembers "looking for a one on the other end," blanks the cell, and sweeps right past the zero to the one at the far end. Match. It blanks that cell and sweeps back. Now the tape holds a lone zero between blanks. The head reads it, remembers "looking for a zero," blanks it, sweeps right, and immediately hits blank. No symbols left. Accept.

Pause and try: run the machine on input 100. Where does it reject, and roughly how many steps does an input of length $n$ cost?

The head reads the leading one, blanks it, sweeps right past two zeros to the end, and finds a zero where it remembered a one. Mismatch, halt, reject, on the very first comparison.

For the cost: each comparison requires a full shuttle across whatever remains of the string, and there are about $n/2$ comparisons over strings of length up to $n$, so the machine spends on the order of $n^2$ steps. You would check a palindrome at a glance; the machine tediously bounces between the ends. Slow, but correct, for any input, no matter how long.

One machine to run them all#

This machine looks primitive, and it is, deliberately. Turing stripped away everything inessential. No random access memory, no arithmetic unit, no subroutines. Just a tape, a head, and a lookup table.

But you can build up from it. There are Turing machines that copy strings, compare numbers, multiply, sort, anything you can express as a precise sequence of steps. And critically, there is a universal Turing machine: one that takes as input the description of any other Turing machine plus that machine's input, and simulates it step by step. One machine to run them all. This is the idea behind the stored-program computer: the hardware is fixed, and the program is just data on the tape.

The Church-Turing thesis#

Here is the deep claim, known as the Church-Turing thesis: anything effectively calculable, anything a human could compute by following rules with unlimited paper and patience, is computable by a Turing machine. A stronger physical variant came later: anything computable by any physically realizable process is Turing computable.

This is not a theorem. You cannot prove it, because "effectively calculable" is not a formal term. It is a hypothesis, tested against every alternative model of computation anyone has proposed. Lambda calculus, recursive functions, cellular automata, quantum computers: each computes exactly the same class of functions as a Turing machine. Some are faster. None compute more.

Nearly ninety years in, the thesis is unbroken.

The halting problem#

Now we can return to Hilbert. In Turing's framework, "mechanical procedure" means Turing machine, so the Entscheidungsproblem becomes: is there a Turing machine that takes any first-order statement, always halts, and correctly answers whether it is provable?

Turing showed the answer is no, and the key step is proving that a problem equivalent to what we now call the halting problem is undecidable; his paper posed it in terms of printing and circularity, and the name came later. The halting problem asks: given a Turing machine and an input, will the machine eventually halt, or run forever? It feels answerable. Just simulate the machine and see. But if the machine runs forever, your simulation runs forever too, and you never get to say "no."

So suppose there were a magic machine $H$ that solves it: hand $H$ any machine and any input, and it always halts and correctly answers "halts" or "doesn't." Build a new machine $D$ that takes a machine $M$ as input and does something devious: it asks $H$ whether $M$ halts when given its own description as input. If $H$ says yes, $D$ deliberately loops forever. If $H$ says no, $D$ immediately halts. $D$ is designed to do the exact opposite of what $H$ predicts.

Now run $D$ on itself. If $D$ halts, then $H$ must have said it would, but then $D$ was supposed to loop forever. Contradiction. If $D$ loops forever, then $H$ must have said it wouldn't, but then $D$ was supposed to halt. Contradiction. Either way $H$ got it wrong, so $H$ cannot exist. No Turing machine solves the halting problem in general.

Pause and try: $H$ is supposed to always answer. What exactly can it say when asked about $D$ running on $D$?

Nothing true. If $H$ answers "halts," then $D$ on $D$ loops, and the answer was wrong. If $H$ answers "doesn't halt," then $D$ on $D$ halts, and the answer was wrong again. The question "does $D$ halt on $D$?" still has a definite answer; the proof shows only that $H$ does not give it. Any machine you propose as a halting decider comes with its own $D$ built against it, a specific input on which it must fail.

Hilbert's answer#

The undecidability of the halting problem is enough to sink Hilbert's dream. If you could decide provability, you could in particular decide whether any given Turing machine halts, and we just showed that is impossible. The Entscheidungsproblem has no solution. Not because we haven't been clever enough: because no procedure could possibly work. Alonzo Church had reached the same verdict a few months earlier, in April 1936, by way of the lambda calculus. And the machine Turing built to prove it became the mathematical foundation of every computer that has existed since.

If this feels like a pattern you've seen before, a thing that breaks when you point it at itself, you're right. It is the same self-referential trick behind Cantor's diagonal argument, Russell's paradox, and Gödel's incompleteness theorems. Turing found it again, in the heart of computation.

If you remember three things#

1. A Turing machine is just a tape, a head, and a finite lookup table, and that is enough: a universal machine can simulate every other machine, the blueprint of the stored-program computer.
2. The Church-Turing thesis says everything effectively calculable is Turing computable; a stronger variant covers physical processes. It is a hypothesis, not a theorem, and ninety years of alternative models have not broken it.
3. The halting problem is undecidable by a self-reference argument, and that single fact answers Hilbert's Entscheidungsproblem: no mechanical procedure can decide all of mathematics.