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:
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 10865 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]