Busy Beaver Turing Machine
This story starts around 1960. Tibor Rado, a professor at the
Ohio State University, thought of a simple non-computable function
besides the standard halting problem for Turing machines. Given
a fixed finite number of symbols and states, select those Turing
machine programs which eventually halt when run with a blank tape.
Among these programs find the maximum number of non-blank symbols
left on the tape when they halt. Alternatively, find the maximum
number of time steps before halting. This function is well-defined
but rapidly becomes un-computable for even a small number of states
He published an article about it in 1962, but went beyond
just writing about a theoretical result. With his student Shen Lin,
they actually tackled the two symbol, three state problem. The
study resulted in a dissertation for Lin in 1963 and an article in
in 1965. After the initial flurry of articles there has been
several others mentioning results. The most popular is probably
the August 1984 Scientific American Computer Recreations column by
Dewdney. There is a PostScript handout by
Jeffrey Shallit about the problem.
Busy Beaver articles
- On Non-Computable Functions, Tibor Rado, The Bell
System Technical Journal, vol. XLI, no. 3, May 1962, pp. 877-884.
- This is the original article that explains the problem. This is
a theoretical article and gives only a single example of a three state
- Shen Lin and Tibor Rado. Computer studies of Turing machine problems.
Journal of the ACM, 12(2):196-212, April 1965.
- This article actually describes the process leading to the solution
of the three state problem. Many details of the machine encoding of
the Turing machines. Has a list of forty machines that required human
analysis. This is based on Shen Lin's thesis results.
- The Determination of the Value of Rado's Noncomputable Function
Sigma(k) for Four-State Turing Machines by Allan H. Brady,
Mathematics of Computation, vol. 40, no. 162, Apr 1983, pp.
- This article contains a description of the process leading to a
solution of the four state problem. It refers to his 1964 thesis.
Has several examples to illustrate the kind of behavior the machines
- The Complex Behavior of Simple Machines, by
Rona Machlin and
Quentin F. Stout,
Physica vol. 42D, 1990, pp. 85-98.
- This article is an independent solution of the four state problem.
Gives a good description of the tree-normal method. Has examples of
machines including some five state contenders by Juergen Buntrock and Heiner Marxen. The
is on the web.
This volume of Physica D appeared as a book "Emergent Computation"
edited by Stephanie Forrest
published by MIT Press and based on the 1989
Los Alamos Conference on Emergent Computation.
- Computer Recreations, by
Scientific American, Apr 1985, p. 30.
- This article gives the Uhing five state contender and mentions
the microprocessor aided search process. His interest was sparked by
reading the August 1984 Dewdney article. The current record for six
states is 95,524,079 marks in 8,690,333,381,690,952 steps by Heiner
Marxen according to a
paper in PostScript by
Turing Machine Information
For a quick introduction to Turing machines
you can visit the Turing's World site at Stanford.
Heiner Marxen has a
good web page about
Busy Beavers and his own contenders.
A German translation of this webpage by azoft.
Back to my home page
Last Updated Mon Apr 04 11:12 EDT 2011