Busy beaver

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.

All machines are started on initially blank tapes and those that do not halt are not candidates.

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 log₂ x states to write x to the tape. Since a constant plus log₂ x is smaller than x, for any large enough x. The busy beaver function of a constant plus log₂ 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 10⁸⁶⁵ (that is a 1 with 865 zeros) ones produced, using over 10¹⁷³⁰ 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.