In computability theory, a busy beaver (from the colloquial expression for "industrious person") is a Turing machine that, when given an initially empty (binary?) tape (a string of only 0's), does a lot of work, then halts. The functions defined below, called busy beaver functions, were introduced and their properties proved in 1952, by Tibor Rado. There are two main 'categories':
- Σ(n): the largest number of 1's printable by an n-state machine before halting, and
- S(n): the largest number of steps taken by an n-state machine before halting.
Both of these functions are uncomputable in general. That they grow faster than any computable functions can be easily shown. Take any computable function f of x. Take a function g that writes that many 1's. We can take 22 states to make a Turing complete Turing machine, add a constant number of states to write the function g to the tape, and add log2 x states to write x to the tape. Since a constant plus log2 x is smaller than x, for any large enough x. The busy beaver function of a constant plus log2 x will be at least as large as f of x, therefore the busy beaver function has grown faster.
A computer which could somehow solve the halting problem would be capable of computing the uncomputable busy beaver function.
Even with only a few states, a Busy Beaver can do very much. At the moment the record 6-state Busy Beaver is over 10865 (that is a 1 with 865 zeros) ones produced, using over 101730 steps.
There is an analog to the Σ function for Minsky machines, namely the largest number which can be present in any register on halting, for a given number of instructions. This is a consequence of the Church-Turing thesis.
Come on, give us some examples of a two state or three stage busy beaver.
These may or may not generate the biggest S(n)...
First state is state A.
1-state:
{| | ||A |- |1 ||N/A |- |0 ||1-Halt |}
Result (starts here, goes to here):
0 0 1 0 0
2-state:
{| | ||A ||B |- |1 ||1B-Left ||1-Halt |- |0 ||1B-Right||1A-Left |}
Result:
0 0 1 1 1 1 0 0
External links:
- The page of Heiner Marxen who with Jürgen Bontrock found the above mentioned record for a 6-state turing machine.