Busy beaver function

From Cantor's Attic
Revision as of 04:08, 8 May 2014 by Onewell (Talk | contribs) (Busy Beaver Function)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

The Busy Beaver function, also known as Rado's Sigma function is a function from computability theory. Denoted Σ(n) or BB(n), it is defined as the maximum number of ones that can be written (in the finished tape) with an n-state, 2-color Turing machine, starting from a blank tape, before halting. It is one of the fastest-growing functions ever arising out of professional mathematics. The Busy Beaver function is an uncomputable function meaning that no algorithm that terminates after a finite number of steps can compute Σ(n) for an arbitrary N.

Values

The first four vales of the Busy Beaver function have been proven to be as follows:

Σ(1) = 1 Σ(2) = 4 Σ(3) = 6 Σ(4) = 13

Values beyond 4 are unknown however the following bounds have been discovered:

Σ(5) > 4098 Σ(6) > 3.514 * 10^18276

Beyond these numbers, the Busy Beaver function grows phenomenally fast. It has been shown that Σ(23) is larger than Grahams number. The growth rate of the function is comparable to the Church-Kleene ordinal in the fast growing hierarchy.