Busy Beaver

In computability theory, a busy beaver (from the colloquial expression for an 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".

Read more about Busy Beaver:  The Busy Beaver Game, The Busy Beaver Function Σ, Non-computability of Σ, Σ, Complexity and Unprovability, Max Shifts Function, Known Values, Generalizations, Applications, Proof For Uncomputability of S(n) and Σ(n), Examples of Busy Beaver Turing Machines, Exact Values and Lower Bounds For Some S(n, m) and Σ(n, m)

Famous quotes containing the words busy and/or beaver:

    She isn’t harassed. She’s busy, and it’s glamorous to be busy. Indeed, the image of the on- the-go working mother is very like the glamorous image of the busy top executive. The scarcity of the working mother’s time seems like the scarcity of the top executive’s time.... The analogy between the busy working mother and the busy top executive obscures the wage gap between them at work, and their different amounts of backstage support at home.
    Arlie Hochschild (20th century)

    On the top of the Crumpetty Tree
    The Quangle Wangle sat,
    But his face you could not see,
    On account of his Beaver Hat.
    Edward Lear (1812–1888)