# What did Alan Turing's 1936 paper 'On Computable Numbers' discover?

Date: 2019-10-03 · Author: Robert Scales · https://guidetoartificialintelligence.com/en/learn/what-is-a-turing-machine-on-computable-numbers/

**Answer:** In "On Computable Numbers," completed in 1936, Alan Turing described an imaginary machine that reads and writes symbols on a tape, and showed that one "universal" machine could carry out the work of any other such machine if given its description. He used it to prove that some mathematical questions can never be settled by any mechanical method, and the idea became a foundation of computer science.

In 1936 a 23-year-old mathematician at Cambridge wrote a paper that quietly described the computer before anyone had built one. Alan Turing's "On Computable Numbers, with an Application to the Entscheidungsproblem" imagined a very simple machine that works through a calculation one symbol at a time. Then he showed something astonishing: a single machine of this kind could do the job of every other one, as long as it was given a written description of that machine to follow.

He used these imaginary machines to answer a deep question in logic, and the answer was "no": there is no mechanical procedure that can settle every mathematical statement. Along the way he gave the world a precise definition of what it means for something to be computable.

## When, where and who

Turing had studied mathematics at King's College, Cambridge, and in 1935 the college made him one of its Fellows. Between 1935 and early 1936 he worked on the problem of decidability. In April 1936 he showed a draft to the mathematician Max Newman. That same month, the American logician Alonzo Church published a paper reaching a similar conclusion by a completely different route.

The paper was received by the London Mathematical Society on 28 May 1936 and read to the Society on 12 November 1936. It appeared in the Society's *Proceedings* in two parts at the end of 1936, with a short correction in 1937. By then Turing had moved to Princeton University to study with Church, who, in a review, was the first to call these devices "Turing machines."

## The problem Turing wanted to solve

In 1928 the German mathematician David Hilbert posed what became known as the *Entscheidungsproblem*, German for "decision problem." Roughly: is there a definite method that, given any statement in formal logic, can always decide whether it can be proved? Hilbert hoped the answer was yes. To show the answer was no, someone first had to say exactly what a "definite method" is. Turing's machine was that definition.

He started from a person doing arithmetic with pencil and paper. Such a person looks at a few symbols at a time, writes or erases one, shifts attention, and follows rules that depend on what they are thinking at that moment. Turing boiled this down to a machine with:

- a tape divided into squares, each holding at most one symbol;
- a reading head that looks at one square at a time;
- a finite set of internal states (Turing called them "m-configurations");
- a table of rules: for each state and symbol, what to write, which way to move, and which state to go to next.

## A worked example: Turing's first machine

The first machine in the paper simply prints 0 1 0 1 0 1 forever, leaving a blank square between each figure. It uses four states, which Turing labels b, c, e and f:

| Current state | What the machine does | Next state |
|---|---|---|
| b | Print 0, move one square right | c |
| c | Move one square right | e |
| e | Print 1, move one square right | f |
| f | Move one square right | b |

Trace it on a blank tape. In state b it writes 0 and steps right; in c it skips a square; in e it writes 1; in f it skips again; then it is back in b. The tape fills up as 0 _ 1 _ 0 _ 1 and so on. Nothing could be simpler, and yet Turing argued that every calculation a person can carry out by rule can be broken into steps this small.

> **Try it:** Change the table so the machine prints 0 0 1 0 0 1 repeating. You will need more states. Write your table on paper and trace the first twelve squares to check it works.

## The universal machine and the limits of computing

Section 6 of the paper makes the leap. Turing showed that the rule table of any machine can itself be written on a tape as a string of symbols. He then designed a single machine, the universal machine, that reads such a description and imitates the machine described, step by step. In his words: "It is possible to invent a single machine which can be used to compute any computable sequence."

This is the idea behind every computer you use: one piece of hardware, many programs. The program is just data that the machine reads.

Turing then turned the tool on Hilbert's question. He showed there can be no general procedure that looks at the description of any machine and decides in advance how it will behave, for example whether it will keep printing digits forever. From this he proved that the Entscheidungsproblem has no solution. Church reached the same result independently, and the two approaches were soon shown to be equivalent.

## Why it mattered

Turing's paper gave a clear, simple model of computation that is still taught in every computer science course. It showed what machines could in principle do, and also what no machine could ever do. After the Second World War, Turing himself designed one of the first stored-program computers, the Automatic Computing Engine at Britain's National Physical Laboratory, and described such machines as practical versions of his universal machine. Historians debate how directly the paper shaped early computers such as the EDVAC design, and they caution against calling Turing the single inventor of the computer. But the idea of the program as data that one general machine can run traces clearly back to 1936.

## What does a Turing machine have to do with AI today?

Every AI system in 2019, from the speech recognizer in a phone to a large language model such as GPT-2, runs on ordinary computers, and every ordinary computer is, in Turing's sense, a practical universal machine with a finite memory. Neural networks look very different from Turing's tidy rule tables, but in the end they are programs, and anything they compute could, in principle, be computed by a Turing machine given enough tape and time.

That gives a useful perspective. The 1936 paper says what is computable, not how fast or how cleverly. Modern AI is about the second part: finding programs, often by learning from data, that do useful things within practical limits of speed and memory. Turing also showed that some questions about programs have no general answer, which is one reason why fully checking what a complex AI system will do in every situation is so hard.

Turing returned to machines and minds in his 1950 paper on the imitation game, now called the Turing test. The universal machine of 1936 is what made that later question, "can machines think?", worth asking at all.

## Sources

- On Computable Numbers, with an Application to the Entscheidungsproblem: https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf
- Turing Machines: https://plato.stanford.edu/entries/turing-machine/
- Alan Turing: https://en.wikipedia.org/w/index.php?title=Alan_Turing&oldid=919248786