Rona Machlin

Quentin F. Stout

Computer Science and Engineering, University of Michigan

**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 |