Sequences: Difference between revisions
Jump to navigation
Jump to search
m (Add more sequences) |
(Move halt-free sequence to computable) |
||
| Line 16: | Line 16: | ||
| | | | ||
|[[oeis:A052200|A052200]] | |[[oeis:A052200|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. | |||
| | |||
|[[oeis:A337025|A337025]] | |||
|} | |} | ||
| Line 29: | Line 34: | ||
![[oeis:|OEIS]] sequence | ![[oeis:|OEIS]] sequence | ||
|- | |- | ||
|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 Turing machine can make on an initially blank tape before eventually halting. | ||
| Line 35: | Line 40: | ||
|[[oeis:A060843|A060843]] | |[[oeis:A060843|A060843]] | ||
|- | |- | ||
|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 Turing machine can print on an initially blank tape before halting. | ||
| Line 52: | Line 57: | ||
| | | | ||
|[[oeis:A337805|A337805]] | |[[oeis:A337805|A337805]] | ||
|- | |- | ||
|[[Beeping Busy Beaver]] | |[[Beeping Busy Beaver]] | ||
| Line 63: | Line 62: | ||
|The latest possible step that any 2-symbol TM with n states exits a chosen state finitely many times | |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 | |BBB(1)=1, BBB(2)=6 | ||
| | | - | ||
|- | |- | ||
|Flocking Flycatcher | |Flocking Flycatcher | ||
Revision as of 12:50, 10 July 2024
This page lists sequences related to the Busy Beaver functions.
This table is 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 | - |
| Flocking Flycatcher | FF(n) | The number of programs with n states that halt after exactly BB(n) steps (Max Shift) for each n (including all equivalent transformations) | FF(1)=32, FF(2)=40, FF(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 | - |
For more related sequences, see OEIS search: "busy beaver" and OEIS Wiki: "related to busy beaver"