Busy Beaver

From: csaamw@urc.tue.nl (Michiel Wijers)
Date: 6 Jan 1995 10:05:09 GMT
Organization: Eindhoven University of Technology, The Netherlands
Newsgroups: sci.math

Re: Busy Beaver

Armando Barbot Matos and Jose Paulo Leal of the Universidade
do Porto, Portugal, asked on January 5th in newsgroup 
for the current state of affairs with respect to the Busy
Beaver Problem.

BB(5) >= 501 was found by Uwe Schult in January 1983. The number
of shifts SH is 134,467. The instructions read:
1B -> 21R, 11 -> 3BL, 2B -> 31R, 21 -> 41R, 3B -> 11L,
31 -> 2BR, 4B -> 5BR, 41 -> S1R, 5B -> 31L, 51 -> 11R.
This solution has been published in:
J. Ludewig, U. Schult, and F. Wankmueller. Chasing the Busy
Beaver - Notes and Observations on a Competition to Find the
5-state Busy Beaver. Forschungsberichte des Fachbereichs
Informatik, 159, Universitaet Dortmund, Dortmund, 1983.

BB(5) >= 1915 was found by George Uhing in December 1984. The
number of shifts SH is 2,133,492. The instructions read:
1B -> 21R, 11 -> 31L, 2B -> 1BL, 21 -> 4BL, 3B -> 11L,
31 -> S1L, 4B -> 21L, 41 -> 51R, 5B -> 4BR, 51 -> 2BR.
This solution has been published in:
A.K. Dewdney, Computer Recreations, in: Scientific American,
vol. 252, no. 4, april 1985, pages 12-16.

BB(5) >= 4098 was found by Heiner Marxen and Juergen Buntrock
in September 1989. The number of shifts SH is 47,176,870. The
instructions read:
1B -> 21L, 11 -> 31R, 2B -> 31L, 21 -> 21L, 3B -> 41L,
31 -> 5BR, 4B -> 11R, 41 -> 41R, 5B -> S1L, 51 -> 1BR.
This solution has been published in:
H. Marxen and J. Buntrock. Attacking the Busy Beaver 5.
Bulletin of the EATCS, 40, pages 247-251, February 1990.

Marxen and Buntrock also present a six-state beaver:
BB(6)>=136,612 and SH>=13,122,572,797.
1B -> 21L, 11 -> 11L, 2B -> 31R, 21 -> 21R, 3B -> 6BR,
31 -> 41R, 4B -> 11L, 41 -> 5BR, 5B -> 1BL, 51 -> 31R,
6B -> 51L, 61 -> S1L.

Worthwhile reading are the following publications:
A.H. Brady. The Busy Beaver Game and the Meaning of Life. In:
Rolf Herken (ed), The Universal Turing Machine: A half-century
survey, pages 259-277, Oxford University Press, 1988.
R. Machlin and Q.F. Stout. The complex behavior of simple
machines. Physica D, 42, pages 85-98, 1990.

Several results on Turing machines given by quadruples instead
of quintuples have been published in:
A. Oberschelp, K. Schmidt-Goettsch, and G. Todt. Castor
Quadruplorum. Archive for Mathematical Logic, 27, pages 35-44, 1988.


 ----------------------------------------------------------------------
| ir. H.J.M. Wijers                  | Name  : Michiel                 |
| Eindhoven University of Technology | Room  : BG 3.25                 |
| P.O. Box 513                       | Phone : +31-40-474536           |
| NL - 5600 MB  Eindhoven            | Fax   : +31-40-454175           |
| The Netherlands                    | Email : H.J.M.Wijers@csg.tue.nl |
 ----------------------------------------------------------------------

Five-state Busy Beaver Turing Machine Contender

Scientific American, April 1985

page 30, A.K.Dewdney

At the end of the March column I mentioned a new candidate for the five-state busy beaver [see "Computer Recreations," Scientific American; August 1984]. In December, George Uhing of Bronx, N.Y., found a five-state Turing machine that prints 1,915 1's before halting. The Uhing machine is reproduced in the table below.

To discover what the machine will do in state B, for example, examine the row bearing that label. The row is subdivided into an upper and a lower portion listing the machine's responses to a 0 or 1 respectively. If the machine reads a 1 on its tape, it enters state D, prints a 0 on the tape and then moves one cell to the left. In the table H means that the machine halts.

Uhing, who programs for a Manhattan optical company, decided to search for the five-state busy beaver after reading this column last August. He used a Z-80 microprocessor running an assembly-language program to oversee a second machine: A Turing-machine simulator that cost Uhing less than $100 to build. It goes through seven million Turing-machine transitions per second. Each transition amounts to a simple lookup in a table like the one below. Uhing seems determined to find the five-state busy beaver. Does the present machine qualify? It showed up after Uhing's computer had been running for a month. As far as I know it is still running.

Allen H. Brady of the University of Nevada at Reno describes Uhing's machine as "astounding." What are the chances we shall discover a six-state busy beaver? "Absolutely out of the question," Brady says.

 old read  new write move
+---+--------------------+
| A |  0    B    1    R  |
|   |  1    C    1    L  |
+---+--------------------+
| B |  0    A    0    L  |
|   |  1    D    0    L  |
+---+--------------------+
| C |  0    A    1    L  |
|   |  1    H    1    L  |
+---+--------------------+
| D |  0    B    1    L  |
|   |  1    E    1    R  |
+---+--------------------+
| E |  0    D    0    R  |
|   |  1    B    0    R  |
+---+--------------------+

Looking for a busy beaver

Science News, February 9, 1985

page 89

Last fall, George Uhing, an amateur mathematician in Bronx, N.Y., built a special-purpose computer to try to solve a mathematical puzzle that he had found in the August SCIENTIFIC AMERICAN. Late in the year, he came up with an answer that has startled mathematicians and computer scientists interested in logic and the theory of computing.

Uhing's result implies that the behavior of even simple digital "machines" can quickly get out of hand, much sooner than mathematicians had expected. Translated into mathematical terms, this means that the amount of computation or number of steps needed to solve particular problems can easily surpass the ultimate problem-solving capacity of a real computer.

The problem Uhing looked at involves a Turing machine, named for the late British mathematician Alan M. Turing. A typical Turing machine can be represented as a device that reads and writes symbols on an infinite tape and has a control unit that can take on a finite number of states. The control unit essentially consists of a table that tells the machine what to do. The first part of the instruction specifies what the machine should write, depending on whether it sees a one or a zero. The second part determines whether the machine stays in the same state or shifts to another state (usually, a different set of instructions). The third part of the instruction specifies whether the printing head is to shift one frame to the left or to the right along the tape.

These Turing machines embody a method of mathematical reasoning. Given a large but finite amount of time, a Turing machine is capable of any computation that can be done by any modern digital computer, no matter how powerful.

Uhing was looking for a particular Turing machine dubbed a "busy beaver," which satisfies the condition: If a Turing machine has five possible states, what is the largest number of ones it can print on a blank tape (all zeros to start with) before coming to a stop? It is now known that a three-state busy beaver writes six ones before it halts; a four-state busy beaver writes 13 ones. Until Uhing's work, the top candidate for a five-state busy beaver printed 501 ones.

Using hardware worth less than $100, Uhing built a small computer that automatically tested, one after another, a selection of the 63,403,380,965,376 different possible five-state Turing machines. Many were easy to eliminate because it was obvious that they would fall into infinite loops or run on forever. Others stopped almost immediately.

After letting his computer run for about three weeks while it sifted through several million possibilities, Uhing found one five-state Turing machine that prints 1,915 ones as it goes through more than 2 million moves. However, Uhing doesn't know yet whether his machine is the long-sought busy beaver because other five-state machines may exists that print out even more ones. "I'm now trying to think up ways to eliminate uncertainties," he says.

The fact that a five-state Turing machine can print at least 1,915 ones and must go through more than 2 million shifts before halting is itself significant, says mathematician Allen H. Brady of the University of Nevada in Reno, who recently checked Uhing's result. "We have no idea what the jump from four states is going to be. It's already so large." Because so many moves are involved for just a five-state machine, Brady adds, "our ability to distinguish between the machines that halt and the machines that don't halt has diminished." Whether a particular Turing machine stops is tantamount to proving or disproving certain mathematical conjectures.

Says Alexander K. Dewdney of the University of Western Ontario in London and author of the "Computer Recreations" column in SCIENTIFIC AMERICAN, "To me, the interesting thing is that basically you've got an amateur doing something which is of great interest to professionals." A description of Uhing's machine will appear in a future SCIENTIFIC AMERICAN.


Typographical Error

There is a slight typographical error in the Science News article. The total number of Turing machines with N states is (4N+4)^(2N). In the case (N=5) the number should be 24^10 but the published number was one digit off. I thank Robert Munafo for pointing this out. He also mentions that just for searching for busy beavers, a smaller number, (2N-1)*(4N)^(2N-2), due to Lin and Rado suffices.
Back to my Busy Beaver page
Back to my home page
Last Updated Tue Mar 25 13:10 EST 2003
Michael Somos <somos@grail.cba.csuohio.edu>
WWW URL: "http://grail.cba.csuohio.edu/~somos/"