Sequences: Difference between revisions
Jump to navigation
Jump to search
m (Split table into computable and noncomputable sequences) |
m (Add more sequences) |
||
| Line 20: | Line 20: | ||
=== Noncomputable Sequences === | === Noncomputable Sequences === | ||
The following sequences depend on the specific behavior of programs. | The following sequences depend on the specific behavior of programs. | ||
TODO: group by position in arithmetical hierarchy | |||
{| class="wikitable" | {| class="wikitable" | ||
!Sequence Name | !Sequence Name | ||
!Symbol | |||
!Description | !Description | ||
!Values | !Values | ||
![[oeis:|OEIS]] sequence | ![[oeis:|OEIS]] sequence | ||
|- | |- | ||
|Max Shift Function S(n, m) | |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. | |The maximal number of steps that an n-state 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]] | ||
|- | |- | ||
|Max Score Function Σ(n, m) | |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. | |Maximal number of 1's that an n-state Turing machine can print on an initially blank tape before halting. | ||
| | | | ||
|[[oeis:A028444|A028444]] | |[[oeis:A028444|A028444]] | ||
|- | |- | ||
| | |||
| | | | ||
|Number of n-state Turing machines which halt. | |Number of n-state Turing machines which halt. | ||
| Line 42: | Line 48: | ||
|- | |- | ||
|Lazy Beaver | |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. | |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. | ||
| | | | ||
|[[oeis:A337805|A337805]] | |[[oeis:A337805|A337805]] | ||
|- | |- | ||
|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]] | |||
|- | |||
|[[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 ([[Busy Beaver Functions#Max Shift Function S(n, m)|Max Shift]]) for each n (including all equivalent transformations) | |The number of programs with n states that halt after exactly BB(n) steps ([[Busy Beaver Functions#Max Shift Function S(n, m)|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 ([[Busy Beaver Functions#Max Score Function Σ(n, m)|Max Score]]) for each n (including all equivalent transformations) | |The number of programs that maximize the number of non-zero cells at the time of halting ([[Busy Beaver Functions#Max Score Function Σ(n, m)|Max Score]]) for each n (including all equivalent transformations) | ||
| Line 56: | Line 77: | ||
| - | | - | ||
|- | |- | ||
| | |||
| | | | ||
|The number of distinct final tape states of halting machines with n states | |The number of distinct final tape states of halting machines with n states | ||
| Line 61: | Line 83: | ||
| - | | - | ||
|- | |- | ||
| | |||
| | | | ||
|The number of non-halting programs with n states which reach infinitely many tape cells | |The number of non-halting programs with n states which reach infinitely many tape cells | ||
Revision as of 12:46, 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 |
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 | ||
| 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 | ||
| 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"