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.

*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.

Back to my home page

Michael Somos <ms639@georgetown.edu>

Michael Somos