The business of busy beavers.

The business of busy beavers

Start with a string of zeros and ones printed on a strip of tape and a device that reads, prints and erases symbols. The device scans the tape and, following a set of precise instructions, makes appropriate changes in the printed symbols. Given sufficient time, such a simple device -- known as a Turing machine -- can perform any computation that a modern digital computer, no matter how powerful, can do.

Of the many possible Turing machines, a few researchers have been looking for one dubbed the "five-state busy beaver." The idea is to find a set of five instructions for printing the largest possible number of ones on a tape originally filled only with zeros. Its mission accomplished, the machine would then automatically shut down.

Finding this creature turns out to be no simple matter. In 1985, amateur mathematician George Uhing discovered a five-state Turing machine that prints 1,915 ones as it goes through more than 2 million moves before finally stopping (SN: 2/9/85, p.89). Now, heiner Marxen of the Technical University of Berlin has topped Uhing's mark by finding a five-state Turing machine that prints 4,098 ones on a tape, taking nearly 12 million steps.

Scientists don't know whether this particular machine is the long-sought five-state busy beaver. Other sets of five instructions might conceivably print out even more ones before coming to a stop. But Marxen's solution already requires so many moves that it would probably take an army of people, using the fastest available computers, many years to search for better machines. "It begins to make it somewhat improbable that we can solve the five-state problem," says Allen H. Brady of the University of Nevada at Reno, who confirmed Marxen's discovery. In contrast, computer scientists already know that no conceivable four-state Turing machine can print more than 13 ones before halting.

With so many moves involved in just a five-state machine, it's difficult to distinguish in general between Turing machines that stop and those that continue computing forever -- a way of determining the truth of certain mathematical conjectures. Translated into mathematical terms, this means the number of steps required to solve particular mathematical problems can easily outstrip the ultimate problem-solving capacity of real computers.