Sequences: Difference between revisions
Jump to navigation
Jump to search
m (Add link to OEIS Wiki page on Busy Beavers) |
m (Fix sequence names) |
||
| Line 36: | Line 36: | ||
|[[Busy Beaver Functions#Max Shift Function S(n, m)|Max Shift Function]] | |[[Busy Beaver Functions#Max Shift Function S(n, m)|Max Shift Function]] | ||
|S(n, m) | |S(n, m) | ||
|The maximal number of steps that an n-state Turing machine can make on an initially blank tape before eventually halting. | |The maximal number of steps that an n-state, m-symbol Turing machine can make on an initially blank tape before eventually halting. | ||
|[[Main Page|see the Main Page]] | |[[Main Page|see the Main Page]] | ||
|[[oeis:A060843|A060843]] | |[[oeis:A060843|A060843]] | ||
| Line 42: | Line 42: | ||
|[[Busy Beaver Functions#Max Score Function Σ(n, m)|Max Score Function]] | |[[Busy Beaver Functions#Max Score Function Σ(n, m)|Max Score Function]] | ||
|Σ(n, m) | |Σ(n, m) | ||
|Maximal number of 1's that an n-state Turing machine can print on an initially blank tape before halting. | |Maximal number of 1's that an n-state, m-symbol Turing machine can print on an initially blank tape before halting. | ||
| | | | ||
|[[oeis:A028444|A028444]] | |[[oeis:A028444|A028444]] | ||
| Line 65: | Line 65: | ||
|- | |- | ||
| | | | ||
|# | |#S(n, m) | ||
|The number of programs | |The number of programs that halt after exactly S(n,m) steps ([[Busy Beaver Functions#Max Shift Function S(n, m)|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 | |The number of programs that halt with Σ(n, m) 1's on the tape ([[Busy Beaver Functions#Max Score Function Σ(n, m)|Max Score]]) for each n of a given m (including all equivalent transformations) | ||
| | | | ||
| - | | - | ||
Revision as of 16:09, 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, 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 | |
| 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 | - |
| #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) | - | ||
| 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 information on sequences, see the OEIS Wiki: Busy Beaver Numbers, OEIS search: "busy beaver" and OEIS Wiki: "related to busy beaver"