Busy Beavers

One of the more fascinating issues involved in Turing Machines is the "Busy Beaver" problem: given a TM with a certain number of states and a blank tape, find the transition table that will cause it to write the maximum number of non-blank characters on the tape, yet still halt eventually, and without going off the end of the tape. The halting requirement means that the machine must not go into any sort of endless loop or oscillation. It turns out that seemingly very complex behavior can be generated on a machine with only a handful of states, as exemplified by the latest candidate for 5-State Busy Beaver, which executes tens of millions of transitions and leaves 4098 1's on the tape upon halting (this machine can be loaded and run from the applet, but I recommend one of the lesser candidates if you plan to wait for it to finish!) All this is related to the Halting Problem -- can it always be determined whether a Turing Machine will eventually halt, or are there some machines for which it is impossible to predict? It turns out that the latter is the case, which makes finding Busy Beavers significantly trickier.

Top
Prev: How to program
Back to the applet