
related topics 
{math, number, function} 
{system, computer, user} 
{game, team, player} 

In computability theory, a busy beaver (from the colloquial expression for "industrious person") is a Turing machine that attains the maximum "operational busyness" (such as measured by the number of steps performed, or the number of nonblank symbols finally on the tape) among all the Turing machines in a certain class. The Turing machines in this class must meet certain design specifications and are required to eventually halt after being started with a blank tape.
A busy beaver function quantifies these upper limits on a given type of "operational busyness", and is a noncomputable function. In fact, a busy beaver function can be shown to grow faster asymptotically than does any computable function. The concept was first introduced by Tibor Radó as the "busy beaver game" in his 1962 paper, "On NonComputable Functions".
Contents
Full article ▸


related documents 
Control flow 
Relational database 
AWK 
Imaginary unit 
Multiplication 
Finite set 
Exponentiation by squaring 
P = NP problem 
Quadratic equation 
General linear group 
Dylan (programming language) 
Communication complexity 
Riemannian manifold 
Semidirect product 
Lie algebra 
Category theory 
Monoid 
Exponential function 
Interpolation 
Polyomino 
Operator 
Stochastic process 
Set (mathematics) 
Reference counting 
Metric space 
Dirac delta function 
Multiplication algorithm 
Sorting algorithm 
Taylor's theorem 
Vacuous truth 
