On this page
Every phone, laptop and exam-result server runs on an idea Alan Turing wrote down before electronic computers existed. In 1936 he asked what it means to calculate something by following rules, and answered with a machine simple enough to trace with a pencil. This post explains the paper in plain terms, walks through his first example machine step by step, and shows what a student can learn from the way he attacked the problem.
Who was Turing when he wrote it?
Turing was born in London on 23 June 1912. He studied mathematics at King's College, Cambridge, and was elected a Fellow of the college in 1935. That year, in lectures by the topologist Max Newman, he heard about Gödel's incompleteness result and an open problem posed by David Hilbert, the *Entscheidungsproblem* or decision problem: is there a method that can decide, for any mathematical statement, whether it can be proved?
He was 23 and new to mathematical logic. The Stanford Encyclopedia of Philosophy calls the resulting paper "his first and perhaps greatest triumph" and "the founding work of modern computer science".
What did the 1936 paper set out to do?
"On Computable Numbers, with an Application to the Entscheidungsproblem" was received on 28 May 1936 and read on 12 November 1936 by the London Mathematical Society. It opens with a definition: "The 'computable' numbers may be described briefly as the real numbers whose expressions as a decimal are calculable by finite means."
The hard part was making "by finite means" exact. Turing did it by imagining a person doing a calculation and stripping away everything inessential. "We may compare a man in the process of computing a real number to a machine which is only capable of a finite number of conditions," he wrote, justifying the limit by "the fact that the human memory is necessarily limited".
What is a Turing machine?
The machine has a tape divided into squares, each of which can hold one symbol. At any moment it scans one square. It has a finite set of internal states, which Turing called m-configurations. A table says, for each state and scanned symbol, what to do: print or erase a symbol, move one square left or right, and which state to go to next. That is all.
Worked example: Turing's first machine
Turing's first example prints the sequence 0 1 0 1 .... It has four states, b, c, e and f, and starts in state b on a blank tape. Its table:
State b, blank square: print 0, move right, go to c.
State c, blank square: move right, go to e.
State e, blank square: print 1, move right, go to f.
State f, blank square: move right, go to b.
Trace it, numbering the squares 1, 2, 3 and so on:
In b at square 1: print 0, move to square 2, now in c.
In c at square 2: move to square 3, now in e.
In e at square 3: print 1, move to square 4, now in f.
In f at square 4: move to square 5, now in b.
In b at square 5: print 0, and the cycle repeats.
The tape reads 0, blank, 1, blank, 0, blank, 1 and so on. In later machines Turing used the in-between squares for temporary marks. Four rules produce an endless, exactly specified sequence.
What is the universal machine?
In section 6 Turing showed something more surprising: "It is possible to invent a single machine which can be used to compute any computable sequence." You write the table of another machine onto the universal machine's tape, as a string of symbols, and it imitates that machine. Instructions become data. That is the idea behind any computer that loads programs instead of being rewired for each job.
What can no machine compute?
Turing then turned the definition on itself. He showed there can be no general process for deciding whether an arbitrary machine, given by its description, will go on printing digits forever. From this he proved that "the Hilbertian Entscheidungsproblem can have no solution". The version taught today, the halting problem, is a close relative that was formalised later; the Stanford Encyclopedia's entry on Turing machines explains how the two problems relate.
Turing was not alone. Alonzo Church at Princeton had defined "effective calculability" in a different way, and Turing added an appendix showing the two ideas are equivalent.
Common misunderstandings
A Turing machine is not a physical computer. It is a mathematical description of a procedure, with an unlimited tape.
"Uncomputable" does not mean "hard". It means no procedure at all works for every case, however fast the machine.
Turing did not prove it with a computer. The proof is pure logic on paper.
What can a student take from Turing's way of working?
Turing took a vague word, "mechanical", and replaced it with a definition precise enough to prove things about. You can use the same habit on any problem that feels fuzzy: write down exactly what is given, what counts as a step, and what would count as an answer. He also checked his definition against a human doing the job, which is a good test for any model you build. George Pólya's advice in How to Solve It makes the same demand: understand the problem before you try to solve it.
Breaking a solution into explicit steps is also how you find the one you got wrong. The Fermi Problem Library has a step-by-step solver that explains the reasoning rather than printing an answer, so you can compare your steps with a full line of argument.
Try it today: write a four-state table that prints 1 1 0 1 1 0 ..., then trace ten steps by hand to check it.
