The Turing machine

The automaton from the last chapter checks dates, email addresses and phone numbers, but it can’t count parentheses or compare the two halves of a string: its whole past is squeezed into one of finitely many states. A stack coped with parentheses but stumbled on strings like aaabbbccc, with equally many letters of each kind. The chapter ended with a proposal: give the automaton memory with no limits at all, an infinite tape it can write on and come back to. The result is a machine so simple it is hard to imagine a simpler one, and, as it turns out, nobody has managed to imagine a stronger one.

This chapter is a game. You will program the machine in its own language, with transition tables, and work your way through levels: first add one to a number, then double it, recognize a palindrome, compare three counts, and at the end take on the record of the machine that runs longer than any other. Between the levels you will learn where the machine came from, how a single machine runs all the others, and why systems that nobody designed for computing keep turning out to be Turing complete.

Cambridge, 1935. A man with a pencil

In 1935 the word “computer” meant a person, not a machine: someone who worked out tables for gunners, astronomers and insurers by following instructions. That person is where Turing started, breaking the work down into its smallest movements. The computer writes symbols on squared paper and at any moment sees only a few squares. The computer also remembers where it is in the instructions and has finitely many states of mind; with infinitely many, similar ones would get mixed up. Depending on what is seen and remembered, the computer takes the simplest of steps: changes the symbol in a square, looks at a neighboring square, goes on to another item of the instructions.

Then Turing simplifies without losing anything. The two-dimensional sheet can be replaced by a long strip: the squares of the sheet are written out in a row. Looking at several squares at once is the same as looking at them one at a time and remembering, and memory is only a few more states. A complicated step breaks up into simple ones. What remains is what would soon be called a Turing machine. There were no electronic computers yet, and what Turing described was a person with a pencil, with as much paper and patience as needed and not a drop of ingenuity beyond the instructions.

Level 0. Tape, head, table

The machine has a tape: a row of cells, infinite in both directions. Each cell holds one symbol from a finite alphabet, and usually almost all of the cells are empty, holding a blank, which we will draw as _. A head stands over one of the cells. And inside the machine is the finite automaton from the last chapter: at every moment it is in one of finitely many states.

A step goes like this. The machine looks at the pair “my state, the symbol under the head” and finds the rule for that pair in its table. The rule says three things: which symbol to write into the cell, where to move the head (left, right or nowhere) and which state to go to. If there is no rule for the pair, the machine halts. That is all it can do.

A Turing machine is a tape, a head and a finite table of rules of the form “in state $q$, reading symbol $a$: write $b$, move $d$, go to $r$.” The table is written one rule per line. Here is a machine with a single state that walks along a binary number and flips every digit:

To describe the machine at any moment of its work, three things are enough: what is written on the tape, where the head is and which state the automaton is in. This triple is called a configuration, and it is written as one line, with the name of the state in square brackets right before the cell under the head. The work of the machine is a chain of configurations, each one following uniquely from the one before by the table. The course module cs.turing can print such a chain.

Five configurations: the head stepped right four times, flipping digits, and in the fifth it stands over a blank, for which there is no rule. The machine has halted, and the tape reads 0100. Now it is your turn: the game starts with this very machine. Its table, under the tape, is laid out as a grid, with a row for each state, a column for each symbol and a rule in each cell.

The first level is missing one rule: the machine doesn’t know what to do with a one, so it halts on the first one it meets. Add the rule. If everything is right, “Check” will run the machine on several numbers, the empty tape included, and mark the level as passed. Already here you can see how strict the check is: a test looks at the answer and also at whether the machine halted. A table that runs right forever gives no answer at all.

Level 2. Plus one

On the second level the machine has to count for the first time: there is a binary number on the tape, the head is on its first digit, and one must be added to the number. On paper you go to the lowest digit, at the right end. If the last digit is 0, it becomes 1, and you are done. If it is 1, it becomes 0, and a one is carried into the next digit to the left, where everything repeats. This is the carry that ran along the chain of adders in Chapter 30, only here the head carries it.

So the machine needs two states. The first goes right to the blank, changing nothing, and at the blank steps back and switches to the second. The second carries to the left: it turns ones into zeros and moves on, and at the first zero it writes a one and halts. One edge case is left. What happens to 111? The carry runs through every digit and runs into the blank to the left of the number. Think about which rule that pair needs, and build the machine on the second level of the game.

Level 3. Doubling: marks on the tape

Now the number is written in unary (111 means three, like notches on a stick), and it has to be doubled, leaving six ones on the tape. The automaton from the last chapter couldn’t do this even in principle. It would have to remember how many ones it had passed, but its memory is no larger than its set of states, and for any finite set of states there is a bigger number.

A Turing machine has memory, the tape, and the main technique for working with it is marks. The machine marks a processed one by replacing it with x, runs to the end and writes a copy there, also an x, returns to the first unmarked one and repeats. When no ones are left, the tape holds only x’s, twice as many as there were ones, and all that remains is to turn them back into ones. The hard part is the way back: going left, the machine must figure out where the copies end and the unprocessed ones begin, and see when no ones are left at all. The author’s solution has five states and eleven rules.

On a long number the head shuttles back and forth, each time a little farther. The author’s machine doubles twenty ones in 880 steps and forty in 3,360. The time grows as the square of the length: a machine with one head pays in running around for what a processor with addressable memory from Chapter 31 does in a single jump. For the question “what can be computed” the difference doesn’t matter; for the question “how fast” it matters a great deal. We will come back to the second question in Chapter 57.

Level 4. Palindrome

A palindrome is a word that reads the same in both directions: “level,” “noon,” abba. In Chapter 7 Python checked this in one line by comparing a string with its reverse. The last chapter showed that a finite automaton can’t compare the two halves of a string, so palindromes are beyond it too: having read up to the middle, it would have to remember the whole first half, and that can be as long as you like.

A Turing machine gets by with a shuttle. It erases the first letter and remembers it in its state: “carrying an a” and “carrying a b” are two different states. It runs right to the blank, steps back and looks at the last letter. If that letter doesn’t match, the answer is “no.” If it matches, the machine erases it too, returns to the start and repeats with a word two letters shorter. When there is nothing left to erase, the answer is “yes.” The answer is the state in which the machine halts: the game has two special states for it, “yes” and “no.”

What does the shuttle cost? On a word of length $n$ the machine runs across almost all of it, then across a word of length $n - 2$, then $n - 4$… This is the sum from Chapter 13, about $n^2/2$ steps. Here is the exact count, on the machine the course module knows as the shuttle.

Doubling the length makes almost four times as many steps, and the count stays close to $n^2/2$. At the bottom is a space-time diagram: each row is the tape after one more step, and time runs downward. The word melts away from both ends, and the head draws a zigzag. The square is no accident: it can be proved that any machine with a single tape needs on the order of $n^2$ steps for palindromes. A machine with two tapes manages in linear time: it copies the word onto the second tape and then compares the two copies, reading one forward and the other backward.

Level 5. Equal counts

On the ladder of machines from the last chapter, the automaton with a stack stands above the finite automaton. It checks parentheses but stumbles on strings like aaabbbccc: to compare the number of a’s with the number of b’s, it has to empty the stack, and nothing is left for the c’s. Marks come to the Turing machine’s rescue again. In one pass from left to right it crosses out one a, one b and one c, replacing them with x, and keeps an eye on the order of the letters as it goes. Then it returns to the start and repeats. If a pass doesn’t find the letter it needs, the answer is “no”; if there is nothing left to cross out, “yes.”

Once you pass the fifth level, you have climbed two rungs above the finite automaton. There is nothing above the Turing machine on this ladder: the languages it recognizes form the widest class in Chomsky’s table. Why nothing higher can be built is the question for the rest of the chapter.

Level 6. The busy beaver

The last level is a contest. The tape is empty, there are two symbols, the blank and 1, and at most three states, not counting the halt. Build a machine that runs as long as possible and still halts. A machine that never halts scores nothing; otherwise anyone could write an infinite loop. The Hungarian mathematician Tibor Radó invented this game in 1962 and called it the busy beaver problem: the beaver that works longer than anyone else but does rest in the end.

The record for three states is 21 steps, and there is no beating it. This can be proved by brute force: there are finitely many machines with three states, so you can list them all and find out for each one whether it halts, and when. For two states the record is 6 steps, for four it is 107. All the difficulty hides in the words “find out.” The record for five states waited more than sixty years for a proof, and the one for six is unknown and may never be known. You will see why in the next chapter, where the beaver returns.

A machine in twelve lines

The game on this page is written in JavaScript and the cs.turing module in Python, but both have the same heart, and it is shorter than this paragraph. The table lives in a dictionary whose keys are pairs “state, symbol” and whose values are triples “what to write, where to move, where to go.” The tape is a dictionary too, from a cell number to a symbol, and there are no empty cells in it at all. That makes the tape infinite in both directions, and cells to the left of the start get negative numbers.

The function returns the state in which the machine halted, the tape without blanks at the edges, and the number of steps. Press “Steps,” and you will see cells and head change: that is where the configurations live. The code has one rough edge: if the machine doesn’t halt within limit steps, the function returns the tape anyway, as if all were well. A careful simulator says “I don’t know, I didn’t wait long enough” in that case; writing one is one of the tasks of this chapter.

Incidentally, run doesn’t care which machine it runs: adding one, palindromes, the beaver. To it, a machine is data, a dictionary that can be read from a file, received over the network or generated by another program. That is how one program runs any machine.

A table on the tape

Turing noticed this in the same 1936 paper and took the next step: he built such a program as a Turing machine. The table of any machine is a finite text, and it can be written on a tape the way we wrote a number. Turing described a single machine $U$ with one fixed table that reads from its tape the description of another machine $M$ and an input for it, and then does what $M$ would do: step by step, running back and forth between the description and the data. It is called the universal machine.

The universal machine is slower than the one it runs: for every step of the guest it takes tens or hundreds of its own, because it has to search the description for the rule. But it pays in time, not in power. And it takes very little to be universal. In 1962 Marvin Minsky built a universal machine with seven states and four symbols; later Yurii Rogozhin and others found even more modest ones, such as one with four states, six symbols and only 22 rules.

You know this idea from Chapter 32: the program lies in the same memory as the data, and one unchanging circuit, the processor, runs any program. The logician Martin Davis, who also wrote a history of computing, argued convincingly that Turing’s idea influenced the way von Neumann described the EDVAC in 1945. The two men knew each other from Princeton: in 1938 von Neumann invited Turing to stay on as his assistant. The universal machine is a computer ten years before there were computers.

Princeton, 1936. Another road

We met Alonzo Church in Chapter 10: his λ-calculus is a language with nothing in it but functions. Church proposed to call computable whatever can be expressed in the λ-calculus, and in the spring of 1936 he used it to prove that the decision problem has no solution. Turing learned of this when his own paper was nearly finished. The two roads were so different that the paper was published anyway, with an appendix in which Turing shows that his machines and the λ-calculus compute the same things.

Church had a definition; Turing had an explanation of why it was the right one. The λ-calculus looks like an arbitrary formal game, while the Turing machine grew out of an analysis of what a person with a pencil does, and that is what makes it convincing. Reviewing his student’s paper, Church granted that it made the identification of computability by a Turing machine with computability in the ordinary sense “evident immediately.” In the same review he wrote the words “Turing machine” for the first time.

The statement “everything that can be computed by a mechanical procedure can be computed by a Turing machine” is called the Church–Turing thesis; Stephen Kleene began calling it a thesis in the 1940s and 1950s. The thesis can’t be proved: “mechanical procedure” is an informal notion, and only statements about formal ones can be proved. It is more of a definition that has stood the test of time. It could be refuted by presenting a way of computing that is clearly mechanical yet can’t be reproduced by a Turing machine. In ninety years no such way has turned up. What has turned up is a host of models of computation, invented independently and looking nothing alike, and every one of them has proved equivalent to the Turing machine.

Here is one task, doubling a number, on four such models: Python; the Turing machine from the third level of the game; Brainfuck from Chapter 49, where the doubler takes seven commands; and Church numerals from Chapter 10, where doubling $n$ means repeating an action $n$ times and then $n$ times more.

All four print 10. Of course, one example proves nothing. The equivalence of two models is proved differently: you show that each of them can run the other. We have already seen Python run Turing machines: that was the twelve lines above. It runs Brainfuck too: that is the function brainfuck in this cell. The other direction is more interesting: making a Turing machine run a Brainfuck program.

All machines are equal

This is easy enough if the machine is allowed a large alphabet. Let the symbols on the tape be numbers from 0 to 255, like Brainfuck’s cells, and let the state of the machine be the number of the current command of the program. Then each command turns into rules all by itself: + in state $i$ writes $v + 1$ in place of $v$ and goes to state $i + 1$; > moves the head; [ looks at the symbol and goes either to $i + 1$ or past the matching bracket. The tape of Brainfuck and the tape of the machine are one and the same here; no wonder Corrado Böhm described P′′, Brainfuck’s ancestor, in 1964 for a machine with a tape. Here is the translator.

The table came out large, 256 rules for each command, but the machine follows the program by it step for step. A binary alphabet would do too: each number from 0 to 255 would take eight cells of the tape, and the machine would get slower but not weaker. The other equivalences are proved the same way: two tapes are replaced by one, a tape infinite in both directions by one infinite in one direction, a large alphabet by a binary one.

That leaves the direction “a Turing machine runs Python.” It is proved by a chain, and you have already been through every link. The Python interpreter is a program in C. A compiler turns it into machine code (Chapter 33), the processor executes the machine code (Chapter 32), and a processor with memory is a finite transition table plus an array of cells. A Turing machine can keep the processor’s memory on its tape as “address: value” pairs and, running up and down the tape, execute its instructions one after another. It would be agonizingly slow, but it would work.

A system that can run any Turing machine is called Turing complete. Python, C, Brainfuck, the λ-calculus and Iskra-8’s processor are complete. The finite automaton and the regular expressions of the last chapter are not: parentheses and palindromes are beyond them. To be complete, a system needs three things: unlimited memory, a way to choose an action by what it has read, and a way to repeat. Take away any one of them, and completeness is gone.

Life on graph paper

Everything so far was invented on purpose: the Turing machine to compute, Brainfuck for the sake of the smallest compiler in the world. But completeness also turns up where no computing machine is in sight at all. The most famous example appeared in 1970 on graph paper: a few rules about neighbors that look nothing like a processor.

The rules of Life fit in two lines. A dead cell with exactly three live neighbors comes to life. A live cell with two or three live neighbors stays alive, and all the others die, of loneliness or of overcrowding. Everything is updated at once: the new generation is computed from the old one alone, like registers on a clock tick in Chapter 31. Such a device, a grid of cells, each with finitely many states, and one rule for all of them that looks at the neighbors, is called a cellular automaton. We can check that Conway lost his fifty dollars by counting the live cells of Gosper’s gun.

Every 30 generations there are five more cells, the size of one glider. The gun fires forever, and the pattern grows without bound. The function step, meanwhile, never scans the infinite board: it counts neighbors only around live cells, since only a cell next to a live one can come to life. This is the dictionary of Chapter 8 serving as a counter.

A glider can be read as a signal: a stream of gliders from a gun is a sequence of ones, and a missing glider is a zero. Two gliders that collide at a right angle at the right moment destroy each other without a trace. This gives a NOT gate: a second gun fires across the input stream. Where the input has a glider, it knocks out the second gun’s glider; where it has a gap, the second gun’s glider flies on. Similar collisions give AND and OR, and from them, as in Chapter 29, everything else.

The rest is engineering, if lengthy engineering. On April 2, 2000, Paul Rendell finished a Turing machine inside Life, assembled from guns, gliders and patterns that enthusiasts had collected over thirty years. The machine is small, three states and three symbols, and one of its steps takes 11,040 generations. But the design can be extended, and in 2010 Rendell built a version that runs a universal machine, and in 2011 one whose tape extends itself as needed. Life is Turing complete: four rules about neighbors on graph paper compute everything your computer does.

Complete by accident

Life is not alone in this. Once a system has unlimited memory, branching and repetition, it is almost certainly complete, whether its authors like it or not. Below is a gallery: for each exhibit, try to guess whether it is complete before you turn the card over.

A few exhibits deserve a story of their own. The cellular automaton Rule 110 is a one-dimensional Life in which a cell looks only at itself and its two neighbors. In 1985 Stephen Wolfram conjectured that it is Turing complete, and Matthew Cook proved it; but Wolfram’s company, where Cook worked, went to court to hold up the publication, and the paper came out only in 2004. C++ templates were meant for generic containers, and in 2003 Todd Veldhuizen showed that they can compute anything at all while the program is still being compiled. Stephen Dolan of Cambridge proved that of all the x86 instructions, one is enough, the data move mov, and Christopher Domas wrote a compiler that turns C programs into nothing but movs.

Farthest from computers, perhaps, is Magic: The Gathering, a card game. In 2019 Alex Churchill, Stella Biderman and Austin Herrick put together a position from ordinary tournament cards in which both players’ moves are forced and the play carries out a given Turing machine: the first player wins if and only if the machine halts. Remember this wording; it will come in handy in the next chapter.

What “complete” means in practice

First, completeness says nothing about convenience or speed: Brainfuck is complete, and Rendell’s machine takes 11 thousand generations per step. “Turing complete” means that anything can be done with it, not that anything is convenient to do with it.

Second, and this matters more, completeness comes at a price. If a language is complete, a program in it can run forever, and, as the next chapter will show, in general there is no way to know that in advance. So Turing-complete systems have to be restrained from outside. The GCC compiler stops instantiating templates at a depth of 900, and its documentation says plainly that the limit is there to catch endless recursion. TypeScript, whose type system is complete too, reports error 2589: “Type instantiation is excessively deep and possibly infinite.” In Ethereum every step of a contract program costs “gas,” and execution stops when the gas runs out.

It can go the other way too: when computing anything at all isn’t needed, a language is made incomplete on purpose. A regular expression without backreferences is a finite automaton, and an engine that runs it as an automaton, like Google’s RE2, guarantees time linear in the length of the string; a backtracking engine, like Python’s re, gives no such guarantee, as Cloudflare’s outage in the last chapter showed. Starlark, the language of Bazel’s build configurations, forbids recursion and while: its loops only walk over finite collections that already exist, so every program in it ends. When you choose a config format or a template language, ask whether it is complete, and what will happen when somebody writes an infinite loop in it.

Tasks

Three tasks. In the first two, the answer is the table of a machine in the string TABLE, in the same format as in the chapter: “state symbol -> write move new_state,” one rule per line, with a comment after #. The tests run the table on the course simulator: the input is written on the tape from cell 0, the head stands on cell 0, the start state is the state of the first rule, and the blank is _. It is handy to build the table in the game and press “Copy the table” there. In the third task you write the simulator yourself.

What next

If the Church–Turing thesis is to be believed, nothing is stronger than the Turing machine: everything that can be computed at all is computed by a table a few lines long. Its equals are almost everything that has memory, branching and repetition, from a processor to a card game. The question of what a machine can do has its answer. But that answer at once raises the next question.

Along the way we kept running into questions: will this table halt, will the first player win in the Magic position, will a Life pattern grow forever? These are precise questions with a yes-or-no answer, and each of them has an answer. But a simulator can only wait: if the machine has halted, the answer is “yes,” and if it hasn’t, perhaps it will in a minute. In 1930 David Hilbert was sure that there are no unsolvable problems. Does every precise question have an answer that a machine can find? That is the subject of the next chapter, where we will talk with someone who is sure he can answer the question of whether a program halts.