More on Turing Machines

Here are a few good links to follow if you're interested:
* Turing's World is a commercial product from Logic Software that allows you to model and study Turing Machines. They have also given a good deal of introductory info on TM's here.
* Michael Somos's 2-dimensional Turing Machine Simulator.
* The Alan Turing Homepage


One of the more fascinating issues involved in Turing Machines is the Busy Beaver problem.
i.e.: 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.

Here's a list of some of the latest contenders for 5 and 6-state Busy Beavers, as well as some information about the Uhing machine (which prints 1915 1's before halting) and how it was discovered.


On to the applet...
Back to the intro