Non-halting Turing machine: Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
← Older edit
VisualWikitext
Icy (talk | contribs)
156 edits
→Regular (non-chaotic): added 1RB0RC_1LB1LD_0RA0LD_1LA1RC
Polygon (talk | contribs)
1,249 edits
→Records: organised champions into tables and added BBS(5,2)
 
(21 intermediate revisions by 4 users not shown)
Line 3: Line 3:
The crux of the [[Busy Beaver function|Busy Beaver]] problem, of finding BB(''n'', ''k'') for a given ''n'' and ''k'', is to prove that all non-halting Turing machines with ''n'' states and ''k'' symbols are, in fact, non-halting.
The crux of the [[Busy Beaver function|Busy Beaver]] problem, of finding BB(''n'', ''k'') for a given ''n'' and ''k'', is to prove that all non-halting Turing machines with ''n'' states and ''k'' symbols are, in fact, non-halting.


The zoology of non-halting Turing machines is extremely rich. See [[Translated cycler]], [[Bouncer]], [[Bell]], [[Counter]], [[Shift overflow counter]], [[Shift overflow bouncer counter]] for a sample. In this page, we provide a detailed zoology for some low numbers of states and symbols.  
The zoology of non-halting Turing machines is extremely rich. See [[Translated cycler]], [[Bouncer]], [[Bell]], [[Counter]], [[Fractal]], [[Shift overflow counter]], [[Shift overflow bouncer counter]] for a sample. In this page, we provide a detailed zoology for some low numbers of states and symbols.  


== Zoology ==
== Zoology ==
Machines are enumerated in [[TNF-1RB]], and we exclude halting machines. In particular, a transition is defined if and only if it is reachable; unreachable transitions are undefined. This avoids duplicates.
Machines are enumerated in [[TNF-1RB]], and we exclude halting machines. In particular, a transition is defined if and only if it is reachable; unreachable transitions are undefined. This avoids duplicates.


For convenience, Turing machines are displayed here in [[lexical normal form]].
For convenience, Turing machines are displayed here in [[Turing machine#Standard text format|standard text format]].
 
=== n × 1 ===
There are no TNF-1RB machines with just one symbol, as they cannot have "print 1" in their instructions.
 
=== 1 × m ===
There are no non-halting TNF-1RB machines with 1 state and any amount of symbols, as the transition to state B already is undefined and leads to halting.


=== 2 × 2 ===
=== 2 × 2 ===
Line 74: Line 80:
* {{TM|1RB1LA_0LA1RC_1LB0RB}}, a translating binary counter.
* {{TM|1RB1LA_0LA1RC_1LB0RB}}, a translating binary counter.
|-
|-
|[[Cubic bell]]
|[[Bell|Cubic bell]]
|10
|10
|
|
Line 87: Line 93:


=== 4 × 2 ===
=== 4 × 2 ===
There are 2,744,516 TNF-1RB machines with 4 states and 2 symbols, with the following breakdown. This breakdown is not complete due the chaotic Turing machines. These are the irregular bells, spaghetti, and chaotic counters. These are informal names for chaotic behaviors which escape analysis, and such may well become a translated cycler, or more rarely, a bouncer, after a large number of steps.
There are 2,744,516 TNF-1RB machines with 4 states and 2 symbols, with the following breakdown. This breakdown is not exact due to the presence of chaotic Turing machines which defy straightforward analysis and may eventually transition into a translated cycler or, more rarely, a bouncer, after a very large number of steps.


==== Regular (non-chaotic) ====
==== Regular (non-chaotic) ====
Line 99: Line 105:
|≥2,253,849
|≥2,253,849
|
|
* {{TM|1RB0LA_0RC1RD_1LD0RB_1LA1RB}}, the current period record holder, with a period of 212,081,736. Before phasing into a translated cycle, this machine appears to be a [[spaghetti]].
* {{TM|1RB0LA_0RC1RD_1LD0RB_1LA1RB}}, the current period record holder, with a period of 212,081,736. Before phasing into a translated cycle, this machine appears to be a spaghetti (described in a later subsubsection).
* {{TM|1RB1LC_0LA1RD_0RB0LC_1LA0RD}}, the current preperiod record holder, with a preperiod of 119,120,230,102. Before phasing into a translated cycle, this machine appears to be a [[spaghetti]].
* {{TM|1RB1LC_0LA1RD_0RB0LC_1LA0RD}}, the current preperiod record holder, with a preperiod of 119,120,230,102. Before phasing into a translated cycle, this machine appears to be a spaghetti.
* {{TM|1RB1RC_1LC0RA_0LB0LD_1LA1LD}} starts out as an irregular bell, but phase transitions into a translated cycler with period 4,222 at step 29,754,825.
* {{TM|1RB1RC_1LC0RA_0LB0LD_1LA1LD}} starts out as an irregular bell, but phase transitions into a translated cycler with period 4,222 at step 29,754,825.
* [[1RB0RC 1LB1LD 0RA0LD 1LA1RC|p17620 s158491]]
* {{TM|1RB0RC_1LB1LD_0RA0LD_1LA1RC}}
|
|[[File:1RB0RC 1LB1LD 0RA0LD 1LA1RC.png|frameless]]
|-
|-
|[[Cycler]]
|[[Cycler]]
|≥341,617
|≥ 341,617
|
|
* {{TM|1RB0RB_1LC0RD_1LA1LB_0LC1RD}}, likely period record holder, with a period of 120.
* {{TM|1RB0RB_1LC0RD_1LA1LB_0LC1RD}}, likely period record holder, with a period of 120.
Line 113: Line 119:
|-
|-
|[[Bouncer]]
|[[Bouncer]]
|≈132,000
|≈ 132,000
|
|
* {{TM|1RB1LA_1LC0RC_0RA1LD_1RC0LD}}, the current record holder for longest time to settle into a bouncer, with a start step of 83,158,409.
* {{TM|1RB1LA_1LC0RC_0RA1LD_1RC0LD}}, the current record holder for longest time to settle into a bouncer, with a start step of 83,158,409.
Line 121: Line 127:
|-
|-
|[[Counter]]
|[[Counter]]
|≈14,700
|≈ 14,700
|
|
* {{TM|1RB1LC_0LC1RD_1LA1LB_0LC0RD}}, a ternary counter.
* {{TM|1RB1LC_0LC1RD_1LA1LB_0LC0RD}}, a ternary counter.
Line 139: Line 145:
|-
|-
|[[Bell]]
|[[Bell]]
|≈2,350
|≈ 2,350
|
|
* {{TM|1RB1LA_0RC0LD_1LC0LA_1RC0RD}}, a typical inverted bell.
* {{TM|1RB1LA_0RC0LD_1LC0LA_1RC0RD}}, a typical inverted bell.
Line 147: Line 153:
|
|
|-
|-
|[[Cubic bell]]
|[[Bell|Cubic bell]]
|≈1,376
|≈ 1,376
|
|
* {{TM|1RB1RC_1LC0RC_0RA1LD_0LC0LB}}, a cubic inverted bell.
* {{TM|1RB1RC_1LC0RC_0RA1LD_0LC0LB}}, a cubic inverted bell.
Line 155: Line 161:
|-
|-
|Bouncer + X
|Bouncer + X
|≈365
|≈ 365
|
|
* {{TM|1RB1LA_1RC0RB_0LC1LD_0LD1RA}}, a bouncer + binary counter.
* {{TM|1RB1LA_1RC0RB_0LC1LD_0LD1RA}}, a bouncer + binary counter.
Line 163: Line 169:
* {{TM|1RB1LB_0LC0RD_0RA1LC_1RA1RD}}, a bouncer + cubic bell, leading to quartic tape growth on the left.
* {{TM|1RB1LB_0LC0RD_0RA1LC_1RA1RD}}, a bouncer + cubic bell, leading to quartic tape growth on the left.
* {{TM|1RB0LC_1LA1RD_1RA1LD_0LA0RB}}, a bouncer + unclassified. (If you can classify it, let me know in the talk page!)
* {{TM|1RB0LC_1LA1RD_1RA1LD_0LA0RB}}, a bouncer + unclassified. (If you can classify it, let me know in the talk page!)
|<div class="text-align: center">[[File:1RB0LB_1LC1RA_1RD0LC_0LA0RB.png|alt=Bouncer + counter|frameless|300x300px|Bouncer + counter.]]</div>
|style="text-align: center"|[[File:1RB0LB_1LC1RA_1RD0LC_0LA0RB.png|alt=Bouncer + counter|frameless|300x300px|Bouncer + counter.]]
<div class="text-align: center">[[File:1RB1LC 0RC1RD 1LA0LA 1RC0RB.png|alt=Bouncer + cellular automaton|frameless|300x300px|Bouncer + cellular automaton.]]</div>
[[File:1RB1LC 0RC1RD 1LA0LA 1RC0RB.png|alt=Bouncer + cellular automaton|frameless|Bouncer + cellular automaton.]]
|-
|-
|Bounce-counter
|Bounce-counter
|≈330
|≈ 330
|
|
* {{TM|1RB1LC_1LC0RB_1RA0LD_1RA1LA}}, a typical binary bounce-counter.
* {{TM|1RB1LC_1LC0RB_1RA0LD_1RA1LA}}, a typical binary bounce-counter.
Line 175: Line 181:
* {{TM|1RB0LC_1RD0RB_1LA1RC_1LC1RB}}, a 3/2-bounce-counter.
* {{TM|1RB0LC_1RD0RB_1LA1RC_1LC1RB}}, a 3/2-bounce-counter.
* {{TM|1RB0LC_1LC0RD_1RA1LA_0RA0LA}}, a binary bounce-counter with stationary counter digits.
* {{TM|1RB0LC_1LC0RD_1RA1LA_0RA0LA}}, a binary bounce-counter with stationary counter digits.
|<div class="text-align: center">[[File:1RB1LC 1LC0RB 1RA0LD 1RA1LA.png|frameless|300x300px]]</div>
|style="text-align: center"|[[File:1RB1LC 1LC0RB 1RA0LD 1RA1LA.png|frameless|300x300px]]
|-
|-
|Fractal
|[[Fractal]]
|20
|20
|
|
* {{TM|1RB1RC_0RC0RB_0LD1LA_1LD0LA}}, a typical example.
* {{TM|1RB1RC_0RC0RB_0LD1LA_1LD0LA}}, a typical example.
|<div class="text-align: center">[[File:1RB1RC 0RC0RB 0LD1LA 1LD0LA.png|frameless|300x300px]]</div>
|style="text-align: center"|[[File:1RB1RC 0RC0RB 0LD1LA 1LD0LA.png|frameless|300x300px]]
|-
|-
|[[Shift overflow bouncer counter|Tetration counter]]
|[[Shift overflow bouncer counter|Tetration counter]]
Line 187: Line 193:
|
|
* {{TM|1RB1LC_0RD0RD_0RC0LA_1LD1RA}}, a typical example.
* {{TM|1RB1LC_0RD0RD_0RC0LA_1LD1RA}}, a typical example.
|<div class="text-align: center">[[File:1RB1LC 0RD0RD 0RC0LA 1LD1RA.png|frameless|300x300px]]</div>
|style="text-align: center"|[[File:1RB1LC 0RD0RD 0RC0LA 1LD1RA.png|frameless|300x300px]]
|-
|-
|Cubic bounce-counter
|Cubic bounce-counter
Line 193: Line 199:
|
|
* {{TM|1RB1RA_0LC0RB_0RA0LD_1LC1RD}}, a typical example. Note that these share many of the same properties as [[Dekaheptoid|dekaheptoids]].
* {{TM|1RB1RA_0LC0RB_0RA0LD_1LC1RD}}, a typical example. Note that these share many of the same properties as [[Dekaheptoid|dekaheptoids]].
|<div class="text-align: center">[[File:1RB1RA 0LC0RB 0RA0LD 1LC1RD.png|frameless|300x300px]]</div>
|style="text-align: center"|[[File:1RB1RA 0LC0RB 0RA0LD 1LC1RD.png|frameless|300x300px]]
|}
|}


Line 208: Line 214:
* {{TM|1RB0RC_1LC1RA_1RA1LD_0LC0LA}}, a typical irregular bell.
* {{TM|1RB0RC_1LC1RA_1RA1LD_0LC0LA}}, a typical irregular bell.
* {{TM|1RB1LA_0RC0RD_1LD1RC_1LD0LA}}, a typical irregular inverted bell.
* {{TM|1RB1LA_0RC0RD_1LD1RC_1LD0LA}}, a typical irregular inverted bell.
|<div class="text-align: center">[[File:1RB0RC 1LC1RA 1RA1LD 0LC0LA.png|frameless|300x300px]]</div>
|style="text-align: center"|[[File:1RB0RC 1LC1RA 1RA1LD 0LC0LA.png|frameless|300x300px]]
|-
|-
|[[Spaghetti]]
|Spaghetti
|26
|26
|This is an informal description for spaghetti-code Turing machines that seem to have no predictable behavior, instead winding back and forth like a spaghetti. Any of these machines could potentially end up proven as one of the regular classifications. Indeed, many translated cyclers start their life out as spaghetti.
|This is an informal description for spaghetti-code Turing machines that seem to have no predictable behavior, instead winding back and forth like a spaghetti. Any of these machines could potentially end up proven as one of the regular classifications. Indeed, many translated cyclers start their life out as spaghetti.
Line 219: Line 225:
* {{TM|1RB0RC_1LC1LD_1RD1LB_1RA0LB}}, a cellular-automaton-like bouncer. The spaghetti nature of this machine is local.
* {{TM|1RB0RC_1LC1LD_1RD1LB_1RA0LB}}, a cellular-automaton-like bouncer. The spaghetti nature of this machine is local.
* {{TM|1RB1LC_1LA1RD_1RA0LC_1LB0RD}}, a "spaghetti sandwich" -- a spaghetti sandwiched on the left and right by a growing predictable repeating pattern.
* {{TM|1RB1LC_1LA1RD_1RA0LC_1LB0RD}}, a "spaghetti sandwich" -- a spaghetti sandwiched on the left and right by a growing predictable repeating pattern.
|<div class="text-align: center">[[File:1RB0RB 1LC1RC 0RA1LD 1RC0LD.png|frameless|300x300px]]</div>
|style="text-align: center"|[[File:1RB0RB 1LC1RC 0RA1LD 1RC0LD.png|frameless|300x300px]]
|-
|-
|Chaotic counter
|Chaotic counter
Line 235: Line 241:
* {{TM|1RB1LC_0LA0RB_1RD0LC_1LA0RD}}
* {{TM|1RB1LC_0LA0RB_1RD0LC_1LA0RD}}
* {{TM|1RB1LC_1RD0RB_1LA0LC_0LA0RD}}
* {{TM|1RB1LC_1RD0RB_1LA0LC_0LA0RD}}
|<div class="text-align: center">[[File:1RB1LC 1RD0RB 1LA0LC 0LA0RD.png|frameless|300x300px]]</div>
|style="text-align: center"|[[File:1RB1LC 1RD0RB 1LA0LC 0LA0RD.png|frameless|300x300px]]
|}
|}


Line 241: Line 247:


=== Translated cycler preperiod ===
=== Translated cycler preperiod ===
* 3x2: 101 (proven): {{TM|1RB1LB_0RC0LA_1LC0LA}} (period = 24)
BBS(n,m) = maximum translated cycler preperiod among n-state, m-symbol TMs.
* 4x2: 119,120,230,102 (current champion): {{TM|1RB1LC_0LA1RD_0RB0LC_1LA0RD}} (period = 966,716)
 
* 2x4: 293,225,660,896 (current champion): {{TM|1RB2LA0RA3LA_1LA1LB3RB1RA}} (period = 483,328)
BBS(1,m) = 0: {{TM|0RA---}} and {{TM|1RA---}}, note that any transitions other than A0 are unreachable.
{| class="wikitable"
|+
!Domain
!Preperiod
!Champions
!Period
|-
|BBS(2,2)
|≥ 9
|{{TM|1RB0LB_1LA0RB}}
|3
|-
|BBS(3,2)
|= 101
|{{TM|1RB1LB_0RC0LA_1LC0LA}}
|24
|-
|BBS(4,2)
|≥ 119,120,230,102
|{{TM|1RB1LC_0LA1RD_0RB0LC_1LA0RD}}
|966,716
|-
|BBS(5,2)
|> 10<sup>14,006</sup>
|{{TM|1RB1LE_0LC0LB_0LD1LC_1RD1RA_0RC0LA}}
|1
|-
|BBS(2,3)
|≥ 165<ref>Nick Drozd. [https://nickdrozd.github.io/2021/02/14/blanking-beavers.html Blanking Beavers]</ref>
|{{TM|1RB0LA---_1LB2LA0RB}}
|55
|-
|BBS(3,3)
|> 10 ↑↑ 6
|{{TM|1RB0LB2LA_1LA0RC0LB_2RC2RB0LC}}
|1
|-
|BBS(4,3)
|> <math>10 \uparrow^{4} 4</math>
|{{TM|1RB1RD1LC_2LB1RB1LC_1LB1LA1LD_0RB2RA2RD}}
|1
|-
|BBS(2,4)
|≥ 205,770,076,433,044,242,247,860
|{{TM|1RB2LA1RA1LB_0LB2RB3RB1LA}}
|1<ref>[https://discord.com/channels/960643023006490684/1385498968011575366/1450955870971367535]</ref>
|}


=== Translated cycler period ===
=== Translated cycler period ===
* 3x2: 92 (proven): {{TM|1RB0LA_0RC1LA_1LC0RB}} (preperiod = 0)
BBP(n,m) = maximum translated cycler period among n-state, m-symbol TMs.
* 4x2: 212,081,736 (current champion): {{TM|1RB0LA_0RC1RD_1LD0RB_1LA1RB}} (preperiod = 5,248,647,886)
 
* 2x4: 33,209,131 (current champion): {{TM|1RB0RA3LB1RB_2LA0LB1RA2RB}} (preperiod = 63,141,841)
BBP(1,m) = 1: {{TM|0RA---}} and {{TM|1RA---}}, note that any transitions other than A0 are unreachable.
{| class="wikitable"
|+
!Domain
!Period
!Champions
!Preperiod
|-
|BBP(2,2)
|≥ 9
|{{TM|1RB0RB_1LB1RA}}
|0
|-
|BBP(3,2)
|= 92
|{{TM|1RB0LA_0RC1LA_1LC0RB}}
|0
|-
|BBP(4,2)
|≥ 212,081,736
|{{TM|1RB0LA_0RC1RD_1LD0RB_1LA1RB}}
|5,248,647,886
|-
|BBP(3,3)
|≥ 1,195
|{{TM|1RB2RC1LC_0RC0RB1LA_2LA2RC1LB}}
|15
|-
|BBP(2,4)
|≥ 33,209,131
|{{TM|1RB0RA3LB1RB_2LA0LB1RA2RB}}
|63,141,841
|}
 
== References ==

Latest revision as of 16:24, 28 December 2025

A non-halting Turing machine is a Turing machine that does not halt. These include halt-free Turing machines, meaning those without an undefined or halt transition, as well as non-halt-free Turing machines that never enter an undefined or halt transition.

The crux of the Busy Beaver problem, of finding BB(n, k) for a given n and k, is to prove that all non-halting Turing machines with n states and k symbols are, in fact, non-halting.

The zoology of non-halting Turing machines is extremely rich. See Translated cycler, Bouncer, Bell, Counter, Fractal, Shift overflow counter, Shift overflow bouncer counter for a sample. In this page, we provide a detailed zoology for some low numbers of states and symbols.

Zoology

Machines are enumerated in TNF-1RB, and we exclude halting machines. In particular, a transition is defined if and only if it is reachable; unreachable transitions are undefined. This avoids duplicates.

For convenience, Turing machines are displayed here in standard text format.

n × 1

There are no TNF-1RB machines with just one symbol, as they cannot have "print 1" in their instructions.

1 × m

There are no non-halting TNF-1RB machines with 1 state and any amount of symbols, as the transition to state B already is undefined and leads to halting.

2 × 2

There are 106 TNF-1RB machines with 2 states and 2 symbols, with the following breakdown:

Classification Count Notable examples
Translated cycler 88
  • 1RB0RB_1LB1RA (bbch), unique TM with a record period of 9.
  • 1RB0LB_1LA0RB (bbch), unique TM with a record preperiod of 9.
Cycler 14
  • 1RB0RB_1LB1LA (bbch), one of the 7 TMs with a record period of 4.
  • 1RB1LB_1LA1RA (bbch), unique TM with a record preperiod of 5.
Bouncer 3
  • 1RB1LA_0LA1RB (bbch)
  • 1RB1LA_1LA1RB (bbch)
  • 1RB0LB_1LA0RA (bbch)
Counter 1
  • 1RB1LA_0LA0RB (bbch), a binary counter.

3 × 2

There are 15,064 TNF-1RB machines with 3 states and 2 symbols, with the following breakdown:

Classification Count Notable examples
Translated cycler 12,427
  • 1RB0LA_0RC1LA_1LC0RB (bbch), unique TM with a record period of 92.
  • 1RB1LB_0RC0LA_1LC0LA (bbch), unique TM with a record preperiod of 101.
Cycler 1,969
  • 1RB0LB_1LB1LC_0RC1RA (bbch), unique TM with a record period of 18.
  • 1RB1RC_1LC0LB_1RA1LA (bbch), unique TM with a record preperiod of 22.
Bouncer 558
  • 1RB0LC_1RC0RB_1LA1LC (bbch), a bouncer with two distinct shift rules.
Counter 95
  • 1RB1LA_0LA0RC_0LA1RB (bbch), a Fibonacci counter.
  • 1RB1LA_0LA1RC_0LA0RB (bbch), a two-phase binary counter.
  • 1RB1LA_0LA1RC_1LB0RB (bbch), a translating binary counter.
Cubic bell 10
  • 1RB1LA_0LA0RC_0LA1RC (bbch), a typical cubic bell.
Bell 5
  • 1RB0LC_1RC1RA_1LA0RB (bbch), a typical bell.
  • 1RB1LA_0RC0RC_1LC0LA (bbch), a typical inverted bell.

4 × 2

There are 2,744,516 TNF-1RB machines with 4 states and 2 symbols, with the following breakdown. This breakdown is not exact due to the presence of chaotic Turing machines which defy straightforward analysis and may eventually transition into a translated cycler or, more rarely, a bouncer, after a very large number of steps.

Regular (non-chaotic)

Classification Count Notes and Notable examples Example space-time diagram
Translated cycler ≥2,253,849
  • 1RB0LA_0RC1RD_1LD0RB_1LA1RB (bbch), the current period record holder, with a period of 212,081,736. Before phasing into a translated cycle, this machine appears to be a spaghetti (described in a later subsubsection).
  • 1RB1LC_0LA1RD_0RB0LC_1LA0RD (bbch), the current preperiod record holder, with a preperiod of 119,120,230,102. Before phasing into a translated cycle, this machine appears to be a spaghetti.
  • 1RB1RC_1LC0RA_0LB0LD_1LA1LD (bbch) starts out as an irregular bell, but phase transitions into a translated cycler with period 4,222 at step 29,754,825.
  • 1RB0RC_1LB1LD_0RA0LD_1LA1RC (bbch)
Cycler ≥ 341,617
  • 1RB0RB_1LC0RD_1LA1LB_0LC1RD (bbch), likely period record holder, with a period of 120.
  • 1RB1LB_1LC1RD_1LA0RD_0LA0RB (bbch), likely preperiod record holder, with a preperiod of 146.
Bouncer ≈ 132,000
  • 1RB1LA_1LC0RC_0RA1LD_1RC0LD (bbch), the current record holder for longest time to settle into a bouncer, with a start step of 83,158,409.
  • 1RB0RC_0RC0RB_1LC0LD_1LA0RA (bbch), starts out as irregular-side bells before phasing into a bouncer at step 3350.
  • 1RB1LC_0RD0LC_1LB0LA_1LD1RA (bbch), a bouncer with very complex runs. Start step 145,729.
Counter ≈ 14,700
  • 1RB1LC_0LC1RD_1LA1LB_0LC0RD (bbch), a ternary counter.
  • 1RB1LC_0LA1RB_1LD0RB_1LA1RA (bbch), a quaternary counter.
  • 1RB0LB_1RC0LD_1LB1RA_0RB1LD (bbch), a quinary counter.
  • 1RB1LC_0LD1RB_1LD0RD_1LA0RB (bbch), a senary counter.
  • 1RB1LC_0LD0RB_1RD1LA_1RA0LC (bbch), a 3/2-counter.
  • 1RB0RA_1LC1RA_1LD0LC_1LA1LD (bbch), a binary bi-counter.
  • 1RB1LC_1RC1RB_1RD0LC_1LA0RD (bbch), a binary-ternary bi-counter.
  • 1RB1LA_0LA0RC_0LA0RD_0LA1RC (bbch), a counter encoding a recurrence with characteristic polynomial x3−x2−2x+1.
  • 1RB1LA_0LA0RC_0LA1RD_0LA0RB (bbch), a counter encoding a recurrence with characteristic polynomial x3−x2−2.
  • 1RB1LC_1LD1RA_0RA0LC_0RB0LD (bbch), a counter encoding a recurrence that grows like n⋅2n.
  • 1RB0RC_0LC0RA_1LA0LD_1RA1LD (bbch), a tri-phasic binary counter.
  • 1RB1LC_0RD0RB_1LA0LA_1LD0LA (bbch), an example of a superexponential counter.
Bell ≈ 2,350
  • 1RB1LA_0RC0LD_1LC0LA_1RC0RD (bbch), a typical inverted bell.
  • 1RB1LB_1LC0RA_1RD0LB_1LA1RC (bbch), alternates between bell and half-bell.
  • 1RB0LC_1RC1RB_1LA1LD_0RA0RB (bbch), a grow-and-shrink bell.
  • 1RB0RC_1LC0RA_1RA1LD_0LC0LA (bbch), starts out as an irregular bell before phasing into a bell.
Cubic bell ≈ 1,376
  • 1RB1RC_1LC0RC_0RA1LD_0LC0LB (bbch), a cubic inverted bell.
  • 1RB0RC_0LD0RA_0LA1RC_1LA1LD (bbch), a cubic grow-and-shrink bell.
Bouncer + X ≈ 365
  • 1RB1LA_1RC0RB_0LC1LD_0LD1RA (bbch), a bouncer + binary counter.
  • 1RB0LA_0RC1LA_1RD0RA_0LB1RB (bbch), a bouncer + bell.
  • 1RB1LC_0RC1RD_1LA0LA_1RC0RB (bbch), a bouncer + cellular automaton. This could be universal.
  • 1RB1LC_0RC1RD_1LA0LA_0LA0RB (bbch), a bouncer + cellular automaton with a fractal nature.
  • 1RB1LB_0LC0RD_0RA1LC_1RA1RD (bbch), a bouncer + cubic bell, leading to quartic tape growth on the left.
  • 1RB0LC_1LA1RD_1RA1LD_0LA0RB (bbch), a bouncer + unclassified. (If you can classify it, let me know in the talk page!)
 Bouncer + counter

Bouncer + cellular automaton

Bounce-counter ≈ 330
  • 1RB1LC_1LC0RB_1RA0LD_1RA1LA (bbch), a typical binary bounce-counter.
  • 1RB1LB_1RC1RD_0LA0RC_1LD0LB (bbch), a typical quaternary bounce-counter.
  • 1RB1RA_0RC0LC_1LA0LD_0RA1LC (bbch), a ternary bounce-counter, which is more rare.
  • 1RB0LA_0RC1LA_0RD1RB_1LD1LA (bbch), a hybrid quaternary-octal bounce-counter.
  • 1RB0LC_1RD0RB_1LA1RC_1LC1RB (bbch), a 3/2-bounce-counter.
  • 1RB0LC_1LC0RD_1RA1LA_0RA0LA (bbch), a binary bounce-counter with stationary counter digits.
Fractal 20
  • 1RB1RC_0RC0RB_0LD1LA_1LD0LA (bbch), a typical example.
Tetration counter 19
  • 1RB1LC_0RD0RD_0RC0LA_1LD1RA (bbch), a typical example.
Cubic bounce-counter 13
  • 1RB1RA_0LC0RB_0RA0LD_1LC1RD (bbch), a typical example. Note that these share many of the same properties as dekaheptoids.

Chaotic

Classification Count Notes and Notable examples Example space-time diagram
Irregular bell 39
  • 1RB0RC_1LC1RA_1RA1LD_0LC0LA (bbch), a typical irregular bell.
  • 1RB1LA_0RC0RD_1LD1RC_1LD0LA (bbch), a typical irregular inverted bell.
Spaghetti 26 This is an informal description for spaghetti-code Turing machines that seem to have no predictable behavior, instead winding back and forth like a spaghetti. Any of these machines could potentially end up proven as one of the regular classifications. Indeed, many translated cyclers start their life out as spaghetti.
  • 1RB0RB_1LC1RC_0RA1LD_1RC0LD (bbch), a typical spaghetti.
  • 1RB0RA_1RC0RD_1LD1LC_1RA0LC (bbch), a spaghetti that seems to converge to a bounce-counter.
  • 1RB1LC_0LA0RD_1LA0LB_1LA1RD (bbch), a spaghetti whose envelope seems to converge to that of a bouncer.
  • 1RB0RC_1LC1LD_1RD1LB_1RA0LB (bbch), a cellular-automaton-like bouncer. The spaghetti nature of this machine is local.
  • 1RB1LC_1LA1RD_1RA0LC_1LB0RD (bbch), a "spaghetti sandwich" -- a spaghetti sandwiched on the left and right by a growing predictable repeating pattern.
Chaotic counter 10

Chaotic counters have slow-growing tapes like counters, but the behavior seems to be chaotic and is as of yet unknown:

  • 1RB0RC_0LD1RC_1LD0RB_0LA1LA (bbch)
  • 1RB1RA_0LC0LD_1LD0RB_0RA1LC (bbch)
  • 1RB0RC_1LA1RC_0LD0RB_0LA1LD (bbch)
  • 1RB0RB_1LC1RA_1LD0LC_0RA0LD (bbch)
  • 1RB1LA_0RC1RC_0LD0RB_0LA1LD (bbch)
  • 1RB1LC_0LC0RD_0LA1LA_0RB1RD (bbch)
  • 1RB0RB_0LC1RA_1LD1LC_0RA0LD (bbch)
  • 1RB1LC_1LD0RB_1RA0LC_0RA0LD (bbch)
  • 1RB1LC_0LA0RB_1RD0LC_1LA0RD (bbch)
  • 1RB1LC_1RD0RB_1LA0LC_0LA0RD (bbch)

Records

Translated cycler preperiod

BBS(n,m) = maximum translated cycler preperiod among n-state, m-symbol TMs.

BBS(1,m) = 0: 0RA--- (bbch) and 1RA--- (bbch), note that any transitions other than A0 are unreachable.

Domain Preperiod Champions Period
BBS(2,2) ≥ 9 1RB0LB_1LA0RB (bbch) 3
BBS(3,2) = 101 1RB1LB_0RC0LA_1LC0LA (bbch) 24
BBS(4,2) ≥ 119,120,230,102 1RB1LC_0LA1RD_0RB0LC_1LA0RD (bbch) 966,716
BBS(5,2) > 1014,006 1RB1LE_0LC0LB_0LD1LC_1RD1RA_0RC0LA (bbch) 1
BBS(2,3) ≥ 165[1] 1RB0LA---_1LB2LA0RB (bbch) 55
BBS(3,3) > 10 ↑↑ 6 1RB0LB2LA_1LA0RC0LB_2RC2RB0LC (bbch) 1
BBS(4,3) > 10↑44 1RB1RD1LC_2LB1RB1LC_1LB1LA1LD_0RB2RA2RD (bbch) 1
BBS(2,4) ≥ 205,770,076,433,044,242,247,860 1RB2LA1RA1LB_0LB2RB3RB1LA (bbch) 1[2]

Translated cycler period

BBP(n,m) = maximum translated cycler period among n-state, m-symbol TMs.

BBP(1,m) = 1: 0RA--- (bbch) and 1RA--- (bbch), note that any transitions other than A0 are unreachable.

Domain Period Champions Preperiod
BBP(2,2) ≥ 9 1RB0RB_1LB1RA (bbch) 0
BBP(3,2) = 92 1RB0LA_0RC1LA_1LC0RB (bbch) 0
BBP(4,2) ≥ 212,081,736 1RB0LA_0RC1RD_1LD0RB_1LA1RB (bbch) 5,248,647,886
BBP(3,3) ≥ 1,195 1RB2RC1LC_0RC0RB1LA_2LA2RC1LB (bbch) 15
BBP(2,4) ≥ 33,209,131 1RB0RA3LB1RB_2LA0LB1RA2RB (bbch) 63,141,841

References

  1. ↑ Nick Drozd. Blanking Beavers
  2. ↑ [1]
Retrieved from "https://wiki.bbchallenge.org/w/index.php?title=Non-halting_Turing_machine&oldid=5869"