Busy beaver function

From Cantor's Attic
Jump to: navigation, search

The Busy Beaver function, also known as Rado's Sigma function is a function from computability theory. Denoted $\Sigma(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 $\Sigma(n)$ for an arbitrary n.

Values

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

$\Sigma(1)=1$

$\Sigma(2)=4$

$\Sigma(3)=6$

$\Sigma(4)=13$

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

$\Sigma(5)>4098$

$\Sigma(6)>3.514 * 10^{18276}$

$\Sigma(7)>10^{10^{10^{10^{18705352}}}}$

Beyond these numbers, the Busy Beaver function grows phenomenally fast. It has been shown that $\Sigma(18)$ is larger than Graham's number. The growth rate of the function is comparable to the Church-Kleene ordinal in the fast-growing hierarchy.