Busy beaver function

From Cantor's Attic
Revision as of 10:54, 13 July 2019 by Trixie Wolf (Talk | contribs) (Added a link to fast-growing hierarchy page.)

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.


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





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


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


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.