brainwagon

If you get a degree in computer science, you end up taking classes on the theory of computation. Here you learn about something called a Turing Machine: an abstract computer that is very simple, yet can be shown to be able to compute anything that any other computer can compute. The Turing machine consists of:

• a TAPE which is divided into cells, each one of which can contain a character. For the sake of this argument, we’ll assume that each cell can either hold a one or a zero, but no other values. The tape is best visualized as doubly infinite, stretching off to infinity in both directions around the start position. For the sake of this discussion, we’ll assume that the tape is initialized to all zeros.
• a HEAD which can read or write symbols on the tape. At any given time it is positioned over a cell, and can move either one step to the left or the right.
• a TABLE, which governs the actions of the Turing machine. This table is a mapping which takes as inputs the state of the machine (hold on, we’ll get to that) and the character under the read head, and tells you:
  • what symbol to write at the current location
  • whether to move the head left or right, and
  • which state to change to. If the new state is a special HALT state, then the machine stops, and the computation is over.

  The state table is read only, and fixed in size.

• a STATE REGISTER, which holds the current state

And that’s all there is to it. With a little work, you can figure out how to do anything that you might consider comptutation on such a machine: there simply doesn’t appear to be any feature you can add to such a machine to actually increase its ability to compute stuff. This would be not too interesting, except that there are things which cannot be computed by such a machine, and by extension any other machine. It turns out that one of the simplest questions that cannot be answered is whether a given program will arrive in the halting state, the so-called “halting” problem.

Another somewhat interesting question is “what is the maximum number of ones that a Turing Machine with n states and which halts can write on an initially blank tape?” This is the so-called Busy Beaver problem, and it too is uncomputable. For certain small values of n we can exhaustively analyze all possible Turing machines, and we find that a 2 state Turing Machine over the binary alphabet can write 4 ones, a 3 state machine 6 ones, and a 4 state machine can write 13 ones. The reader might try to hypothesize a guess as to what the maximum number of ones written by a 5 state machine might be. Then, consider a six state machine.

The best known 5 state machine writes 4098 ones, and is not known to be the maximal. There exist a 6 state machine that writes over 1.2 x 10⁸⁶⁵ ones.

For fun, I dug out the best known 5 state machine, and wrote a little .signature program version of it, which I include below. It runs for 47,176,870 cycles and writes 4098 ones before halting. If you’d like to learn more, surf to the links above, and check out Heiner Marxen’s page for more information.

int S[5][2][3]={1,0,1,1,2,2,1,0,2,1,0,1,1,0,3,0,2,4,1,2,0,1,2,3,1,0,-1,0,2,0},
tp[20000],*T=tp+99,*q,P,c,s,o;main(){for(;s>=0;c++)o+=*(q=S[s][T[P]])-T[P],T[P
--]=*q++,P+=*q++,s=*q;printf("%d steps %d ones\\n",c,o);} /* markv@xxxxx.xxx */

[tags]Computer Science,Theory of Computation,Turing Machine[/tags]