Contents

Busy beaver

A busy beaver (from the colloquial expression for "industrious person") is a Turing machine that, when given an initially empty tape (a string of only 0's), does a lot of work, then halts. This function was discovered and its properties proved in 1952, by Tibor Rado[?]. There are two main 'categories':

  1. Sigma(n): the largest number of 1's printable by an n-state machine before halting, and
  2. 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.

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 to the Sigma 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.

External links: