Sequences
This page lists sequences related to the Busy Beaver functions.
These tables are incomplete, you can help by adding missing items. If you add a value, please add a reference to a paper or code with which it was computed/proved if possible.
If the "canonical" values of a sequence are maintained on another Wiki page, please link to that, instead of replicating them here.
Computable Sequences
| Sequence Name | Description | Values | OEIS sequence |
|---|---|---|---|
| 2-symbol TM count | Number of n-state, 2-symbol, d+ in {LEFT, RIGHT}, 5-tuple (q, s, q+, s+, d+) (halting or not) Turing machines. | A052200 | |
| Number of n-state 2-symbol halt-free TMs | A Turing machine is halt-free if none of its instructions lead to the halt state. | A337025 | |
| Lazy Beaver | The smallest positive number of steps a(n) such that no n-state Turing machine halts in exactly a(n) steps on an initially blank tape. | LB(1)=2, LB(2)=7, LB(3)=22, LB(4)=72, LB(5)=427 | A337805 |
Noncomputable Sequences
The following sequences depend on the specific behavior of programs.
TODO: group by position in arithmetical hierarchy
| Sequence Name | Symbol | Description | Values | OEIS sequence |
|---|---|---|---|---|
| Max Shift Function | S(n, m) | The maximal number of steps that an n-state, m-symbol Turing machine can make on an initially blank tape before eventually halting. | see the Main Page | A060843 |
| Max Score Function | Σ(n, m) | Maximal number of 1's that an n-state, m-symbol Turing machine can print on an initially blank tape before halting. | A028444 | |
| BB_SPACE(n,m) | Maximum number of memory cells visited by a halting Turing machine with n states and m symbols starting from all-0 memory tape | BB_SPACE(1,2)=2, BB_SPACE(2,2)=4, BB_SPACE(3,2)=7, BB_SPACE(4,2)=16 | - | |
| Number of n-state Turing machines which halt. | A004147 | |||
| Beeping Busy Beaver | BBB(n) | The latest possible step that any 2-symbol TM with n states exits a chosen state finitely many times | see Beeping Busy Beaver#Results | - |
| Blanking Beavers | The maximum number of steps that an n-state m-symbol Turing machine can make on an initially blank tape until it is blank again (halting or not) | - | ||
| BB_clean | The maximum number of steps that an n-state 2-symbol Turing machine can make on an initially blank tape until it halts on a blank tape | (see comments #75 and #77 here) | ||
| BB_ones | The maximum number of 1's that an n-state 2-symbol Turing machine can make in a row, before halting on a 0 next to it | |||
| Size of the Runtime Spectrum | The number of distinct runtimes for a machine with a given number of symbols, for increasing number of states | see "The Spectrum of Runtimes" here (.pdf) | ||
| #S(n, m) | The number of programs that halt after exactly S(n,m) steps (Max Shift) for each n of a given m (including all equivalent transformations) | #S(1,2)=32, #S(2,2)=40, #S(3,2)=16 | - | |
| #Σ(n, m) | The number of programs that halt with Σ(n, m) 1's on the tape (Max Score) for each n of a given m (including all equivalent transformations) | #Σ(1,2)=16, #Σ(2,2)=4, #Σ(3,2)=40 | - | |
| #BB_SPACE(n,m) | The number of programs that visited the most number of tape cells for a given (n,m) (including all equivalent transformations) | #BB_SPACE(1,2)=32, #BB_SPACE(2,2)=24, #BB_SPACE(3,2)=48 | - | |
| The number of non-halting programs with n states which reach infinitely many tape cells | - | |||
| The average number of states that are reached infinitely many times, among all non-halting turing machines with n states | - |
More possibilities
- The number of distinct final tape states of halting machines with n states and m symbols, for some definition of "distinct"
- Any of the above for machines with more than one tape, or tapes with more dimensions (2d grid, 3d, n-d...)
- Machines with a finite tape, or a circular one of a certain length
Further information
For more information on sequences, see the OEIS Wiki: Busy Beaver Numbers, OEIS search: "busy beaver" and OEIS Wiki: "related to busy beaver"