- Σ(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 log_{2} *x* states to write *x* to the tape. Since a constant plus log_{2} *x* is smaller than *x*, for any large enough *x*. The busy beaver function of a constant plus log_{2} *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^{865} (that is a 1 with 865 zeros) ones produced, using over 10^{1730} 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.