Turing Machine Simulator

A Turing machine is almost insultingly plain. There is a tape divided into cells, a head over one cell at a time, and a finite table of rules. Nothing else.

That plainness is the whole point. In the 1930s mathematicians had a question they could not even state properly, because it turned on a word nobody had defined. The word was “mechanical”. Alan Turing answered by describing the least impressive machine he could think of and arguing that it was enough. The argument has held ever since, and the machine’s limits turned out to be limits on every computer built after it.

The question behind the machine

The question had a German name. The Entscheidungsproblem, or decision problem, was posed by David Hilbert and Wilhelm Ackermann in 1928. It asked for a procedure that would take any statement of formal logic and answer, after finitely many steps, whether the statement is universally valid. A procedure of that kind would have turned a large part of mathematics into routine work.

Nobody could show that such a procedure existed. To show that none could exist was harder still, because that needs a precise account of what counts as a procedure at all. Turing, then a young fellow of King’s College, Cambridge, had been thinking about decidability since attending Max Newman’s lectures. His paper, “On Computable Numbers, with an Application to the Entscheidungsproblem”, reached the London Mathematical Society in 1936 and was printed in volume 42 of its Proceedings.

In it he introduced an abstract machine that moves from one condition to another by a finite table of rules, depending only on the single symbol it is reading from a tape. He called it an automatic machine, or a-machine. The name “Turing machine” came afterwards, from Alonzo Church, in a review. Turing used the device to define a computable number: a real number whose decimal expansion such a machine could write out, starting from a blank tape.

Church had reached the same negative answer to Hilbert’s question by a very different route, and published first. That made it hard to get Turing’s paper accepted, and Newman had to argue the case for it. The two approaches were soon shown to agree. A function is computable in Church’s sense exactly when it is computable by one of Turing’s machines.

Why so little is enough

Here is everything such a machine does in one step. It reads the symbol under the head. It looks up the rule for its current state and that symbol. It writes a symbol, moves one cell left or right, and enters the state the rule names. Then it does the same again.

Books differ on the details, and a careful reader should know where. Some allow a third move, staying put. Some give the machine a halt state, others let it stop simply because no rule applies. The standard textbook definition makes the table a partial function: where it has no entry, the machine halts. The tape is unbounded in both directions, and all but finitely many cells hold a blank.

None of these choices changes what can be computed. That is the surprising part, and it is the content of the Church-Turing thesis: a function on the natural numbers can be calculated by an effective method if and only if a Turing machine can compute it. It is called a thesis because “effective method” is an informal idea. What can be proved, and was, is that every serious attempt to make the idea formal lands on the same class of functions.

Turing found a second thing in the same paper. One machine can be built that imitates all the others: hand it the table of any machine, written out on its tape, and it will do what that machine would do. This universal machine is widely regarded as the idea behind the stored-program computer, set down before the technology existed to build one. Real computers are organised very differently, with memory they can reach at random, because a tape walked one cell at a time is far too slow for practical work.

Reading a rule table

A table is easier to read than to describe. Take the smallest interesting machine, the two-state busy beaver. Its states are A and B, its symbols are 0 and 1, and 0 is the blank. In state A, reading 0, it writes 1, moves right and goes to B. In A reading 1, it writes 1, moves left and goes to B. In B reading 0, it writes 1, moves left and goes to A. In B reading 1, it writes 1, moves right and halts.

Start it in state A on a blank tape, with the head on cell 0. The first step writes a 1 on cell 0 and moves right to cell 1. The second writes a 1 there and comes back. Now the machine is in A and reading a 1, so it steps left to cell -1 without changing anything. It writes a 1 there, moves left, writes another on cell -2, and turns round. On the sixth step it is in B, reading a 1 on cell -1, and that is the halting rule.

The count is 6 steps, 4 ones. Four cells in a row hold a 1, from cell -2 to cell 1, and the head has come to rest on cell 0. Every one of those claims can be checked by pressing a step button six times. The same compact line that enthusiasts use for this machine, 1RB1LB_1LA1RZ, is just the table read row by row: what to write, which way to move, where to go.

Useful machines read the same way, only longer. A machine that adds one to a binary number runs right to the end of the digits, then walks back turning each 1 into a 0 until it meets a 0 or a blank, which becomes a 1. Given 1011 it stops with 1100 on the tape. Three working states are enough.

The question no table can answer

Once machines can be written down as tables, they can be handed to other machines as input. So ask for a machine that takes any table and any starting tape and reports whether that computation ever stops. This is the halting problem, and no such machine exists.

The usual argument is short. Suppose a halting tester existed. Build a second program that hands its own description to the tester and then does the opposite of whatever was predicted, looping if told it halts and halting if told it loops. Whatever the tester says about that program is wrong. So the tester cannot be right in every case.

Two cautions about the history. Turing did not use the words “halt” or “halting” in his published work. His paper asked whether a machine ever prints a given symbol, and whether a machine is what he called circular. The phrase “halting problem” appears in print only in the 1950s and is credited to Martin Davis. The result is Turing’s all the same.

The second caution matters to anyone running a simulator. Undecidable does not mean that nothing can ever be known. It means no single method works for every machine. If a machine returns to exactly the configuration it was in before, with the same state, the same head position and the same tape, it will repeat forever. That can be detected. So can a machine that marches off in one direction doing the same thing at each stage. What cannot be done is to run a machine for a million steps, see it still going, and conclude that it never stops.

The busiest machines

In 1962 Tibor Rado turned that warning into a game. Take all machines with n states and the symbols 0 and 1, start each on a blank tape, and discard those that never halt. Among the rest, which one runs longest, and which leaves the most ones? The winners are called busy beavers. The two maxima, written S(n) for steps and Sigma(n) for ones, are perfectly well defined, since there are only finitely many tables of each size.

They are also not computable. Both grow faster than any function a program can calculate. The reason loops back to halting: if S(n) were known, every n-state machine could be run for S(n) steps, and any machine still going could be declared endless. A way to compute S would therefore solve the halting problem.

Small cases can still be settled by hard work. One state gives 1 step. Two states give the 6 steps traced above, which Rado found with pencil and paper. For three states the maximum is 21 steps and 6 ones, proved by Shen Lin and Rado in work published in 1965, and no single machine holds both records. Their method was to guess 21, run tens of thousands of machines that far, and then prove, by studying the survivors, that none of them would ever halt.

Four states took until 1983, when Allen Brady published a proof that the maximum is 107 steps, by a machine that leaves 13 ones. Then the numbers leave the human scale. A five-state machine found by Heiner Marxen and Jürgen Buntrock in 1989 runs for 47,176,870 steps and leaves 4,098 ones. For decades it was only the best known.

It was confirmed as the true maximum in 2024. A collaboration of volunteers working online, the Busy Beaver Challenge, decided the fate of 181,385,789 five-state machines and checked the entire argument with the Coq proof assistant. Their paper describes it as the first new busy beaver value in over forty years and the first ever to be formally verified. For six states only lower bounds are known, and they are already too large to write as ordinary numbers.

That is the honest shape of the subject. A device a child can operate, with a table that fits on a postcard, can outrun every attempt to predict it. A simulator can show each step, count exactly, and prove the easy cases of endlessness. Beyond those it can only report how far it looked.