Sequences: Difference between revisions
Jump to navigation
Jump to search
m (add new sequence) |
m (Grammar fix) |
||
| Line 1: | Line 1: | ||
This page lists sequences related to the Busy Beaver functions. | This page lists sequences related to the Busy Beaver functions. | ||
These tables are incomplete, you can help by adding missing items. | |||
If the "canonical" values of a sequence are maintained on another Wiki page, please link to that, instead of replicating them here. | If the "canonical" values of a sequence are maintained on another Wiki page, please link to that, instead of replicating them here. | ||
| Line 92: | Line 92: | ||
|The average number of states that are reached infinitely many times, among all non-halting turing machines with n states | |The average number of states that are reached infinitely many times, among all non-halting turing machines with n states | ||
| | | | ||
| | | - | ||
|} | |} | ||
For more related sequences, see [https://oeis.org/search?q=busy+beaver OEIS search: "busy beaver"] and [[oeis:wiki/Index_to_OEIS:_Section_Br#beaver|OEIS Wiki: "related to busy beaver"]] | For more related sequences, see [https://oeis.org/search?q=busy+beaver OEIS search: "busy beaver"] and [[oeis:wiki/Index_to_OEIS:_Section_Br#beaver|OEIS Wiki: "related to busy beaver"]] | ||
Revision as of 13:29, 10 July 2024
This page lists sequences related to the Busy Beaver functions.
These tables are incomplete, you can help by adding missing items.
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 |
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 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 | |
| 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 | ||
| Beeping Busy Beaver | BBB(n) | The latest possible step that any 2-symbol TM with n states exits a chosen state finitely many times | BBB(1)=1, BBB(2)=6 | - |
| #BB(n) | The number of programs with n states that halt after exactly BB(n) steps (Max Shift) for each n (including all equivalent transformations) | #BB(1)=32, #BB(2)=40, #BB(3)=16 | - | |
| 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 | - | |||
| The average number of states that are reached infinitely many times, among all non-halting turing machines with n states | - |
For more related sequences, see OEIS search: "busy beaver" and OEIS Wiki: "related to busy beaver"