Busy beaver

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 Non-Computable 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