Non-halting Turing machine: Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
← Older edit
VisualWikitext
Icy (talk | contribs)
156 edits
No edit summary
Tlonuqbar (talk | contribs)
25 edits
mention of independent nonhalting machines
 
(51 intermediate revisions by 4 users not shown)
Line 1: Line 1:
(Very rough sketches and outlines)
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.


== Partial classification ==
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.
* Cyclers
* Translated cyclers
* Bouncers (first seen in 2x2)
* Bells
** Exponential bells (first seen<ref>By "first seen" I mean either minimal in number of states '''or''' minimal in number of symbols</ref> in 3x2)
** Cubic bells (first seen in 3x2)
** Quartic bells (first seen in 5x2)
** etc...
** Irregular bells
* Counters (first seen in 2x2)
** Regular
** Irregular
** Exponential/tetration...
* Hybrid (counter-counter, bouncer-counter)
* Fractals
** Cube-like fractals (first seen in 4x2)
** Christmas tree fractals (first seen in 2x4)
* Spaghetti (first seen in 4x2)
** Asymptotically parabolically-shaped spaghetti e.g. {{TM|1RB0LB_1RC1LD_1LA0RC_0LA1LD}}
** Asymptotically irregular spaghetti e.g. {{TM|1RB0RB_1LC1RC_0RA1LD_1RC0LD}}. I suspect most irregular spaghetti, including this example, eventually become translated cyclers.
** Note: The bbchallenge links cannot show more than 65,536 steps, so it is not possible to visually verify asymptotic shapes via the above 2 links. See [https://fiery.pages.dev/turing/1RB0LB_1RC1LD_1LA0RC_0LA1LD?n=4194304 here] and [https://fiery.pages.dev/turing/1RB0RB_1LC1RC_0RA1LD_1RC0LD?n=4194304 here] for visualizations of the asymptotic shapes.
* Cellular automata (first seen in 5x2 and 3x3)
Sometimes phase transitions can occur. For example, {{TM|1RB1RC_1LC0RA_0LB0LD_1LA1LD}} starts out as an irregular bell but phase transitions into a translated cycler with period 4222 at step 29754825.


An informal argument, in light of the uncomputability of the Busy Beaver function, suggests that there can never be a complete classification of behaviors of Turing machines for arbitrarily high numbers of states.
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 [[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 ===
There are 106 TNF-1RB machines with 2 states and 2 symbols, with the following breakdown:
{| class="wikitable"
|+
!Classification
!Count
!Notable examples
|-
|[[Translated cycler]]
|88
|
* {{TM|1RB0RB_1LB1RA}}, unique TM with a record period of 9.
* {{TM|1RB0LB_1LA0RB}}, unique TM with a record preperiod of 9.
|-
|[[Cycler]]
|14
|
* {{TM|1RB0RB_1LB1LA}}, one of the 7 TMs with a record period of 4.
* {{TM|1RB1LB_1LA1RA}}, unique TM with a record preperiod of 5.
|-
|[[Bouncer]]
|3
|
* {{TM|1RB1LA_0LA1RB}}
* {{TM|1RB1LA_1LA1RB}}
* {{TM|1RB0LB_1LA0RA}}
|-
|[[Counter]]
|1
|
* {{TM|1RB1LA_0LA0RB}}, a binary counter.
|}
 
=== 3 × 2 ===
There are 15,064 TNF-1RB machines with 3 states and 2 symbols, with the following breakdown:
{| class="wikitable"
!Classification
!Count
!Notable examples
|-
|[[Translated cycler]]
|12,427
|
* {{TM|1RB0LA_0RC1LA_1LC0RB}}, unique TM with a record period of 92.
* {{TM|1RB1LB_0RC0LA_1LC0LA}}, unique TM with a record preperiod of 101.
|-
|[[Cycler]]
|1,969
|
* {{TM|1RB0LB_1LB1LC_0RC1RA}}, unique TM with a record period of 18.
* {{TM|1RB1RC_1LC0LB_1RA1LA}}, unique TM with a record preperiod of 22.
|-
|[[Bouncer]]
|558
|
* {{TM|1RB0LC_1RC0RB_1LA1LC}}, a bouncer with two distinct shift rules.
|-
|[[Counter]]
|95
|
* {{TM|1RB1LA_0LA0RC_0LA1RB}}, a Fibonacci counter.
* {{TM|1RB1LA_0LA1RC_0LA0RB}}, a two-phase binary counter.
* {{TM|1RB1LA_0LA1RC_1LB0RB}}, a translating binary counter.
|-
|[[Bell|Cubic bell]]
|10
|
* {{TM|1RB1LA_0LA0RC_0LA1RC}}, a typical cubic bell.
|-
|[[Bell]]
|5
|
* {{TM|1RB0LC_1RC1RA_1LA0RB}}, a typical bell.
* {{TM|1RB1LA_0RC0RC_1LC0LA}}, 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) ====
{| class="wikitable"
!Classification
!Count
!Notes and Notable examples
!Example space-time diagram
|-
|[[Translated cycler]]
|≥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 (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|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]]
|≥ 341,617
|
* {{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.
|
|-
|[[Bouncer]]
|≈ 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|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.
|
|-
|[[Counter]]
|≈ 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_0LA1RD_0LA0RB}}, a counter encoding a recurrence with characteristic polynomial <math>x^3 - x^2 - 2</math>.
* {{TM|1RB1LC_1LD1RA_0RA0LC_0RB0LD}}, a counter encoding a recurrence that grows like <math>n \cdot 2^n</math>.
* {{TM|1RB0RC_0LC0RA_1LA0LD_1RA1LD}}, a tri-phasic binary counter.
 
* {{TM|1RB1LC_0RD0RB_1LA0LA_1LD0LA}}, an example of a superexponential counter.
|
|-
|[[Bell]]
|≈ 2,350
|
* {{TM|1RB1LA_0RC0LD_1LC0LA_1RC0RD}}, a typical inverted bell.
* {{TM|1RB1LB_1LC0RA_1RD0LB_1LA1RC}}, alternates between bell and half-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.
|
|-
|[[Bell|Cubic bell]]
|≈ 1,376
|
* {{TM|1RB1RC_1LC0RC_0RA1LD_0LC0LB}}, a cubic inverted bell.
* {{TM|1RB0RC_0LD0RA_0LA1RC_1LA1LD}}, a cubic grow-and-shrink bell.
|
|-
|Bouncer + X
|≈ 365
|
* {{TM|1RB1LA_1RC0RB_0LC1LD_0LD1RA}}, a bouncer + binary counter.
* {{TM|1RB0LA_0RC1LA_1RD0RA_0LB1RB}}, a bouncer + bell.
* {{TM|1RB1LC_0RC1RD_1LA0LA_1RC0RB}}, a bouncer + cellular automaton. This could be universal.
* {{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|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.]]
|-
|Bounce-counter
|≈ 330
|
* {{TM|1RB1LC_1LC0RB_1RA0LD_1RA1LA}}, a typical binary bounce-counter.
* {{TM|1RB1LB_1RC1RD_0LA0RC_1LD0LB}}, a typical quaternary bounce-counter.
* {{TM|1RB1RA_0RC0LC_1LA0LD_0RA1LC}}, a ternary bounce-counter, which is more rare.
* {{TM|1RB0LA_0RC1LA_0RD1RB_1LD1LA}}, a hybrid quaternary-octal 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.
|style="text-align: center"|[[File:1RB1LC 1LC0RB 1RA0LD 1RA1LA.png|frameless|300x300px]]
|-
|[[Fractal]]
|20
|
* {{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]]
|19
|
* {{TM|1RB1LC_0RD0RD_0RC0LA_1LD1RA}}, a typical example.
|style="text-align: center"|[[File:1RB1LC 0RD0RD 0RC0LA 1LD1RA.png|frameless|300x300px]]
|-
|Cubic bounce-counter
|13
|
* {{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
|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.
 
* {{TM|1RB0RB_1LC1RC_0RA1LD_1RC0LD}}, a typical spaghetti.
* {{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|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.
|style="text-align: center"|[[File:1RB0RB 1LC1RC 0RA1LD 1RC0LD.png|frameless|300x300px]]
|-
|Chaotic counter
|10
|
Chaotic counters have slow-growing tapes like counters, but the behavior seems to be chaotic and is as of yet unknown:
* {{TM|1RB0RC_0LD1RC_1LD0RB_0LA1LA}}
* {{TM|1RB1RA_0LC0LD_1LD0RB_0RA1LC}}
* {{TM|1RB0RC_1LA1RC_0LD0RB_0LA1LD}}
* {{TM|1RB0RB_1LC1RA_1LD0LC_0RA0LD}}
* {{TM|1RB1LA_0RC1RC_0LD0RB_0LA1LD}}
* {{TM|1RB1LC_0LC0RD_0LA1LA_0RB1RD}}
* {{TM|1RB0RB_0LC1RA_1LD1LC_0RA0LD}}
* {{TM|1RB1LC_1LD0RB_1RA0LC_0RA0LD}}
* {{TM|1RB1LC_0LA0RB_1RD0LC_1LA0RD}}
* {{TM|1RB1LC_1RD0RB_1LA0LC_0LA0RD}}
|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"