Alan Turing · Mathematics
How Alan Turing, in 1936, captured the very idea of mechanical computation in a single imaginary device - a machine reading and writing symbols on an endless tape - and thereby founded the theory of computation.
In 1936, a twenty-three-year-old Cambridge mathematician named Alan Turing published a paper with a forbidding title - On Computable Numbers, with an Application to the Entscheidungsproblem - that quietly founded an entire science. The question that drove it was deceptively simple: what does it mean to compute something? For millennia, people had carried out computations - adding, multiplying, following Al-Khwarizmi’s recipes, working through Euclid’s constructions - but no one had ever said precisely what a ‘computation’ is. We have an intuitive sense: a computation is a process that follows fixed rules mechanically, step by step, without insight or guesswork, of the kind a clerk could perform with paper and pencil by rote. But intuition is not a definition, and Turing needed a definition - because he wanted to prove that certain things cannot be computed at all, and to prove a thing impossible you must say exactly what the thing is. His answer was a stroke of genius: instead of trying to define computation abstractly, he imagined the simplest possible machine that could carry out any computation whatever, and identified computation with what such a machine can do. That imaginary device - now called the Turing machine - is one of the most important ideas in the history of thought, the conceptual foundation of every computer that has ever been built.
Let us look more closely at the four parts of a Turing machine, because their simplicity is the whole point. First, the tape: an endless strip divided into squares, each holding one symbol from a small fixed alphabet (in the simplest version, just ‘0’, ‘1’, and ‘blank’). The tape is the machine’s memory and workspace - its paper. Second, the head: a reader-writer positioned over a single square, which can read the symbol there, erase it and write a new one, and then shift one square to the left or right. The head can only ever see one square at a time - it has no overview, no big picture. Third, the states: a finite list of internal conditions the machine can be in, like the settings of a dial; the current state, together with the symbol under the head, is all the machine ‘knows’ at any moment. Fourth, the rule table (or ‘program’): a finite list of instructions, each of the form ‘if you are in state X and reading symbol Y, then write symbol Z, move left or right, and switch to state W.’ The machine simply runs: read the current square, look up the matching rule, do what it says, and repeat - over and over, mechanically, with no understanding, until it reaches a rule that tells it to halt. From this almost absurdly simple behaviour - read a symbol, write a symbol, move, change state - emerges, Turing showed, the entire power of computation.
Turing’s 1936 paper contains a second idea even more momentous than the machine itself: the universal Turing machine. A particular Turing machine has a particular rule table - it is built to do one job, like a dedicated device that only adds, or only sorts. But Turing realised that the rule table of any Turing machine could itself be written out as a string of symbols and placed on the tape, as data. He then designed a single, special machine - the universal machine - that reads, from its tape, a description of any other Turing machine, together with that machine’s input, and then simulates it: carries out exactly what the described machine would do. In other words, Turing invented a machine that can be any machine, simply by being given the right description to read. This is the theoretical birth of the programmable computer. The deep insight is that the distinction between machine (hardware) and program (software) dissolves: a program is just data describing a machine, and one universal machine, by reading different programs, can do the work of infinitely many special-purpose machines. Every modern computer is, at bottom, a physical realisation of Turing’s universal machine: a single device that becomes a word processor, a calculator, a game, or anything else, depending only on the program - the description - it is fed. The most important machine in human history was first conceived as a mathematician’s thought experiment about the nature of computation.
This is the opening of the lesson. The rest — the dialogue, the primary source, and the recall — is in the app.
You learned how Turing defined computation precisely by imagining an abstract machine that reads and writes symbols on a tape according to fixed rules. Explain what a Turing machine is and why this simple device captures the essence of all mechanical computation.
Leads to Al-Khwarizmi.
Begin this lesson →epoché — a humanities education that remembers you.