Improved Bounds for Functions Related to Busy Beavers

Consider Turing machines that use a tape infinite in both directions, with the tape alphabet {0,1} . Rado's busy beaver function, ones(n), is the maximum number of 1's such a machine, with n states, started on a blank (all-zero) tape, may leave on its tape when it halts. The function ones(n) is non-computable; in fact, it grows faster than any computable function. Other functions with a similar nature can be defined also. All involve machines of n states, started on a blank tape. The function time(n) is the maximum number of moves such a machine may make before halting. The function num(n) is the largest number of 1's such a machine may leave on its tape in the form of a single run; and the function space(n) is the maximum number of tape squares such a machine may scan before it halts. This paper establishes new bounds on these functions in terms of each other. Specifically, we bound time(n) by num(n+o(n)), improving on the previously known bound num(3n+6) . This result is obtained using a kind of ``self-interpreting'' Turing machine. We also improve on the trivial relation space(n) ≤ time(n) , using a technique of counting crossing sequences.

Authors and Affiliations

1. The Academic College of Tel-Aviv-Yaffo, 4 Antokolski St., amirben@mta.ac.il, 64044 Tel Aviv, Israel, IL

   A. M. Ben-Amram

2. The University of Stuttgart, Institute of Computer Science, petersen@informatik.uni-stuttgart.de, Breitwiesenstr. 20—22, D-70565 Stuttgart, Germany, DE

   H. Petersen

Received July 18, 2000, and in revised form October 10, 2001. Online publication February 20, 2002.

Reprints and permissions