Busy beaver¶

The n-state busy beaver game consists of finding the longest-running or highest-scoring Turing machine which has n states and eventually halts.

Version: v1 · 2026-09-28 · History
Domain-specific #: 8303
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomain: Computability Theory → Computer Science & Software Engineering

Core Idea¶

Busy beaver is treated here as the recurring computability theory identity summarized by this source-grounded definition: The n-state busy beaver game consists of finding the longest-running or highest-scoring Turing machine which has n states and eventually halts. In theoretical computer science, the busy beaver game aims to find a terminating program of a given size that (depending on definition) either produces the most output possible, or runs for the longest number of steps. Since an endlessly looping program producing infinite output or running for infinite time is easily conceived, such programs are excluded from the.

How would you explain it like I'm…

The Busiest Little Robot

Imagine a tiny toy robot that follows only a few rules, and it has to stop sometime. The busy beaver game asks: out of all the robots with that many rules, which one keeps busy the longest, or makes the most marks, before it finally stops? Robots that never stop don't count.

Longest-Running Stopping Machine

The busy beaver game is a puzzle about very simple pretend computers called Turing machines, which move along a long strip of tape reading and writing marks. You pick a size, like "machines with 3 states," where each state is a small set of rules, and look at every machine of that size. Some of them run forever, and those are thrown out. Among the ones that eventually stop, the winner is the one that runs for the most steps, or the one that writes the most 1s on the tape.

Maximal Halting Turing Machine Game

The busy beaver game is a problem from computability theory, the study of what computers can and cannot do in principle. It uses Turing machines, an early mathematical model of a computer made of an infinite tape plus a finite set of states that serve as its program. For each number of states n, you look only at machines that eventually halt, since a machine that loops forever could trivially run or write without end. Among those halting n-state machines, the busy beaver is the one that runs for the most steps, or, under the other version of the game, writes the most 1s (its "score"). The concept isn't just about long-running programs; it is specifically about the best halting machine for a fixed size.

The busy beaver game, a problem in computability theory, asks for the halting program of a given size that produces the most output or runs the longest. The programs are n-state Turing machines: each has an infinite tape and a finite set of states serving as its source code. "Most output" is defined as writing the largest number of 1s on the tape (the machine's score), and "longest" as taking the greatest number of steps before halting. Non-halting machines are excluded because infinite output or infinite running time would be trivially achievable. The n-state busy beaver game is therefore to find, among all n-state Turing machines that eventually halt, the longest-running or highest-scoring one. The halting requirement is essential: an instance of the concept must preserve both the fixed state count and the restriction to machines that terminate, not just the idea of a machine that runs for a long time.

Scope of Application¶

Functions. The function BB(n) has been defined to be either of these functions, so that notation is not used in this article.
ApplicationsOpen mathematical problems. The busy beaver functions Σ(n) and S(n) can be used to prove theorems in mathematics.
Technical definition. "Running" the machine consists of starting in the starting state, with the current tape cell being any cell of a blank (all-0) tape, and then iterating the transition function until the.
Functions. In his original 1962 paper, Radó defined two functions related to the busy beaver game: the score function Σ(n) and the shifts function S(n).
Functions. He proved that both of these functions were noncomputable, because they each grew faster than any computable function.

Clarity¶

A clear use of Busy beaver names the carrier, the operative relation, and the conditions under which the source treats the identity as present. The minimal definition is The n-state busy beaver game consists of finding the longest-running or highest-scoring Turing machine which has n states and eventually halts.

Manages Complexity¶

Busy beaver compresses multiple computability theory details into a stable diagnostic relation. The source shows both the central mechanism—depending on definition, it either attains the highest score (denoted by Σ(n) ), or runs for the longest time (S(n)), among all other possible n-state competing Turing machines.—and the practical consequence—(Given any n-state busy beaver, another is obtained by merely changing the shift direction in a halting transition.

Abstract Reasoning¶

Type the carrier. Identify the computability theory entities to which the claim applies.
State the relation. Use the source-grounded identity: The n-state busy beaver game consists of finding the longest-running or highest-scoring Turing machine which has n states and eventually halts.
Check operation and conditions. Both take a number of Turing machine states n and output the maximum score attainable by a Turing machine of that number of states by some measure.
Demand recognition evidence.

Knowledge Transfer¶

Within the home domain. Knowledge about Busy beaver transfers literally when a new case preserves the same carrier type, relation, and recognition test. The function BB(n) has been defined to be either of these functions, so that notation is not used in this article. The busy beaver functions Σ(n) and S(n) can be used to prove theorems in mathematics. Beyond the home domain. No canonical parent is asserted for Busy beaver.

Relationships to Other Abstractions¶

Current abstraction Busy beaver Domain-specific

Parents (1) — more general patterns this builds on

Busy beaver presupposes Halting Problem Domain-specific

The Busy Beaver function is defined as an extremum over halting Turing machines, so its uncomputability presupposes and is a direct consequence of the Halting Problem's undecidability.

Hierarchy path (1) — routes to 1 parentless root

Busy beaver → Halting Problem → Diagonal Impossibility → Reflexivity (Self-Reference)

Neighborhood in Abstraction Space¶

Busy beaver sits in a moderately populated region (45^th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Computation Models & Complexity Classes (37 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08