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 and symbols.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.
Sample of Busy Beaver Turing Machine
A.K.Dewdney "Five-state Busy Beaver Turing Machine Contender, Scientific American, April 1985,page 30
Known Busy Beavers upto 1995: http://grail.cba.csuohio.edu/~somos/busy.html
Nice survey paper
Heiner Marxen, Jürgen Buntrock : Attacking the Busy Beaver 5
Bulletin of the EATCS, Number 40, February 1990, pp. 247-251
Wikipedia: http://en.wikipedia.org/wiki/Busy+beaver
Posted by tjst at 2004年01月04日 13:02