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): More counters
Tlonuqbar (talk | contribs)
25 edits
mention of independent nonhalting machines
 
(35 intermediate revisions by 4 users not shown)
Line 1: Line 1:
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.
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 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]], [[Logical independence]] 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 [[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 19: Line 27:
|88
|88
|
|
* {{TM|1RB0RB_1LB1RA}}, unique TM with a record period of 9
* {{TM|1RB0RB_1LB1RA}}, unique TM with a record period of 9.
* {{TM|1RB0LB_1LA0RB}}, unique TM with a record preperiod of 9
* {{TM|1RB0LB_1LA0RB}}, unique TM with a record preperiod of 9.
|-
|-
|[[Cycler]]
|[[Cycler]]
|14
|14
|
|
* {{TM|1RB0RB_1LB1LA}}, one of the 7 TMs with a record period of 4
* {{TM|1RB0RB_1LB1LA}}, one of the 7 TMs with a record period of 4.
* {{TM|1RB1LB_1LA1RA}}, unique TM with record preperiod of 5
* {{TM|1RB1LB_1LA1RA}}, unique TM with a record preperiod of 5.
|-
|-
|[[Bouncer]]
|[[Bouncer]]
Line 51: Line 59:
|12,427
|12,427
|
|
* {{TM|1RB0LA_0RC1LA_1LC0RB}}, unique TM with a record period of 92
* {{TM|1RB0LA_0RC1LA_1LC0RB}}, unique TM with a record period of 92.
* {{TM|1RB1LB_0RC0LA_1LC0LA}}, unique TM with a record preperiod of 101
* {{TM|1RB1LB_0RC0LA_1LC0LA}}, unique TM with a record preperiod of 101.
|-
|-
|[[Cycler]]
|[[Cycler]]
|1,969
|1,969
|
|
* {{TM|1RB0LB_1LB1LC_0RC1RA}}, unique TM with a record period of 18
* {{TM|1RB0LB_1LB1LC_0RC1RA}}, unique TM with a record period of 18.
* {{TM|1RB1RC_1LC0LB_1RA1LA}}, unique TM with record preperiod of 22
* {{TM|1RB1RC_1LC0LB_1RA1LA}}, unique TM with a record preperiod of 22.
|-
|-
|[[Bouncer]]
|[[Bouncer]]
Line 72: 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 85: 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 92: Line 100:
!Count
!Count
!Notes and Notable examples
!Notes and Notable examples
!Example space-time diagram
|-
|-
|[[Translated cycler]]
|[[Translated cycler]]
|≥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 4222 at step 29754825.
* {{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|1RB0RC_1LB1LD_0RA0LD_1LA1RC}}
|[[File:1RB0RC 1LB1LD 0RA0LD 1LA1RC.png|frameless]]
|-
|-
|[[Cycler]]
|[[Cycler]]
|≥341617
|≥ 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.
* {{TM|1RB1LB_1LC1RD_1LA0RD_0LA0RB}}, likely preperiod record holder, with a preperiod of 146.
* {{TM|1RB1LB_1LC1RD_1LA0RD_0LA0RB}}, likely preperiod record holder, with a preperiod of 146.
|
|-
|-
|[[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.
* {{TM|1RB0RC_0RC0RB_1LC0LD_1LA0RA}}, starts out as irregular-side bells before phasing into a bouncer at step 3350.
* {{TM|1RB0RC_0RC0RB_1LC0LD_1LA0RA}}, starts out as irregular-side bells before phasing into a bouncer at step 3350.
* {{TM|1RB1LC_0RD0LC_1LB0LA_1LD1RA}}, a bouncer with very complex runs. Start step 145,729.
* {{TM|1RB1LC_0RD0LC_1LB0LA_1LD1RA}}, a bouncer with very complex runs. Start step 145,729.
|
|-
|-
|[[Counter]]
|[[Counter]]
|≈14,700
|≈ 14,700
|
|
* {{TM|1RB1LC_0LC1RD_1LA1LB_0LC0RD}}, a ternary counter.
* {{TM|1RB1LC_0LC1RD_1LA1LB_0LC0RD}}, a ternary counter.
Line 129: Line 142:


* {{TM|1RB1LC_0RD0RB_1LA0LA_1LD0LA}}, an example of a superexponential counter.
* {{TM|1RB1LC_0RD0RB_1LA0LA_1LD0LA}}, an example of a superexponential counter.
|
|-
|-
|[[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 137: Line 151:
* {{TM|1RB0LC_1RC1RB_1LA1LD_0RA0RB}}, a grow-and-shrink bell.
* {{TM|1RB0LC_1RC1RB_1LA1LD_0RA0RB}}, a grow-and-shrink bell.
* {{TM|1RB0RC_1LC0RA_1RA1LD_0LC0LA}}, starts out as an irregular bell before phasing into a bell.
* {{TM|1RB0RC_1LC0RA_1RA1LD_0LC0LA}}, starts out as an irregular bell before phasing into a bell.
|
|-
|-
|[[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.
* {{TM|1RB0RC_0LD0RA_0LA1RC_1LA1LD}}, a cubic grow-and-shrink bell.
* {{TM|1RB0RC_0LD0RA_0LA1RC_1LA1LD}}, a cubic grow-and-shrink bell.
|
|-
|-
|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 153: 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!)
|style="text-align: center"|[[File:1RB0LB_1LC1RA_1RD0LC_0LA0RB.png|alt=Bouncer + counter|frameless|300x300px|Bouncer + counter.]]
[[File:1RB1LC 0RC1RD 1LA0LA 1RC0RB.png|alt=Bouncer + cellular automaton|frameless|Bouncer + cellular automaton.]]
|-
|-
|Bouncing counter
|Bounce-counter
|≈330
|≈ 330
|
|
* {{TM|1RB1LC_1LC0RB_1RA0LD_1RA1LA}}, a typical bouncing binary counter.
* {{TM|1RB1LC_1LC0RB_1RA0LD_1RA1LA}}, a typical binary bounce-counter.
* {{TM|1RB1LB_1RC1RD_0LA0RC_1LD0LB}}, a typical bouncing quaternary counter.
* {{TM|1RB1LB_1RC1RD_0LA0RC_1LD0LB}}, a typical quaternary bounce-counter.
* {{TM|1RB1RA_0RC0LC_1LA0LD_0RA1LC}}, a bouncing ternary counter, which is more rare.
* {{TM|1RB1RA_0RC0LC_1LA0LD_0RA1LC}}, a ternary bounce-counter, which is more rare.
* {{TM|1RB0LA_0RC1LA_0RD1RB_1LD1LA}}, a hybrid quaternary-octal bouncing counter.
* {{TM|1RB0LA_0RC1LA_0RD1RB_1LD1LA}}, a hybrid quaternary-octal bounce-counter.
* {{TM|1RB0LC_1RD0RB_1LA1RC_1LC1RB}}, a bouncing 3/2-counter.
* {{TM|1RB0LC_1RD0RB_1LA1RC_1LC1RB}}, a 3/2-bounce-counter.
* {{TM|1RB0LC_1LC0RD_1RA1LA_0RA0LA}}, a bouncing binary counter with stationary counter digits.
* {{TM|1RB0LC_1LC0RD_1RA1LA_0RA0LA}}, a binary bounce-counter with stationary counter digits.
|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.
|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 173: Line 193:
|
|
* {{TM|1RB1LC_0RD0RD_0RC0LA_1LD1RA}}, a typical example.
* {{TM|1RB1LC_0RD0RD_0RC0LA_1LD1RA}}, a typical example.
|style="text-align: center"|[[File:1RB1LC 0RD0RD 0RC0LA 1LD1RA.png|frameless|300x300px]]
|-
|-
|Cubic bouncing counter
|Cubic bounce-counter
|13
|13
|
|
* {{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]].
|style="text-align: center"|[[File:1RB1RA 0LC0RB 0RA0LD 1LC1RD.png|frameless|300x300px]]
|}
|}


=== Chaotic ===
==== Chaotic ====
{| class="wikitable"
{| class="wikitable col4center"
!Classification
!Classification
!Count
!Count
Line 192: 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.
|[[File:1RB0RC 1LC1RA 1RA1LD 0LC0LA.png|frameless]]
|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.


* {{TM|1RB0RB_1LC1RC_0RA1LD_1RC0LD}}, a typical spaghetti.
* {{TM|1RB0RB_1LC1RC_0RA1LD_1RC0LD}}, a typical spaghetti.
* {{TM|1RB0RA_1RC0RD_1LD1LC_1RA0LC}}, a spaghetti that seems to converge to a bouncing counter.
* {{TM|1RB0RA_1RC0RD_1LD1LC_1RA0LC}}, a spaghetti that seems to converge to a bounce-counter.
* {{TM|1RB1LC_0LA0RD_1LA0LB_1LA1RD}}, a spaghetti whose envelope seems to converge to that of a bouncer.
* {{TM|1RB1LC_0LA0RD_1LA0LB_1LA1RD}}, a spaghetti whose envelope seems to converge to that of a bouncer.
* {{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.
|[[File:1RB0RB 1LC1RC 0RA1LD 1RC0LD.png|frameless]]
|style="text-align: center"|[[File:1RB0RB 1LC1RC 0RA1LD 1RC0LD.png|frameless|300x300px]]
|-
|-
|Chaotic counter
|Chaotic counter
Line 219: Line 241:
* {{TM|1RB1LC_0LA0RB_1RD0LC_1LA0RD}}
* {{TM|1RB1LC_0LA0RB_1RD0LC_1LA0RD}}
* {{TM|1RB1LC_1RD0RB_1LA0LC_0LA0RD}}
* {{TM|1RB1LC_1RD0RB_1LA0LC_0LA0RD}}
|[[File:1RB1LC 1RD0RB 1LA0LC 0LA0RD.png|frameless]]
|style="text-align: center"|[[File:1RB1LC 1RD0RB 1LA0LC 0LA0RD.png|frameless|300x300px]]
|}
|}
Additionally, some machines have been created that are non-halting if and only if certain [[wikipedia:Formal_system|formal systems]] are consistent. By [[wikipedia:Gödel's_incompleteness_theorems|Gödel's incompleteness theorems]], if the corresponding theory is consistent, it cannot prove that the machine is non-halting even though it is, and therefore if the machine has length n, the value BB(n) cannot be determined by the formal theory. See [[logical independence]] for more info.


== Records ==
== Records ==


=== 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 ==
 
[[Category:Zoology]]
[[Category:Functions]]

Latest revision as of 06:18, 27 February 2026

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, Logical independence 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)

Additionally, some machines have been created that are non-halting if and only if certain formal systems are consistent. By Gödel's incompleteness theorems, if the corresponding theory is consistent, it cannot prove that the machine is non-halting even though it is, and therefore if the machine has length n, the value BB(n) cannot be determined by the formal theory. See logical independence for more info.

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=6441"