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 newsgroupfor 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 | ----------------------------------------------------------------------
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 | +---+--------------------+
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.