Sequences
This page lists sequences related to the Busy Beaver functions.
This table is incomplete, you can help by adding missing items.
| Sequence Name | Description | Values | OEIS sequence |
|---|---|---|---|
| Max Shift Function S(n, m) | The maximal number of steps that an n-state 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 Turing machine can print on an initially blank tape before halting. | A028444 | |
| 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 Turing machines which halt. | A004147 | ||
| 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. | A337805 | |
| The number of programs with n states that halt after exactly BB(n) steps (Max Shift) for each n (including all equivalent transformations) | - | ||
| The number of programs that maximize the number of non-zero cells at the time of halting (Max Score) for each n (including all equivalent transformations) | - | ||
| The number of distinct final tape states of halting machines with n states | |||
| The number of non-halting programs with n states which reach infinitely many tape cells |
For more related sequences, see OEIS search: "busy beaver" and OEIS Wiki: "related to busy beaver"