Non-halting Turing machine: Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
← Older edit
VisualWikitext
Icy (talk | contribs)
157 edits
→Chaotic: Converted HTML markup to wikitable markup
Loader3229 (talk | contribs)
131 edits
No edit summary
 
(19 intermediate revisions by 5 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]], [[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 [[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 21: Line 27:
|88
|88
|
|
* {{TM|1RB0RB_1LB1RA}}, unique TM with a record period of 9.
* {{TM|1RB0RB_1LB1RA|non_halt}}, unique TM with a record period of 9.
* {{TM|1RB0LB_1LA0RB}}, unique TM with a record preperiod of 9.
* {{TM|1RB0LB_1LA0RB|non_halt}}, 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|non_halt}}, one of the 7 TMs with a record period of 4.
* {{TM|1RB1LB_1LA1RA}}, unique TM with a record preperiod of 5.
* {{TM|1RB1LB_1LA1RA|non_halt}}, unique TM with a record preperiod of 5.
|-
|-
|[[Bouncer]]
|[[Bouncer]]
|3
|3
|
|
* {{TM|1RB1LA_0LA1RB}}
* {{TM|1RB1LA_0LA1RB|non_halt}}
* {{TM|1RB1LA_1LA1RB}}
* {{TM|1RB1LA_1LA1RB|non_halt}}
* {{TM|1RB0LB_1LA0RA}}
* {{TM|1RB0LB_1LA0RA|non_halt}}
|-
|-
|[[Counter]]
|[[Counter]]
|1
|1
|
|
* {{TM|1RB1LA_0LA0RB}}, a binary counter.
* {{TM|1RB1LA_0LA0RB|non_halt}}, a binary counter.
|}
|}


Line 53: Line 59:
|12,427
|12,427
|
|
* {{TM|1RB0LA_0RC1LA_1LC0RB}}, unique TM with a record period of 92.
* {{TM|1RB0LA_0RC1LA_1LC0RB|non_halt}}, unique TM with a record period of 92.
* {{TM|1RB1LB_0RC0LA_1LC0LA}}, unique TM with a record preperiod of 101.
* {{TM|1RB1LB_0RC0LA_1LC0LA|non_halt}}, 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|non_halt}}, unique TM with a record period of 18.
* {{TM|1RB1RC_1LC0LB_1RA1LA}}, unique TM with a record preperiod of 22.
* {{TM|1RB1RC_1LC0LB_1RA1LA|non_halt}}, unique TM with a record preperiod of 22.
|-
|-
|[[Bouncer]]
|[[Bouncer]]
|558
|558
|
|
* {{TM|1RB0LC_1RC0RB_1LA1LC}}, a bouncer with two distinct shift rules.
* {{TM|1RB0LC_1RC0RB_1LA1LC|non_halt}}, a bouncer with two distinct shift rules.
|-
|-
|[[Counter]]
|[[Counter]]
|95
|95
|
|
* {{TM|1RB1LA_0LA0RC_0LA1RB}}, a Fibonacci counter.
* {{TM|1RB1LA_0LA0RC_0LA1RB|non_halt}}, a Fibonacci counter.
* {{TM|1RB1LA_0LA1RC_0LA0RB}}, a two-phase binary counter.
* {{TM|1RB1LA_0LA1RC_0LA0RB|non_halt}}, a two-phase binary counter.
* {{TM|1RB1LA_0LA1RC_1LB0RB}}, a translating binary counter.
* {{TM|1RB1LA_0LA1RC_1LB0RB|non_halt}}, a translating binary counter.
|-
|-
|[[Bell|Cubic bell]]
|[[Bell|Cubic bell]]
|10
|10
|
|
* {{TM|1RB1LA_0LA0RC_0LA1RC}}, a typical cubic bell.
* {{TM|1RB1LA_0LA0RC_0LA1RC|non_halt}}, a typical cubic bell.
|-
|-
|[[Bell]]
|[[Bell]]
|5
|5
|
|
* {{TM|1RB0LC_1RC1RA_1LA0RB}}, a typical bell.
* {{TM|1RB0LC_1RC1RA_1LA0RB|non_halt}}, a typical bell.
* {{TM|1RB1LA_0RC0RC_1LC0LA}}, a typical inverted bell.
* {{TM|1RB1LA_0RC0RC_1LC0LA|non_halt}}, a typical inverted bell.
|}
|}


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|non_halt}}, 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|non_halt}}, 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|non_halt}} 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|non_halt}}
|[[File:1RB0RC 1LB1LD 0RA0LD 1LA1RC.png|frameless]]
|[[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|non_halt}}, 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|non_halt}}, 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|non_halt}}, 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|non_halt}}, 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|non_halt}}, 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|non_halt}}, a ternary counter.
* {{TM|1RB1LC_0LA1RB_1LD0RB_1LA1RA}}, a quaternary counter.
* {{TM|1RB1LC_0LA1RB_1LD0RB_1LA1RA|non_halt}}, a quaternary counter.
* {{TM|1RB0LB_1RC0LD_1LB1RA_0RB1LD}}, a quinary counter.
* {{TM|1RB0LB_1RC0LD_1LB1RA_0RB1LD|non_halt}}, a quinary counter.
* {{TM|1RB1LC_0LD1RB_1LD0RD_1LA0RB}}, a senary counter.
* {{TM|1RB1LC_0LD1RB_1LD0RD_1LA0RB|non_halt}}, a senary counter.
* {{TM|1RB1LC_0LD0RB_1RD1LA_1RA0LC}}, a 3/2-counter.
* {{TM|1RB1LC_0LD0RB_1RD1LA_1RA0LC|non_halt}}, a 3/2-counter.
* {{TM|1RB0RA_1LC1RA_1LD0LC_1LA1LD}}, a binary bi-counter.
* {{TM|1RB0RA_1LC1RA_1LD0LC_1LA1LD|non_halt}}, a binary bi-counter.
* {{TM|1RB1LC_1RC1RB_1RD0LC_1LA0RD}}, a binary-ternary bi-counter.
* {{TM|1RB1LC_1RC1RB_1RD0LC_1LA0RD|non_halt}}, 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|non_halt}}, 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|non_halt}}, 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|1RB1LC_1LD1RA_0RA0LC_0RB0LD|non_halt}}, 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|1RB0RC_0LC0RA_1LA0LD_1RA1LD|non_halt}}, a tri-phasic binary counter.


* {{TM|1RB1LC_0RD0RB_1LA0LA_1LD0LA}}, an example of a superexponential counter.
* {{TM|1RB1LC_0RD0RB_1LA0LA_1LD0LA|non_halt}}, 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|non_halt}}, a typical inverted bell.
* {{TM|1RB1LB_1LC0RA_1RD0LB_1LA1RC}}, alternates between bell and half-bell.
* {{TM|1RB1LB_1LC0RA_1RD0LB_1LA1RC|non_halt}}, alternates between bell and half-bell.
* {{TM|1RB0LC_1RC1RB_1LA1LD_0RA0RB}}, a grow-and-shrink bell.
* {{TM|1RB0LC_1RC1RB_1LA1LD_0RA0RB|non_halt}}, 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|non_halt}}, starts out as an irregular bell before phasing into a bell.
|
|
|-
|-
|[[Bell|Cubic bell]]
|[[Bell|Cubic bell]]
|≈1,376
|≈ 1,376
|
|
* {{TM|1RB1RC_1LC0RC_0RA1LD_0LC0LB}}, a cubic inverted bell.
* {{TM|1RB1RC_1LC0RC_0RA1LD_0LC0LB|non_halt}}, a cubic inverted bell.
* {{TM|1RB0RC_0LD0RA_0LA1RC_1LA1LD}}, a cubic grow-and-shrink bell.
* {{TM|1RB0RC_0LD0RA_0LA1RC_1LA1LD|non_halt}}, 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|non_halt}}, a bouncer + binary counter.
* {{TM|1RB0LA_0RC1LA_1RD0RA_0LB1RB}}, a bouncer + bell.
* {{TM|1RB0LA_0RC1LA_1RD0RA_0LB1RB|non_halt}}, a bouncer + bell.
* {{TM|1RB1LC_0RC1RD_1LA0LA_1RC0RB}}, a bouncer + cellular automaton. This could be universal.
* {{TM|1RB1LC_0RC1RD_1LA0LA_1RC0RB|non_halt}}, a bouncer + cellular automaton. This could be universal.
* {{TM|1RB1LC_0RC1RD_1LA0LA_0LA0RB}}, a bouncer + cellular automaton with a fractal nature.
* {{TM|1RB1LC_0RC1RD_1LA0LA_0LA0RB|non_halt}}, 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|non_halt}}, 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|non_halt}}, 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.]]
|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.]]
[[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|non_halt}}, a typical binary bounce-counter.
* {{TM|1RB1LB_1RC1RD_0LA0RC_1LD0LB}}, a typical quaternary bounce-counter.
* {{TM|1RB1LB_1RC1RD_0LA0RC_1LD0LB|non_halt}}, a typical quaternary bounce-counter.
* {{TM|1RB1RA_0RC0LC_1LA0LD_0RA1LC}}, a ternary bounce-counter, which is more rare.
* {{TM|1RB1RA_0RC0LC_1LA0LD_0RA1LC|non_halt}}, a ternary bounce-counter, which is more rare.
* {{TM|1RB0LA_0RC1LA_0RD1RB_1LD1LA}}, a hybrid quaternary-octal bounce-counter.
* {{TM|1RB0LA_0RC1LA_0RD1RB_1LD1LA|non_halt}}, a hybrid quaternary-octal bounce-counter.
* {{TM|1RB0LC_1RD0RB_1LA1RC_1LC1RB}}, a 3/2-bounce-counter.
* {{TM|1RB0LC_1RD0RB_1LA1RC_1LC1RB|non_halt}}, a 3/2-bounce-counter.
* {{TM|1RB0LC_1LC0RD_1RA1LA_0RA0LA}}, a binary bounce-counter with stationary counter digits.
* {{TM|1RB0LC_1LC0RD_1RA1LA_0RA0LA|non_halt}}, a binary bounce-counter with stationary counter digits.
|style="text-align: center"|[[File:1RB1LC 1LC0RB 1RA0LD 1RA1LA.png|frameless|300x300px]]
|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|non_halt}}, a typical example.
|style="text-align: center"|[[File:1RB1RC 0RC0RB 0LD1LA 1LD0LA.png|frameless|300x300px]]
|style="text-align: center"|[[File:1RB1RC 0RC0RB 0LD1LA 1LD0LA.png|frameless|300x300px]]
|-
|-
Line 186: Line 192:
|19
|19
|
|
* {{TM|1RB1LC_0RD0RD_0RC0LA_1LD1RA}}, a typical example.
* {{TM|1RB1LC_0RD0RD_0RC0LA_1LD1RA|non_halt}}, a typical example.
|style="text-align: center"|[[File:1RB1LC 0RD0RD 0RC0LA 1LD1RA.png|frameless|300x300px]]
|style="text-align: center"|[[File:1RB1LC 0RD0RD 0RC0LA 1LD1RA.png|frameless|300x300px]]
|-
|-
Line 192: Line 198:
|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|non_halt}}, 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]]
|style="text-align: center"|[[File:1RB1RA 0LC0RB 0RA0LD 1LC1RD.png|frameless|300x300px]]
|}
|}
Line 206: Line 212:
|39
|39
|
|
* {{TM|1RB0RC_1LC1RA_1RA1LD_0LC0LA}}, a typical irregular bell.
* {{TM|1RB0RC_1LC1RA_1RA1LD_0LC0LA|non_halt}}, a typical irregular bell.
* {{TM|1RB1LA_0RC0RD_1LD1RC_1LD0LA}}, a typical irregular inverted bell.
* {{TM|1RB1LA_0RC0RD_1LD1RC_1LD0LA|non_halt}}, a typical irregular inverted bell.
|style="text-align: center"|[[File:1RB0RC 1LC1RA 1RA1LD 0LC0LA.png|frameless|300x300px]]
|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|non_halt}}, a typical spaghetti.
* {{TM|1RB0RA_1RC0RD_1LD1LC_1RA0LC}}, a spaghetti that seems to converge to a bounce-counter.
* {{TM|1RB0RA_1RC0RD_1LD1LC_1RA0LC|non_halt}}, 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|non_halt}}, 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|non_halt}}, 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|non_halt}}, 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]]
|style="text-align: center"|[[File:1RB0RB 1LC1RC 0RA1LD 1RC0LD.png|frameless|300x300px]]
|-
|-
Line 225: Line 231:
|
|
Chaotic counters have slow-growing tapes like counters, but the behavior seems to be chaotic and is as of yet unknown:
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|1RB0RC_0LD1RC_1LD0RB_0LA1LA|non_halt}}
* {{TM|1RB1RA_0LC0LD_1LD0RB_0RA1LC}}
* {{TM|1RB1RA_0LC0LD_1LD0RB_0RA1LC|non_halt}}
* {{TM|1RB0RC_1LA1RC_0LD0RB_0LA1LD}}
* {{TM|1RB0RC_1LA1RC_0LD0RB_0LA1LD|non_halt}}
* {{TM|1RB0RB_1LC1RA_1LD0LC_0RA0LD}}
* {{TM|1RB0RB_1LC1RA_1LD0LC_0RA0LD|non_halt}}
* {{TM|1RB1LA_0RC1RC_0LD0RB_0LA1LD}}
* {{TM|1RB1LA_0RC1RC_0LD0RB_0LA1LD|non_halt}}
* {{TM|1RB1LC_0LC0RD_0LA1LA_0RB1RD}}
* {{TM|1RB1LC_0LC0RD_0LA1LA_0RB1RD|non_halt}}
* {{TM|1RB0RB_0LC1RA_1LD1LC_0RA0LD}}
* {{TM|1RB0RB_0LC1RA_1LD1LC_0RA0LD|non_halt}}
* {{TM|1RB1LC_1LD0RB_1RA0LC_0RA0LD}}
* {{TM|1RB1LC_1LD0RB_1RA0LC_0RA0LD|non_halt}}
* {{TM|1RB1LC_0LA0RB_1RD0LC_1LA0RD}}
* {{TM|1RB1LC_0LA0RB_1RD0LC_1LA0RD|non_halt}}
* {{TM|1RB1LC_1RD0RB_1LA0LC_0LA0RD}}
* {{TM|1RB1LC_1RD0RB_1LA0LC_0LA0RD|non_halt}}
|style="text-align: center"|[[File:1RB1LC 1RD0RB 1LA0LC 0LA0RD.png|frameless|300x300px]]
|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---|non_halt}} and {{TM|1RA---|non_halt}}, note that any transitions other than A0 are unreachable.
{| class="wikitable"
|+
!Domain
!Preperiod
!Champions
!Period
|-
|BBS(2,2)
|≥ 9
|{{TM|1RB0LB_1LA0RB|non_halt}}
|3
|-
|BBS(3,2)
|= 101
|{{TM|1RB1LB_0RC0LA_1LC0LA|non_halt}}
|24
|-
|BBS(4,2)
|≥ 119,120,230,102
|{{TM|1RB1LC_0LA1RD_0RB0LC_1LA0RD|non_halt}}
|966,716
|-
|BBS(5,2)
|> 10<sup>14,006</sup>
|{{TM|1RB1LE_0LC0LB_0LD1LC_1RD1RA_0RC0LA|non_halt}}
|1
|-
|BBS(2,3)
|≥ 165<ref>Nick Drozd. [https://nickdrozd.github.io/2021/02/14/blanking-beavers.html Blanking Beavers]</ref>
|{{TM|1RB0LA---_1LB2LA0RB|non_halt}}
|55
|-
|BBS(3,3)
|> 10 ↑↑ 6
|{{TM|1RB0LB2LA_1LA0RC0LB_2RC2RB0LC|non_halt}}
|1
|-
|BBS(4,3)
|> <math>10 \uparrow^{4} 4</math>
|{{TM|1RB1RD1LC_2LB1RB1LC_1LB1LA1LD_0RB2RA2RD|non_halt}}
|1
|-
|BBS(2,4)
|≥ 205,770,076,433,044,242,247,860
|{{TM|1RB2LA1RA1LB_0LB2RB3RB1LA|non_halt}}
|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---|non_halt}} and {{TM|1RA---|non_halt}}, note that any transitions other than A0 are unreachable.
{| class="wikitable"
|+
!Domain
!Period
!Champions
!Preperiod
|-
|BBP(2,2)
|≥ 9
|{{TM|1RB0RB_1LB1RA|non_halt}}
|0
|-
|BBP(3,2)
|= 92
|{{TM|1RB0LA_0RC1LA_1LC0RB|non_halt}}
|0
|-
|BBP(4,2)
|≥ 212,081,736
|{{TM|1RB0LA_0RC1RD_1LD0RB_1LA1RB|non_halt}}
|5,248,647,886
|-
|BBP(3,3)
|≥ 1,195
|{{TM|1RB2RC1LC_0RC0RB1LA_2LA2RC1LB|non_halt}}
|15
|-
|BBP(2,4)
|≥ 33,209,131
|{{TM|1RB0RA3LB1RB_2LA0LB1RA2RB|non_halt}}
|63,141,841
|}
 
== References ==
 
[[Category:Zoology]]
[[Category:Functions]]

Latest revision as of 15:52, 29 September 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=8776"