Explore Busy Beaver Values
Choose the number of non-halting states and the Busy Beaver function you want to explore.
What Is the Busy Beaver Function?
The Busy Beaver functions measure the maximum behavior of small halting Turing machines. A Turing machine is a mathematical model of computation that reads and writes symbols on a tape according to a finite set of rules.
For a fixed number of states and symbols, consider all machines that eventually halt when started on a blank tape. The Busy Beaver functions identify the maximum output or running time among those halting machines.
The two main Busy Beaver functions
S(n) = maximum number of steps taken by a halting n-state machine
Both functions depend on the chosen Turing-machine model. This explorer uses a common model with two tape symbols, a blank initial tape and n non-halting states.
Known Busy Beaver Values
The following table shows exact values where established and distinguishes them from unresolved cases.
| States (n) | Σ(n): Maximum ones | S(n): Maximum steps | Status |
|---|---|---|---|
| 1 | 1 | 1 | Exact values known |
| 2 | 4 | 6 | Exact values known |
| 3 | 6 | 21 | Exact values known |
| 4 | 13 | 107 | Exact values known |
| 5 | Unknown | Unknown | Exact values unknown |
| 6 | Unknown | Unknown | Exact values unknown |
The five- and six-state entries are not exact results. Their exact values are not established; lower bounds can still be proved by exhibiting machines that attain those bounds.
Known Lower Bounds
A lower bound proves that a Busy Beaver value is at least a particular number. It does not establish that the number is the exact maximum.
| States | Σ(n) lower bound | S(n) lower bound |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 4 | 6 |
| 3 | 6 | 21 |
| 4 | 13 | 107 |
| 5 | At least 4098 | At least 47,176,870 |
| 6 | At least 1,000,000,000 | At least 10^36 |
Lower-bound records depend on the precise machine convention and on the published machine constructions. Treat the displayed five- and six-state figures as illustrative conservative records, not as exact values or a complete current record database.
How Does a Busy Beaver Machine Work?
A Turing machine has a finite set of states, a tape containing symbols and a head that reads and writes one cell at a time. Each transition specifies:
- Which symbol to write.
- Whether to move left or right.
- Which state to enter next, or whether to halt.
A Busy Beaver machine is a halting machine that achieves the maximum score for its state count under the selected scoring rule.
A simplified example
A simple one-state machine can print one 1 and halt. This illustrates the basic idea behind Σ(1).
Why Is the Busy Beaver Function So Important?
The Busy Beaver function is a central example in computability theory because it grows faster than every computable function.
It is not computable
There is no general algorithm that takes an arbitrary state count n and always returns the exact value of S(n) or Σ(n). If such an algorithm existed, it would provide a way to solve the halting problem.
It grows faster than computable functions
For every total computable function f, the Busy Beaver functions eventually exceed f, under the standard definitions and machine conventions. This makes them important examples of extremely rapid growth.
Small machines can behave unexpectedly
Even machines with relatively few states can run for extraordinarily long periods before halting. Determining whether a particular machine eventually halts can be much harder than simply simulating it for a long time.
Busy Beaver and Other Large-Number Functions
| Function or system | How it grows | Computable? |
|---|---|---|
| Exponentiation | Repeated multiplication | Yes |
| Tetration | Repeated exponentiation | Yes, for finite inputs under a specified convention |
| Ackermann function | Nested recursion | Yes |
| Fast-growing hierarchy | Ordinal-indexed function iteration | Depends on the specified effective notation and input domain |
| Busy Beaver function | Maximum behavior of halting machines | No |
The Busy Beaver function is not merely another computable fast-growing hierarchy level. Its non-computability is a fundamental distinction.
Related Large Number Calculators
Frequently Asked Questions
What does BB(n) mean?
BB(n) is a general informal label for a Busy Beaver value. It is important to specify whether it means Σ(n), the maximum number of ones printed, or S(n), the maximum number of steps before halting.
What is Σ(n)?
Σ(n) is the maximum number of 1s that a halting n-state machine can leave on its initially blank tape, under a specified machine model.
What is S(n)?
S(n) is the maximum number of steps taken before halting by any halting n-state machine under the specified model.
Are all Busy Beaver values known?
No. Only some small values have been established exactly. For larger state counts, researchers may know lower bounds without knowing the exact maximum.
Why can't the Busy Beaver function be calculated by an algorithm?
An algorithm that computed all exact Busy Beaver values would solve the general halting problem, which is impossible. The function is therefore non-computable.
Does an unknown value mean the machine does not halt?
No. An unknown Busy Beaver value means the exact maximum has not been established. Individual machines may be proven to halt or proven not to halt.
Can a Busy Beaver value be infinite?
No. For each fixed finite number of states, there are finitely many machines in the specified model. At least one halting machine exists, and the maximum over the halting machines is finite.