The Paper That Invented Computer Science: Alan Turing and On Computable Numbers (1936)

In the spring of 1936, a 23-year-old mathematician at King’s College, Cambridge finished a paper with a forbidding title - On Computable Numbers, with an Application to the Entscheidungsproblem - that set out to answer a narrow, abstract question about the foundations of mathematics. Along the way, almost as scaffolding for his argument, its author invented an imaginary machine so powerful and so general that it turned out to be the blueprint for every computer that would ever be built. His name was Alan Turing, and the paper is widely regarded as the founding document of computer science.

This is a tribute to what Turing wrote, the beautiful trick at its heart, and how a question about pure logic accidentally gave the world the machine you are reading this on.

1. A question at the edge of mathematics

Turing was not trying to build a computer. He was chasing a challenge posed by the great German mathematician David Hilbert: the Entscheidungsproblem, or “decision problem.” Hilbert asked whether there exists a single, purely mechanical procedure - what we would now call an algorithm - that could take any statement in formal logic and decide, with a guaranteed yes or no, whether it is provable. If such a procedure existed, mathematics could in principle be put on autopilot.

To prove whether it did, Turing faced a deep obstacle: what, exactly, counts as a “mechanical procedure”? Nobody had ever defined it rigorously. His stroke of genius was to answer that question by imagining the simplest possible machine that could do anything a human computer - then a job title, for a person who carried out calculations by hand - could do by following fixed rules.

2. To define a machine, he invented one

Turing opened the paper with a sentence of deceptive calm:

“The ‘computable’ numbers may be described briefly as the real numbers whose expressions as a decimal are calculable by finite means.”

To make “finite means” precise, he described a device of almost childlike simplicity. Picture an endless paper tape divided into squares; a head that can move left or right, one square at a time, reading and writing a single symbol; and a small table of rules that says, for each combination of current state and symbol under the head, what to write, which way to move, and what state to enter next. That is the entire machine. Turing called it an a-machine (for “automatic”); the world now calls it a Turing machine.

The astonishing claim was that this trivial-looking contraption is enough. Anything a mathematician could compute by a definite, step-by-step method, one of these machines could compute too. The tape and the table capture the whole essence of “following a procedure.”

3. The universal machine: the birth of software

Then Turing did something that still feels like sleight of hand. He noticed that the rule-table of any particular machine could itself be written down as a string of symbols - as data. And if a machine’s description is just data, then you could build one special machine that reads that description off its tape and behaves exactly like the machine it describes. He wrote:

“It is possible to invent a single machine which can be used to compute any computable sequence.”

This is the universal machine - and it is the most consequential idea in the paper. One machine, unchanged, can become any machine simply by being fed a different description. Change the program, not the hardware. That single insight is the reason the glass rectangle in your pocket can be a telephone, a camera, a map, a cinema, and an AI assistant, one tap apart - it is a universal machine, and those are all just programs. Turing had, on paper, split the computer into hardware and software more than a decade before either word meant what it does today.

4. The answer: some things can never be computed

With his definition of computation in hand, Turing could finally attack Hilbert’s question - and his answer was a resounding no. He showed that there is no general procedure that can decide, for every machine and input, whether the machine will ever finish and give an answer (the essence of what is now taught as the halting problem). From that, the Entscheidungsproblem falls: no algorithm can decide the provability of every mathematical statement. Some questions are simply undecidable.

Far from a defeat, this was a profound discovery. Turing had drawn a precise boundary around what any computer - past, present, or future - can and cannot do, and he did it in 1936, before a single electronic computer existed. It was the mathematical cousin of Kurt Gödel’s famous incompleteness theorems, reached by a completely different and far more tangible road: the road of machines.

5. Church, and the definition of ‘computable’

Turing was not entirely alone. Months earlier, the American logician Alonzo Church had reached the same conclusion about the Entscheidungsproblem by a very different route - his lambda calculus. When Turing learned of it, he added an appendix proving that his notion of machine-computability and Church’s were exactly equivalent. Together with a third formulation (recursive functions), they all pointed at the same class of problems. That convergence became the Church-Turing thesis: the claim that these equivalent definitions capture everything that can meaningfully be called “computable.” It remains the bedrock definition of the field.

There is a fitting footnote in the naming. Church, who would soon become Turing’s doctoral advisor at Princeton, reviewed the paper - and it was Church who gave Turing’s a-machine the name it has carried ever since: the Turing machine.

What the 1936 paper made possible

6. The mind behind the machine

Alan Turing (1912-1954) is celebrated today as the father of computer science and artificial intelligence, but in 1936 he was simply a brilliant, unassuming young mathematician who happened to think in machines. He would go on to an extraordinary decade: leading the codebreaking effort against the German Enigma cipher at Bletchley Park during the Second World War, helping design some of the earliest stored-program computers, and, in his 1950 essay Computing Machinery and Intelligence, posing the question “Can machines think?” and proposing the test that still bears his name.

The through-line from that 1936 paper to the present is unbroken. When the computing world’s highest honour was created in 1966, it was named the ACM A. M. Turing Award - now widely called the “Nobel Prize of Computing.” Every recipient, in a sense, is working inside the universe Turing sketched on paper as a young man.

Why it still matters

Ninety years on, Turing’s little tape-and-head machine is still how computer scientists define what a computation is. Every programming language, every processor, every cloud server is, at bottom, a way of realising a universal Turing machine. The reason a single laptop can run software its designers never imagined - including the neural networks behind today’s AI - is the very universality Turing proved possible in 1936.

He set out to answer a question about the limits of logic, and in doing so he handed us the machine that would remake the world. Some papers describe the world. A rare few build the one we live in. Turing’s is one of them.

Sources & further reading

• A. M. Turing, ‘On Computable Numbers, with an Application to the Entscheidungsproblem’, Proceedings of the London Mathematical Society, Series 2, Vol. 42, pp. 230-265 (1936-37)
• Wikipedia: Turing machine · Universal Turing machine · Entscheidungsproblem
• Wikipedia: Church-Turing thesis · Alan Turing
• Stanford Encyclopedia of Philosophy: Turing Machines
• Image: portrait of Alan Turing (1951) by Elliott & Fry, via the Computer History Museum; public domain (Wikimedia Commons)

Curated by Jerry Cards - jerrycards.com. Our 致敬 (tribute) series celebrates the landmark papers and discoveries that quietly built the modern world. More at jerrycards.com/news.