Abstract: This paper examines the actions of Turing machines operating on an initially blank tape, specifically the calculation of "Busy Beaver" numbers. It is impossible to calculate Busy Beaver numbers for arbitrary machines since they grow faster than any computable function and hence determining them would allow one to to solve the halting problem. However, complete characterizations of behavior are possible if the number of states is very small. The approach utilized here combines normalization to drastically reduce the number of machines considered and human generated classification schemes that are converted into computer generated proofs of behavior where one computer program proves that another is in an infinite loop of a specific type. For the few machines not analyzed by these techniques, a human analyzes their behavior. This approach can be applied to other simple computational systems, giving complete characterizations in sufficiently small domains.

This computer-assisted classification approach is of interest in the area of emergent systems since the properties of such systems are often difficult to determine. By using computers to eliminate vast numbers of machines with well understood behavior, some unanticipated exotic machines with complex behavior were discovered. These exotic machines show that it is quite difficult to estimate the number of states needed to produce a given behavior, and hence subjective estimates of computational or operational complexity may be poor approximations of the true complexity.

This work can also be utilized to give upper and lower bounds on Chaitan's probability that a random Turing machine halts, given an initially blank tape.

In the concluding section of the paper we give advice as to what to do if aliens attack and demand to know specific values of the Busy Beaver number. This advice still seems correct.

Keywords: Turing machine, halting problem, Tibor Rado, emergent systems behavior, complex systems, Busy Beaver problem, halting probability, Chaitan's number, undecidable, computer-assisted proof

Complete paper: it appears in Physica D 42 (1990), pp. 85-98, reprinted in Emergent Computation, S. Forrest, ed., MIT Press, 1991, pp. 85-98. It is based on work in ``The Busy Beaver Problem'', Rona Kopp, M.A. thesis, SUNY Binghamton, Math. Sci., 1981.

Copyright © 2008-2024 Quentin F. Stout