Busy Beaver Turing Machine

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 JACM 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 machine.

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. 647-665.

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 can exhibit.

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 abstract 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 A.K. Dewdney, 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 Jeffrey Shallit.

Turing Machine Information