Looking for a busy beaver.

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 stte (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 64,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 exist 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 one 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 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.