Starting in 1996, Alexa Internet has been donating their crawl data to the Internet Archive. Flowing in every day, these data are added to the Wayback Machine after an embargo period.
Starting in 1996, Alexa Internet has been donating their crawl data to the Internet Archive. Flowing in every day, these data are added to the Wayback Machine after an embargo period.
TIMESTAMPS
The Wayback Machine - https://web.archive.org/web/20161105013714/http://somos.crg4.com:80/bb.html
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
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.
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.
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.
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.
