Cognitive Scaffold

Preparing your thinking workspace

arrow_back_ios_new
MENTAL MODEL · M0181

The Busy Beaver

The Busy Beaver
SystemsHigh supportSystems Theory
Included
account_tree

Version 1.0.0 · Updated 2026-07-28

CORE DEFINITION

In computer science, the Busy Beaver is a terminating program that, given a parameter, seeks the maximum possible output. The Busy Beaver game involves designing a terminating Turing machine that outputs only 0 or 1, aiming to output as many 1s as possible on a tape. The two-state Busy Beaver game has the following two rules: The Turing machine includes two states in addition to the halt state. The tape is initially all zeros. The player must design a state transition table that outputs the maximum number of 1s while also ensuring the machine terminates. A Turing machine that wins the n-state Busy Beaver game is called the nth Busy Beaver, denoted BB-n (BB stands for Busy Beaver). BB-n is the machine among all n-state Turing machines that outputs the most 1s. For example, BB-2 can output 4 ones in 6 state transitions. The Busy Beaver game was proposed by Hungarian mathematician Tibor Radó in his 1962 paper 'On Non-Computable Functions'.

SCAFFOLDING EFFECT

psychology

Reduce cognitive load

In computer science, the Busy Beaver is a terminating program that, given a parameter, seeks the maximum possible output. The Busy Beaver game involves designing a terminating Turing machine that outputs only 0 or 1, aiming to output as many 1s as possible on a tape. The two-state Busy Beaver game has the following two rules: The Turing machine includes two states in addition to the halt state. The tape is initially all zeros. The player must design a state transition table that outputs the maximum number of 1s while also ensuring the machine terminates.

anchor

Anchor fast decisions

The Busy Beaver problem: among Turing machines with a given number of states, find the machine that writes the most 1s (or takes the most steps) before halting. Its function grows faster than any computable function, revealing the boundaries of computability and the unsolvability of the halting problem.

MINIMUM ACTION

In progress 0/4

Practice this model in one real situation:

Check to track your progress (stored locally)
Learning progress0%
account_treeGenealogyexpand_more
menu_bookReferencesexpand_more

Source support: Explicit

  • link
    zh.wikipedia.orghttps://zh.wikipedia.org/wiki/%E5%BF%99%E7%A2%8C%E7%9A%84%E6%B5%B7%E7%8B%B8ZH · Explicit
    verified

RELATED MODELS

Related model

Wirth's Law

Wirth's law is an adage on computer performance which states that software is getting slower more rapidly than hardware is becoming faster.

arrow_forwardRelated model

Hyrum's Law

An application programming interface (API) is a connection between computers or between computer programs. It is a type of software interface, offering a service to other pieces of software. A documen

arrow_forwardRelated model

Coriolis Force

The Coriolis force is an inertial-force term needed to describe motion in a rotating reference frame, involving the cross product of frame angular velocity and relative object velocity.

arrow_forward