Non-halting Turing machine: Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
VisualWikitext
No edit summary
(→‎Records: Name BBS function)
 
(27 intermediate revisions by 3 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]] 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]].


=== 2 × 2 ===
=== 2 × 2 ===
Line 19: Line 21:
|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 53:
|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 70: Line 72:
* {{TM|1RB1LA_0LA0RC_0LA1RB}}, a Fibonacci counter.
* {{TM|1RB1LA_0LA0RC_0LA1RB}}, a Fibonacci counter.
* {{TM|1RB1LA_0LA1RC_0LA0RB}}, a two-phase binary counter.
* {{TM|1RB1LA_0LA1RC_0LA0RB}}, a two-phase binary counter.
* {{TM|1RB1LA_0LA1RC_1LB0RB}}, a binary bi-counter.
* {{TM|1RB1LA_0LA1RC_1LB0RB}}, a translating binary counter.
|-
|-
|[[Cubic bell]]
|[[Bell|Cubic bell]]
|10
|10
|
|
Line 85: Line 87:


=== 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 fact that there are still some unclassified Turing machines.
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) ====
{| class="wikitable"
{| class="wikitable"
!Classification
!Classification
!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_0LA1RB_1LD0RB_1LA1RA}}, a quaternary counter.
* {{TM|1RB0LB_1RC0LD_1LB1RA_0RB1LD}}, a quinary counter.
* {{TM|1RB1LC_0LD1RB_1LD0RD_1LA0RB}}, a senary counter.
* {{TM|1RB1LC_0LD0RB_1RD1LA_1RA0LC}}, a 3/2-counter.
* {{TM|1RB0RA_1LC1RA_1LD0LC_1LA1LD}}, a binary bi-counter.
* {{TM|1RB1LC_1RC1RB_1RD0LC_1LA0RD}}, a binary-ternary bi-counter.
* {{TM|1RB1LA_0LA0RC_0LA0RD_0LA1RC}}, a counter encoding a recurrence with characteristic polynomial <math>x^3 - x^2 - 2x + 1</math>.
* {{TM|1RB1LA_0LA0RC_0LA0RD_0LA1RC}}, a counter encoding a recurrence with characteristic polynomial <math>x^3 - x^2 - 2x + 1</math>.
* {{TM|1RB1LA_0LA0RC_0LA1RD_0LA0RB}}, a counter encoding a recurrence with characteristic polynomial <math>x^3 - x^2 - 2</math>.
* {{TM|1RB1LA_0LA0RC_0LA1RD_0LA0RB}}, a counter encoding a recurrence with characteristic polynomial <math>x^3 - x^2 - 2</math>.
Line 120: Line 136:


* {{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 128: Line 145:
* {{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 143: Line 162:
* {{TM|1RB1LC_0RC1RD_1LA0LA_0LA0RB}}, a bouncer + cellular automaton with a fractal nature.
* {{TM|1RB1LC_0RC1RD_1LA0LA_0LA0RB}}, a bouncer + cellular automaton with a fractal nature.
* {{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|1RB1LA_1RC0RB_0LC1LD_0LD1RA}}, a bouncer + binary counter.
* {{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]]
|-
|-
|Irregular bell
|[[Fractal]]
|39
|
* {{TM|1RB0RC_1LC1RA_1RA1LD_0LC0LA}}, a typical irregular bell.
* {{TM|1RB1LA_0RC0RD_1LD1RC_1LD0LA}}, a typical irregular inverted bell.
|-
|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 171: Line 187:
|
|
* {{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 ====
{| class="wikitable col4center"
!Classification
!Count
!Notes and Notable examples
!Example space-time diagram
|-
|Irregular bell
|39
|
* {{TM|1RB0RC_1LC1RA_1RA1LD_0LC0LA}}, a typical irregular bell.
* {{TM|1RB1LA_0RC0RD_1LD1RC_1LD0LA}}, a typical irregular inverted bell.
|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 above 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.
|style="text-align: center"|[[File:1RB0RB 1LC1RC 0RA1LD 1RC0LD.png|frameless|300x300px]]
|-
|-
|Chaotic counter
|Chaotic counter
Line 201: Line 235:
* {{TM|1RB1LC_0LA0RB_1RD0LC_1LA0RD}}
* {{TM|1RB1LC_0LA0RB_1RD0LC_1LA0RD}}
* {{TM|1RB1LC_1RD0RB_1LA0LC_0LA0RD}}
* {{TM|1RB1LC_1RD0RB_1LA0LC_0LA0RD}}
|style="text-align: center"|[[File:1RB1LC 1RD0RB 1LA0LC 0LA0RD.png|frameless|300x300px]]
|}
|}


Line 206: Line 241:


=== 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)
* BBS(3,2) = 101 (proven): {{TM|1RB1LB_0RC0LA_1LC0LA}} (period = 24)
* 2x4: 293,225,660,896 (current champion): {{TM|1RB2LA0RA3LA_1LA1LB3RB1RA}} (period = 483,328)
* BBS(4,2) ≥ 119,120,230,102 (current champion): {{TM|1RB1LC_0LA1RD_0RB0LC_1LA0RD}} (period = 966,716)
* BBS(2,4) ≥ 293,225,660,896 (current champion): {{TM|1RB2LA0RA3LA_1LA1LB3RB1RA}} (period = 483,328)


=== 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)
* BBP(3,2) = 92 (proven): {{TM|1RB0LA_0RC1LA_1LC0RB}} (preperiod = 0)
* 2x4: 33,209,131 (current champion): {{TM|1RB0RA3LB1RB_2LA0LB1RA2RB}} (preperiod = 63,141,841)
* BBP(4,2) ≥ 212,081,736 (current champion): {{TM|1RB0LA_0RC1RD_1LD0RB_1LA1RB}} (preperiod = 5,248,647,886)
* BBP(2,4) ≥ 33,209,131 (current champion): {{TM|1RB0RA3LB1RB_2LA0LB1RA2RB}} (preperiod = 63,141,841)

Latest revision as of 01:39, 30 July 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.

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 .
  • 1RB1LA_0LA0RC_0LA1RD_0LA0RB (bbch), a counter encoding a recurrence with characteristic polynomial .
  • 1RB1LC_1LD1RA_0RA0LC_0RB0LD (bbch), a counter encoding a recurrence that grows like .
  • 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(3,2) = 101 (proven): 1RB1LB_0RC0LA_1LC0LA (bbch) (period = 24)
  • BBS(4,2) ≥ 119,120,230,102 (current champion): 1RB1LC_0LA1RD_0RB0LC_1LA0RD (bbch) (period = 966,716)
  • BBS(2,4) ≥ 293,225,660,896 (current champion): 1RB2LA0RA3LA_1LA1LB3RB1RA (bbch) (period = 483,328)

Translated cycler period

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

  • BBP(3,2) = 92 (proven): 1RB0LA_0RC1LA_1LC0RB (bbch) (preperiod = 0)
  • BBP(4,2) ≥ 212,081,736 (current champion): 1RB0LA_0RC1RD_1LD0RB_1LA1RB (bbch) (preperiod = 5,248,647,886)
  • BBP(2,4) ≥ 33,209,131 (current champion): 1RB0RA3LB1RB_2LA0LB1RA2RB (bbch) (preperiod = 63,141,841)
Retrieved from "https://wiki.bbchallenge.org/w/index.php?title=Non-halting_Turing_machine&oldid=2692"