Counter

2024-11-13T21:55:52Z

Icy: /* Analysis 1 */ Typo

[[File:1RB1LA 0LA0RB.png|thumb|A close-up of the counter {{TM|1RB1LA_0LA0RB}}.]]
A '''counter''' is a [[non-halting Turing machine]] that, roughly speaking, has a tape that grows logarithmically with time and whose tape counts up in some sort of place-value system. Often, when the place-value system is known, we may call such counters '''binary counters''', '''ternary counters''', and so on.

== Example ==
{{TM|1RB1LA_0LA0RB}} is a binary counter with 2 states and 2 symbols, whose spacetime diagram is shown in the image to the right. In fact, it is the only Turing machine with 2 states and symbols, up to permutations, that is a counter. In this section we give two analyses of this counter. The first analysis is coarse-grained in that it only proves non-halting and logarithmic tape growth. The second analysis is more detailed and furthermore explains the counter nature of this machine, as well as the precise step counts from one encoded number to the next.

=== Analysis 1 ===
Define the macro rule '''R'''''n'' recursively as follows:

* '''R'''0 = B0,
* '''R'''''n'' = B1 '''R'''''n''−1 A0 '''R'''''n''−1 A1, for ''n'' ≥ 1.
Then we find by induction, for all ''n'' ≥ 0:

* '''R'''0: <code>B >0 → A <0</code>,
* '''R'''''n'': <code>B >(1n)0 → A <(1n)0</code>,

so that, for all ''n'' ≥ 0,<blockquote>A0 '''R'''''n'' A1: <code>A >0(1n)0 → A <(1n+1)0</code>. </blockquote>This proves that the [[transcript]] of <code>1RB1LA_0LA0RB</code> from the all zeros tape is<blockquote>(A0 '''R'''''n'' A1)''n'' ≥ 0.</blockquote>Furthermore, |'''R'''''n''|, the number of steps taken by '''R'''''n'', can be seen to be given by the recurrence<blockquote><math>|\mathbf R_0|=1,\ |\mathbf R_n| = 2|\mathbf R_{n-1}| + 3</math>,</blockquote>which has solution <math>|\mathbf R_n| = 2^{n + 2} - 3.</math>

=== Analysis 2 ===
In this analysis, we will show that the counter indeed counts up in binary. More precisely, for a given non-negative integer ''n'', let <code>bin(n)</code> denote the number ''n'' in binary. Also, let ''v2''(''n'') denote the 2-valuation of ''n'', which is the number of times that ''n'' is divisible by 2. Then we will show:<blockquote><code>B bin(n) >0 →[2v2(n+1) + 2] B bin(n+1) >0</code>.</blockquote>To show this, it suffices to show, for all ''k'' ≥ 0,<blockquote><code>B 0(1k)>0 →[2k + 2] B 1(0k)>0</code>.</blockquote>The sequence B0 A1''k'' A0 B1''k'' proves this, which completes the analysis.<blockquote></blockquote>

Non-halting Turing machine

2024-11-13T20:43:48Z

Icy: Cubic bell links to bell now

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 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.

== 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 [[lexical normal form]].

=== 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]].
* {{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.
* [[1RB0RC 1LB1LD 0RA0LD 1LA1RC|p17620 s158491]]
|<div style="text-align: center">[[File:1RB0RC 1LB1LD 0RA0LD 1LA1RC.png|frameless|300x300px]]</div>
|-
|[[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!)
|<div class="text-align: center">[[File:1RB0LB_1LC1RA_1RD0LC_0LA0RB.png|alt=Bouncer + counter|frameless|300x300px|Bouncer + counter.]]</div>
<div class="text-align: center">[[File:1RB1LC 0RC1RD 1LA0LA 1RC0RB.png|alt=Bouncer + cellular automaton|frameless|300x300px|Bouncer + cellular automaton.]]</div>
|-
|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.
|<div class="text-align: center">[[File:1RB1LC 1LC0RB 1RA0LD 1RA1LA.png|frameless|300x300px]]</div>
|-
|Fractal
|20
|
* {{TM|1RB1RC_0RC0RB_0LD1LA_1LD0LA}}, a typical example.
|<div class="text-align: center">[[File:1RB1RC 0RC0RB 0LD1LA 1LD0LA.png|frameless|300x300px]]</div>
|-
|[[Shift overflow bouncer counter|Tetration counter]]
|19
|
* {{TM|1RB1LC_0RD0RD_0RC0LA_1LD1RA}}, a typical example.
|<div class="text-align: center">[[File:1RB1LC 0RD0RD 0RC0LA 1LD1RA.png|frameless|300x300px]]</div>
|-
|Cubic bounce-counter
|13
|
* {{TM|1RB1RA_0LC0RB_0RA0LD_1LC1RD}}, a typical example. Note that these share many of the same properties as [[Dekaheptoid|dekaheptoids]].
|<div class="text-align: center">[[File:1RB1RA 0LC0RB 0RA0LD 1LC1RD.png|frameless|300x300px]]</div>
|}

==== 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.
|<div class="text-align: center">[[File:1RB0RC 1LC1RA 1RA1LD 0LC0LA.png|frameless|300x300px]]</div>
|-
|[[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.
|<div class="text-align: center">[[File:1RB0RB 1LC1RC 0RA1LD 1RC0LD.png|frameless|300x300px]]</div>
|-
|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}}
|<div class="text-align: center">[[File:1RB1LC 1RD0RB 1LA0LC 0LA0RD.png|frameless|300x300px]]</div>
|}

== Records ==

=== Translated cycler preperiod ===
* 3x2: 101 (proven): {{TM|1RB1LB_0RC0LA_1LC0LA}} (period = 24)
* 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)

=== Translated cycler period ===
* 3x2: 92 (proven): {{TM|1RB0LA_0RC1LA_1LC0RB}} (preperiod = 0)
* 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)

Counter

2024-11-13T20:28:14Z

Icy: /* Analysis 2 */ typo

[[File:1RB1LA 0LA0RB.png|thumb|A close-up of the counter {{TM|1RB1LA_0LA0RB}}.]]
A '''counter''' is a [[non-halting Turing machine]] that, roughly speaking, has a tape that grows logarithmically with time and whose tape counts up in some sort of place-value system. Often, when the place-value system is known, we may call such counters '''binary counters''', '''ternary counters''', and so on.

== Example ==
{{TM|1RB1LA_0LA0RB}} is a binary counter with 2 states and 2 symbols, whose spacetime diagram is shown in the image to the right. In fact, it is the only Turing machine with 2 states and symbols, up to permutations, that is a counter. In this section we give two analyses of this counter. The first analysis is coarse-grained in that it only proves non-halting and logarithmic tape growth. The second analysis is more detailed and furthermore explains the counter nature of this machine, as well as the precise step counts from one encoded number to the next.

=== Analysis 1 ===
Define the macro rule '''R'''''n'' recursively as follows:

* '''R'''0 = B0,
* '''R'''''n'' = B1 '''R'''''n''−1 A0 '''R'''''n''−1 A1, for ''n'' ≥ 1.
Then we find by induction, for all ''n'' ≥ 0:

* '''R'''0: <code>B >0 → A <0</code>,
* '''R'''''n'': <code>B >(1n)0 → A <(1n)0</code>,

so that, for all ''n'' ≥ 0,<blockquote>A0 '''R'''''n'' A1: <code>A >0(1n)0 → A <(1n+1)0</code>. </blockquote>This proves that the [[transcript]] of <code>1RB1LA_0LA0RB</code> from the all zeros tape is<blockquote>(A0 '''R'''''n'' A1)''n'' ≥ 0.</blockquote>Furthermore, |'''R'''''n''|, the number of steps taken by '''R'''''n'', can be seen to be given by the recurrence<blockquote><math>|\mathbf R_0|=0,\ |\mathbf R_n| = 2|\mathbf R_{n-1}| + 3</math>,</blockquote>which has solution <math>|\mathbf R_n| = 2^{n + 2} - 3.</math>

=== Analysis 2 ===
In this analysis, we will show that the counter indeed counts up in binary. More precisely, for a given non-negative integer ''n'', let <code>bin(n)</code> denote the number ''n'' in binary. Also, let ''v2''(''n'') denote the 2-valuation of ''n'', which is the number of times that ''n'' is divisible by 2. Then we will show:<blockquote><code>B bin(n) >0 →[2v2(n+1) + 2] B bin(n+1) >0</code>.</blockquote>To show this, it suffices to show, for all ''k'' ≥ 0,<blockquote><code>B 0(1k)>0 →[2k + 2] B 1(0k)>0</code>.</blockquote>The sequence B0 A1''k'' A0 B1''k'' proves this, which completes the analysis.<blockquote></blockquote>

Counter

2024-11-13T20:27:51Z

Icy: /* Analysis 2 */

[[File:1RB1LA 0LA0RB.png|thumb|A close-up of the counter {{TM|1RB1LA_0LA0RB}}.]]
A '''counter''' is a [[non-halting Turing machine]] that, roughly speaking, has a tape that grows logarithmically with time and whose tape counts up in some sort of place-value system. Often, when the place-value system is known, we may call such counters '''binary counters''', '''ternary counters''', and so on.

== Example ==
{{TM|1RB1LA_0LA0RB}} is a binary counter with 2 states and 2 symbols, whose spacetime diagram is shown in the image to the right. In fact, it is the only Turing machine with 2 states and symbols, up to permutations, that is a counter. In this section we give two analyses of this counter. The first analysis is coarse-grained in that it only proves non-halting and logarithmic tape growth. The second analysis is more detailed and furthermore explains the counter nature of this machine, as well as the precise step counts from one encoded number to the next.

=== Analysis 1 ===
Define the macro rule '''R'''''n'' recursively as follows:

* '''R'''0 = B0,
* '''R'''''n'' = B1 '''R'''''n''−1 A0 '''R'''''n''−1 A1, for ''n'' ≥ 1.
Then we find by induction, for all ''n'' ≥ 0:

* '''R'''0: <code>B >0 → A <0</code>,
* '''R'''''n'': <code>B >(1n)0 → A <(1n)0</code>,

so that, for all ''n'' ≥ 0,<blockquote>A0 '''R'''''n'' A1: <code>A >0(1n)0 → A <(1n+1)0</code>. </blockquote>This proves that the [[transcript]] of <code>1RB1LA_0LA0RB</code> from the all zeros tape is<blockquote>(A0 '''R'''''n'' A1)''n'' ≥ 0.</blockquote>Furthermore, |'''R'''''n''|, the number of steps taken by '''R'''''n'', can be seen to be given by the recurrence<blockquote><math>|\mathbf R_0|=0,\ |\mathbf R_n| = 2|\mathbf R_{n-1}| + 3</math>,</blockquote>which has solution <math>|\mathbf R_n| = 2^{n + 2} - 3.</math>

=== Analysis 2 ===
In this analysis, we will show that the counter indeed counts up in binary. More precisely, for a given non-negative integer ''n'', let <code>bin(n)</code> denote the number ''n'' in binary. Also, let ''v2''(''n'') denote the 2-valuation of ''n'', which is the number of times that ''n'' is divisible by 2. Then we will show:<blockquote><code>B bin(n) >0 →[2v2(n + 1) + 2] B bin(n) >0</code>.</blockquote>To show this, it suffices to show, for all ''k'' ≥ 0,<blockquote><code>B 0(1k)>0 →[2k + 2] B 1(0k)>0</code>.</blockquote>The sequence B0 A1''k'' A0 B1''k'' proves this, which completes the analysis.<blockquote></blockquote>

Counter

2024-11-13T20:27:35Z

Icy: /* Analysis 2 */

[[File:1RB1LA 0LA0RB.png|thumb|A close-up of the counter {{TM|1RB1LA_0LA0RB}}.]]
A '''counter''' is a [[non-halting Turing machine]] that, roughly speaking, has a tape that grows logarithmically with time and whose tape counts up in some sort of place-value system. Often, when the place-value system is known, we may call such counters '''binary counters''', '''ternary counters''', and so on.

== Example ==
{{TM|1RB1LA_0LA0RB}} is a binary counter with 2 states and 2 symbols, whose spacetime diagram is shown in the image to the right. In fact, it is the only Turing machine with 2 states and symbols, up to permutations, that is a counter. In this section we give two analyses of this counter. The first analysis is coarse-grained in that it only proves non-halting and logarithmic tape growth. The second analysis is more detailed and furthermore explains the counter nature of this machine, as well as the precise step counts from one encoded number to the next.

=== Analysis 1 ===
Define the macro rule '''R'''''n'' recursively as follows:

* '''R'''0 = B0,
* '''R'''''n'' = B1 '''R'''''n''−1 A0 '''R'''''n''−1 A1, for ''n'' ≥ 1.
Then we find by induction, for all ''n'' ≥ 0:

* '''R'''0: <code>B >0 → A <0</code>,
* '''R'''''n'': <code>B >(1n)0 → A <(1n)0</code>,

so that, for all ''n'' ≥ 0,<blockquote>A0 '''R'''''n'' A1: <code>A >0(1n)0 → A <(1n+1)0</code>. </blockquote>This proves that the [[transcript]] of <code>1RB1LA_0LA0RB</code> from the all zeros tape is<blockquote>(A0 '''R'''''n'' A1)''n'' ≥ 0.</blockquote>Furthermore, |'''R'''''n''|, the number of steps taken by '''R'''''n'', can be seen to be given by the recurrence<blockquote><math>|\mathbf R_0|=0,\ |\mathbf R_n| = 2|\mathbf R_{n-1}| + 3</math>,</blockquote>which has solution <math>|\mathbf R_n| = 2^{n + 2} - 3.</math>

=== Analysis 2 ===
In this analysis, we will show that the counter indeed counts up in binary. More precisely, for a given non-negative integer ''n'', let <code>bin(n)</code> denote the number ''n'' in binary. Also, let ''v2''(''n'') denote the 2-valuation of ''n'', which is the number of times that ''n'' is divisible by 2. Then we will show:<blockquote><code>B (bin(n)) >0 →[2v2(n + 1) + 2] B (bin(n)) >0</code>.</blockquote>To show this, it suffices to show, for all ''k'' ≥ 0,<blockquote><code>B 0(1k)>0 →[2k + 2] B 1(0k)>0</code>.</blockquote>The sequence B0 A1''k'' A0 B1''k'' proves this, which completes the analysis.<blockquote></blockquote>

Counter

2024-11-13T20:26:38Z

Icy: /* Analysis 2 */ Disambiguate with parentheses

[[File:1RB1LA 0LA0RB.png|thumb|A close-up of the counter {{TM|1RB1LA_0LA0RB}}.]]
A '''counter''' is a [[non-halting Turing machine]] that, roughly speaking, has a tape that grows logarithmically with time and whose tape counts up in some sort of place-value system. Often, when the place-value system is known, we may call such counters '''binary counters''', '''ternary counters''', and so on.

== Example ==
{{TM|1RB1LA_0LA0RB}} is a binary counter with 2 states and 2 symbols, whose spacetime diagram is shown in the image to the right. In fact, it is the only Turing machine with 2 states and symbols, up to permutations, that is a counter. In this section we give two analyses of this counter. The first analysis is coarse-grained in that it only proves non-halting and logarithmic tape growth. The second analysis is more detailed and furthermore explains the counter nature of this machine, as well as the precise step counts from one encoded number to the next.

=== Analysis 1 ===
Define the macro rule '''R'''''n'' recursively as follows:

* '''R'''0 = B0,
* '''R'''''n'' = B1 '''R'''''n''−1 A0 '''R'''''n''−1 A1, for ''n'' ≥ 1.
Then we find by induction, for all ''n'' ≥ 0:

* '''R'''0: <code>B >0 → A <0</code>,
* '''R'''''n'': <code>B >(1n)0 → A <(1n)0</code>,

so that, for all ''n'' ≥ 0,<blockquote>A0 '''R'''''n'' A1: <code>A >0(1n)0 → A <(1n+1)0</code>. </blockquote>This proves that the [[transcript]] of <code>1RB1LA_0LA0RB</code> from the all zeros tape is<blockquote>(A0 '''R'''''n'' A1)''n'' ≥ 0.</blockquote>Furthermore, |'''R'''''n''|, the number of steps taken by '''R'''''n'', can be seen to be given by the recurrence<blockquote><math>|\mathbf R_0|=0,\ |\mathbf R_n| = 2|\mathbf R_{n-1}| + 3</math>,</blockquote>which has solution <math>|\mathbf R_n| = 2^{n + 2} - 3.</math>

=== Analysis 2 ===
In this analysis, we will show that the counter indeed counts up in binary. More precisely, for a given non-negative integer ''n'', let <code>[n] := bin(n)</code> denote the number ''n'' in binary. Also, let ''v2''(''n'') denote the 2-valuation of ''n'', which is the number of times that ''n'' is divisible by 2. Then we will show:<blockquote><code>B [n] >0 →[2v2(n + 1) + 2] B [n+1] >0</code>.</blockquote>To show this, it suffices to show<blockquote><code>B 0(1k)>0 →[2k + 2] B 1(0k)>0</code>.</blockquote>The sequence B0 A1''k'' A0 B1''k'' proves this, which completes the analysis.<blockquote></blockquote>

Counter

2024-11-13T20:24:51Z

Icy: Added counter page + analysis

[[File:1RB1LA 0LA0RB.png|thumb|A close-up of the counter {{TM|1RB1LA_0LA0RB}}.]]
A '''counter''' is a [[non-halting Turing machine]] that, roughly speaking, has a tape that grows logarithmically with time and whose tape counts up in some sort of place-value system. Often, when the place-value system is known, we may call such counters '''binary counters''', '''ternary counters''', and so on.

== Example ==
{{TM|1RB1LA_0LA0RB}} is a binary counter with 2 states and 2 symbols, whose spacetime diagram is shown in the image to the right. In fact, it is the only Turing machine with 2 states and symbols, up to permutations, that is a counter. In this section we give two analyses of this counter. The first analysis is coarse-grained in that it only proves non-halting and logarithmic tape growth. The second analysis is more detailed and furthermore explains the counter nature of this machine, as well as the precise step counts from one encoded number to the next.

=== Analysis 1 ===
Define the macro rule '''R'''''n'' recursively as follows:

* '''R'''0 = B0,
* '''R'''''n'' = B1 '''R'''''n''−1 A0 '''R'''''n''−1 A1, for ''n'' ≥ 1.
Then we find by induction, for all ''n'' ≥ 0:

* '''R'''0: <code>B >0 → A <0</code>,
* '''R'''''n'': <code>B >1n 0 → A <1n 0</code>,

so that, for all ''n'' ≥ 0,<blockquote>A0 '''R'''''n'' A1: <code>A >0 1n 0 → A <1n+1 0</code>. </blockquote>This proves that the [[transcript]] of <code>1RB1LA_0LA0RB</code> from the all zeros tape is<blockquote>(A0 '''R'''''n'' A1)''n'' ≥ 0.</blockquote>Furthermore, |'''R'''''n''|, the number of steps taken by '''R'''''n'', can be seen to be given by the recurrence<blockquote><math>|\mathbf R_0|=0,\ |\mathbf R_n| = 2|\mathbf R_{n-1}| + 3</math>,</blockquote>which has solution <math>|\mathbf R_n| = 2^{n + 2} - 3.</math>

=== Analysis 2 ===
In this analysis, we will show that the counter indeed counts up in binary. More precisely, for a given non-negative integer ''n'', let <code>[n] := bin(n)</code> denote the number ''n'' in binary. Also, let ''v2''(''n'') denote the 2-valuation of ''n'', which is the number of times that ''n'' is divisible by 2. Then we will show:<blockquote><code>B [n] >0 →[2v2(n + 1) + 2] B [n+1] >0</code>.</blockquote>To show this, it suffices to show<blockquote><code>B 01k>0 →[2k + 2] B 10k>0</code>.</blockquote>The sequence B0 A1''k'' A0 B1''k'' proves this, which completes the analysis.<blockquote></blockquote>

File:1RB1LA 0LA0RB.png

2024-11-13T19:56:46Z

Icy:

An example of a binary counter. 54 steps.

Bell

2024-11-13T15:57:28Z

Icy: Mentioned 5-state winner

A '''bell''' is a [[non-halting Turing machine]] whose behavior can be described as a sequence of [[bouncer]]s of increasing size. There are two main variants of bells, depending on whether the bouncers participate in tape growth or not. A bell whose bouncers grow the tape on each bounce is called an '''exponential bell''' or simply '''bell''' for short, while a bell whose bouncers do not grow the tape on each bounce is called a '''cubic bell'''.

Sometimes a Turing machine displays bell characteristics for some number of steps before phase transitioning to another behavior, such as halting. A famous example is the [[5-state busy beaver winner]]. These may also be called bells, or more precisely, '''transient bells''', to indicate that they only show bell-like features up to a certain point.

== Examples ==

[[File:1RB0LC 1RC1RA 1LA0RB.png|thumb|300px|Spacetime diagram of the bell {{TM|1RB0LC_1RC1RA_1LA0RB}}.]]
=== Exponential bell ===

{{TM|1RB0LC_1RC1RA_1LA0RB}} is an example of an exponential bell with 3 states and 2 symbols.

==== Analysis ====
'''Transcript''': (A0 B0 ((C1 B0)2k (C0 A1)2k+1)(k = 0 .. n-1) (C0 B1)2n (C0 A1)2n C0 (A0 B1)2n+1)n=''a''0, ''a''1, ...,

where <math>a_0=1</math> and <math>a_k=2a_{k-1}+3\text{ for }k\geq 1.</math>

[[File:1RB0LC 1LA1RB 0RA1LC.png|thumb|Spacetime diagram of the cubic bell {{TM|1RB0LC_1RC1RA_1LA0RB}}.]] [[File:1RB0LC 1LA1RB 0RA1LC explore.png|thumb|300px|Close-up of the cubic bell {{TM|1RB0LC_1RC1RA_1LA0RB}}.]]
=== Cubic bell ===
{{TM|1RB0LC_1LA1RB_0RA1LC}} is an example of a cubic bell with 3 states and 2 symbols.

==== Analysis ====
'''Transcript''': ((A0 B1k B0 A1 C1k C0 A1 C0)(k = n, n-1, .. 1) A0 B0 A1 C0)(n ≥ 0).

[[Category: Zoology]]
[[Category: Stub]]

Bell

2024-11-13T15:54:21Z

Icy: Added page. TODO: Add derivation of transcripts

A '''bell''' is a [[non-halting Turing machine]] whose behavior can be described as a sequence of [[bouncer]]s of increasing size. There are two main variants of bells, depending on whether the bouncers participate in tape growth or not. A bell whose bouncers grow the tape on each bounce is called an '''exponential bell''' or simply '''bell''' for short, while a bell whose bouncers do not grow the tape on each bounce is called a '''cubic bell'''.

== Examples ==

[[File:1RB0LC 1RC1RA 1LA0RB.png|thumb|300px|Spacetime diagram of the bell {{TM|1RB0LC_1RC1RA_1LA0RB}}.]]
=== Exponential bell ===

{{TM|1RB0LC_1RC1RA_1LA0RB}} is an example of an exponential bell with 3 states and 2 symbols.

==== Analysis ====
'''Transcript''': (A0 B0 ((C1 B0)2k (C0 A1)2k+1)(k = 0 .. n-1) (C0 B1)2n (C0 A1)2n C0 (A0 B1)2n+1)n=''a''0, ''a''1, ...,

where <math>a_0=1</math> and <math>a_k=2a_{k-1}+3\text{ for }k\geq 1.</math>

[[File:1RB0LC 1LA1RB 0RA1LC.png|thumb|Spacetime diagram of the cubic bell {{TM|1RB0LC_1RC1RA_1LA0RB}}.]] [[File:1RB0LC 1LA1RB 0RA1LC explore.png|thumb|300px|Close-up of the cubic bell {{TM|1RB0LC_1RC1RA_1LA0RB}}.]]
=== Cubic bell ===
{{TM|1RB0LC_1LA1RB_0RA1LC}} is an example of a cubic bell with 3 states and 2 symbols.

==== Analysis ====
'''Transcript''': ((A0 B1k B0 A1 C1k C0 A1 C0)(k = n, n-1, .. 1) A0 B0 A1 C0)(n ≥ 0).

[[Category: Zoology]]
[[Category: Stub]]

File:1RB0LC 1LA1RB 0RA1LC explore.png

2024-11-13T15:51:55Z

Icy: Icy uploaded a new version of File:1RB0LC 1LA1RB 0RA1LC explore.png

== Summary ==
Close-up of a cubic bell. About 100 steps.

File:1RB0LC 1LA1RB 0RA1LC.png

2024-11-13T15:50:14Z

Icy: Icy reverted File:1RB0LC 1LA1RB 0RA1LC.png to an old version

== Summary ==
An example of a cubic bell. 65536 steps.

File:1RB0LC 1LA1RB 0RA1LC explore.png

2024-11-13T15:44:37Z

Icy: Close-up of a cubic bell. About 100 steps.

== Summary ==
Close-up of a cubic bell. About 100 steps.

File:1RB0LC 1LA1RB 0RA1LC.png

2024-11-13T15:41:32Z

Icy: Icy uploaded a new version of File:1RB0LC 1LA1RB 0RA1LC.png

== Summary ==
An example of a cubic bell. 65536 steps.

File:1RB0LC 1LA1RB 0RA1LC.png

2024-11-13T15:29:13Z

Icy: An example of a cubic bell. 65536 steps.

== Summary ==
An example of a cubic bell. 65536 steps.

File:1RB0LC 1RC1RA 1LA0RB.png

2024-11-13T15:16:31Z

Icy: An example of a bell. 65536 steps.

== Summary ==
An example of a bell. 65536 steps.

Bouncer

2024-11-13T15:03:23Z

Icy: Brevity

[[File:1RB0LB 1LA0RA.png|alt=1RB0LB_1LA0RA|thumb|A close-up of the bouncer {{TM|1RB0LB_1LA0RA}} with 2 states, the smallest number of states for which a bouncer can appear.]]
A '''bouncer''' is a [[non-halting Turing machine]] whose tape head, roughly speaking, alternates back and forth between the two edges of the tape in a linear fashion, growing the tape along one or both edges with each iteration.

== Example ==
{{TM|1RB0LB_1LA0RA}} is an example of a bouncer, and its spacetime diagram is shown in the picture on the right.

=== Analysis ===
'''Transcript''': (A0 (B0 A1)2n+1 B0 (A0 B1)2n+2)n≥0.

The derivation of this transcript is as follows.

'''Shift rules:'''

* B0 A1: <code>B 10< →[2] B <01</code>,
* A0 B1: <code>A >10 →[2] A 01></code>.

'''Bounce rule:'''

* '''B'''n := A0 (B0 A1)2n+1 B0 (A0 B1)2n+2: <code>A 00(102n)>00 →[8n+8] A (102(n+1))></code>

In particular, we have<blockquote>'''B'''n: <code>A 0∞(102n)>0∞ →[8n+8] 0∞(102(n+1))>0∞</code>,</blockquote>which by induction proves that the transcript of <code>1RB0LB_1LA0RA</code> on the all-zeros tape is ('''B'''n)n≥0. Moreover, we have shown that there are 8''n'' + 8 steps between the ''n''th and the (''n''+1)st bounce.

== See also ==

* [https://github.com/bbchallenge/bbchallenge-proofs/blob/build-latex-pdf/deciders/correctness-deciders.pdf Section 7] of bbchallenge's deciders write-up.

[[Category:Zoology]]
[[Category:Stub]]

Bouncer

2024-11-13T15:00:45Z

Icy: /* Example */ Added transcript

[[File:1RB0LB 1LA0RA.png|alt=1RB0LB_1LA0RA|thumb|A close-up of the bouncer {{TM|1RB0LB_1LA0RA}} with 2 states, the smallest number of states for which a bouncer can appear.]]
A '''bouncer''' is a Turing machine whose tape head, roughly speaking, alternates back and forth between the two edges of the tape in a linear fashion, growing the tape along one or both edges with each iteration. A bouncer is a possible classification of [[Non-halting Turing machine|non-halting Turing machines]].

== Example ==
{{TM|1RB0LB_1LA0RA}} is an example of a bouncer, and its spacetime diagram is shown in the picture on the right.

=== Analysis ===
'''Transcript''': (A0 (B0 A1)2n+1 B0 (A0 B1)2n+2)n≥0.

The derivation of this transcript is as follows.

'''Shift rules:'''

* B0 A1: <code>B 10< →[2] B <01</code>,
* A0 B1: <code>A >10 →[2] A 01></code>.

'''Bounce rule:'''

* '''B'''n := A0 (B0 A1)2n+1 B0 (A0 B1)2n+2: <code>A 00(102n)>00 →[8n+8] A (102(n+1))></code>

In particular, we have<blockquote>'''B'''n: <code>A 0∞(102n)>0∞ →[8n+8] 0∞(102(n+1))>0∞</code>,</blockquote>which by induction proves that the transcript of <code>1RB0LB_1LA0RA</code> on the all-zeros tape is ('''B'''n)n≥0. Moreover, we have shown that there are 8''n'' + 8 steps between the ''n''th and the (''n''+1)st bounce.

== See also ==

* [https://github.com/bbchallenge/bbchallenge-proofs/blob/build-latex-pdf/deciders/correctness-deciders.pdf Section 7] of bbchallenge's deciders write-up.

[[Category:Zoology]]
[[Category:Stub]]

Bouncer

2024-11-13T14:23:31Z

Icy: /* Example */

[[File:1RB0LB 1LA0RA.png|alt=1RB0LB_1LA0RA|thumb|A close-up of the bouncer {{TM|1RB0LB_1LA0RA}} with 2 states, the smallest number of states for which a bouncer can appear.]]
A '''bouncer''' is a Turing machine whose tape head, roughly speaking, alternates back and forth between the two edges of the tape in a linear fashion, growing the tape along one or both edges with each iteration. A bouncer is a possible classification of [[Non-halting Turing machine|non-halting Turing machines]].

== Example ==
{{TM|1RB0LB_1LA0RA}} is an example of a bouncer, and its spacetime diagram is shown in the picture on the right.

=== Analysis ===
'''Shift rules:'''

* B0 A1: <code>B 10< →[2] B <01</code>,
* A0 B1: <code>A >10 →[2] A 01></code>.

'''Bounce rule:'''

* '''B'''n := A0 (B0 A1)2n+1 B0 (A0 B1)2n+2: <code>A 00(102n)>00 →[8n+8] A (102(n+1))></code>

In particular, we have

'''B'''n: <code>A 0∞(102n)>0∞ →[8n+8] 0∞(102(n+1))>0∞</code>,

which by induction proves that the transcript of <code>1RB0LB_1LA0RA</code> on the all-zeros tape is ('''B'''n)n≥0. This shows that <code>1RB0LB_1LA0RA</code> is a bouncer. Moreover, we have shown that there are 8''n'' + 8 steps between the ''n''th and the (''n''+1)st bounce.

== See also ==

* [https://github.com/bbchallenge/bbchallenge-proofs/blob/build-latex-pdf/deciders/correctness-deciders.pdf Section 7] of bbchallenge's deciders write-up.

[[Category:Zoology]]
[[Category:Stub]]

Bouncer

2024-11-13T14:18:45Z

Icy: /* Example */ forgot head

[[File:1RB0LB 1LA0RA.png|alt=1RB0LB_1LA0RA|thumb|A close-up of the bouncer {{TM|1RB0LB_1LA0RA}} with 2 states, the smallest number of states for which a bouncer can appear.]]
A '''bouncer''' is a Turing machine whose tape head, roughly speaking, alternates back and forth between the two edges of the tape in a linear fashion, growing the tape along one or both edges with each iteration. A bouncer is a possible classification of [[Non-halting Turing machine|non-halting Turing machines]].

== Example ==
{{TM|1RB0LB_1LA0RA}} is an example of a bouncer, and its spacetime diagram is shown in the picture on the right.

=== Analysis ===
'''Shift rules:'''

* <code>B0 A1: B 10< →[2] B <01</code>
* <code>A0 B1: A >10 →[2] A 01></code>

'''Bounce rule:'''

* <code>'''B'''n := A0 (B0 A1)2n+1 B0 (A0 B1)2n+2: A 00(102n)>00 →[8n+8] A (102(n+1))></code>

In particular,
'''B'''n: A 0∞(102n)>0∞ →[8n+8] 0∞(102(n+1))>0∞
thus proving by induction that the transcript of <code>1RB0LB_1LA0RA</code> on the all zeros tape is <code>('''B'''n)n≥0</code>, which shows that <code>1RB0LB_1LA0RA</code> is a bouncer. Moreover, we have shown that there are 8''n'' + 8 steps between the ''n''th and the (''n''+1)st bounce.

== See also ==

* [https://github.com/bbchallenge/bbchallenge-proofs/blob/build-latex-pdf/deciders/correctness-deciders.pdf Section 7] of bbchallenge's deciders write-up.

[[Category:Zoology]]
[[Category:Stub]]

Bouncer

2024-11-13T14:17:04Z

Icy: /* Analysis */ Added number of steps

[[File:1RB0LB 1LA0RA.png|alt=1RB0LB_1LA0RA|thumb|A close-up of the bouncer {{TM|1RB0LB_1LA0RA}} with 2 states, the smallest number of states for which a bouncer can appear.]]
A '''bouncer''' is a Turing machine whose tape head, roughly speaking, alternates back and forth between the two edges of the tape in a linear fashion, growing the tape along one or both edges with each iteration. A bouncer is a possible classification of [[Non-halting Turing machine|non-halting Turing machines]].

== Example ==
{{TM|1RB0LB_1LA0RA}} is an example of a bouncer, and its spacetime diagram is shown in the picture on the right.

=== Analysis ===
'''Shift rules:'''

* <code>B0 A1: B 10< →[2] B <01</code>
* <code>A0 B1: A >10 →[2] A 01></code>

'''Bounce rule:'''

* <code>'''B'''n := A0 (B0 A1)2n+1 B0 (A0 B1)2n+2: A 00(102n)>00 →[8n+8] A (102(n+1))></code>

In particular,
'''B'''n: A 0∞(102n)0∞ →[8n+8] 0∞(102(n+1))0∞
thus proving by induction that the transcript of <code>1RB0LB_1LA0RA</code> on the all zeros tape is <code>('''B'''n)n≥0</code>, which shows that <code>1RB0LB_1LA0RA</code> is a bouncer. Moreover, we have shown that there are 8''n'' + 8 steps between the ''n''th and the (''n''+1)st bounce.

== See also ==

* [https://github.com/bbchallenge/bbchallenge-proofs/blob/build-latex-pdf/deciders/correctness-deciders.pdf Section 7] of bbchallenge's deciders write-up.

[[Category:Zoology]]
[[Category:Stub]]

Bouncer

2024-11-13T14:13:40Z

Icy: Added example of bouncer + analysis

[[File:1RB0LB 1LA0RA.png|alt=1RB0LB_1LA0RA|thumb|A close-up of the bouncer {{TM|1RB0LB_1LA0RA}} with 2 states, the smallest number of states for which a bouncer can appear.]]
A '''bouncer''' is a Turing machine whose tape head, roughly speaking, alternates back and forth between the two edges of the tape in a linear fashion, growing the tape along one or both edges with each iteration. A bouncer is a possible classification of [[Non-halting Turing machine|non-halting Turing machines]].

== Example ==
{{TM|1RB0LB_1LA0RA}} is an example of a bouncer, and its spacetime diagram is shown in the picture on the right.

=== Analysis ===
'''Shift rules:'''

* <code>B0 A1: B 10< →[2] B <01</code>
* <code>A0 B1: A >10 →[2] A 01></code>

'''Bounce rule:'''

* <code>'''B'''n := A0 (B0 A1)2n+1 B0 (A0 B1)2n+2: A 00(102n)>00 → A (102(n+1))></code>

In particular,
'''B'''n: A 0∞(102n)0∞ → 0∞(102(n+1))0∞
thus proving by induction that the transcript of <code>1RB0LB_1LA0RA</code> on the all zeros tape is <code>('''B'''n)n≥0</code>, which shows that <code>1RB0LB_1LA0RA</code> is a bouncer.

== See also ==

* [https://github.com/bbchallenge/bbchallenge-proofs/blob/build-latex-pdf/deciders/correctness-deciders.pdf Section 7] of bbchallenge's deciders write-up.

[[Category:Zoology]]
[[Category:Stub]]

1RB0RC 1LB1LD 0RA0LD 1LA1RC

2024-11-13T03:02:18Z

Icy: /* Shift rule */ Added state and note

{{machine|1RB0RC_1LB1LD_0RA0LD_1LA1RC}}[[File:1RB0RC 1LB1LD 0RA0LD 1LA1RC.png|thumb|A spacetime diagram of '''p17620 s158491''' up to 262144 steps.]]'''{{TM|1RB0RC_1LB1LD_0RA0LD_1LA1RC}}''' (also known as '''p17620 s158491''' or '''p17620''') is a non-halting Turing machine with 4 states and 2 symbols. It is a [[translated cycler]] with period 17,620, preperiod 158,491, and offset 118. The behavior of this Turing machine before entering its period can be classified as [[spaghetti]], but as shown below, it is possible to analyze its computation to some extent.

== Analysis ==

=== Summary ===
When the head is going from right to left, it takes the 01-run length encoding (separated by 1s) of the left side, doubles each run length, and interprets it as a 1-run length encoding (separated by 0s) and outputs it to the right side. It does this until it hits two consecutive 0s in a row, at which point it changes direction.

When the head is going from left to right, the behavior is more complicated but has a mod 3 theme. A run length that is 0 mod 3 causes the head to change direction.

=== Details ===
We adopt the following notation:

* To the left of the head, we represent strings in 01-run length encoding, separated by 1s. That is, the non-negative integer ''n'' represents the string <code>01n 1</code>. In addition, the vertical bar <code>|</code> represents a 0 which is not part of any 01 blocks.
* To the right of the head, we represent strings in 1-run length encoding, separated by 0s. That is, the non-negative integer ''n'' represents the string <code>1n 0</code>.
* The variables ''x'' and ''y'' stand for integers.
* Every macro transition in the below analysis goes from state A to state A.

==== Example ====
At step 1656, the machine's tape is
A 0∞ 1011101101011010110110100110 >0 00111101111 0∞.
In the aforementioned run length encoding, this is
A 0∞ |2012211|10| >0 0044 0∞.
Note that the first integer is a 2 because we "borrow" a 0 from the leading 0∞.

==== Going left ====
T1: A x|1| >0 0y →[13] A x+1| >0 (y+2)
T2: A x|10| >0 0y →[16] A x+1| >0 0(y+2)
T3: A x|100| >0 0y →[19] A x+1| >0 00(y+2)
T4: A x|0|0| >0 0 →[19] A (x+1)0| >0

T5: A (x+1)| >0 0y →[13] A x0| >0 (y+2)
T6: A (x+1)0| >0 0y →[16] A x0| >0 0(y+2)
T7: A (x+1)00| >0 0y →[19] A x0| >0 00(y+2)
T8: A (x+1)000| >0 0y →[22] A x0| >0 000(y+2)
Combining these, we can show, for any integers ''x'' and ''b'' and any string ''s'':
T9: A x|sb0| >0 0y → A x0| >0 0 (2*s) (y+2*(b+1))

==== Going right ====
T10: A x| >0 (y+3) →[15] A (x+1)0| >0 y
T10': A x| >0 (y+6) →[30] A (x+1)10| >0 y

T11: A x| >0 20 →[27] A (x+2)0| >0
T12: A x| >0 2(y+2) →[17] A (x+1)|1| >0 y
T13: A x| >0 4 →[21] A (x+1)1| >0

The first thing we can notice from the previous section is that we only need to analyze tapes whose integers to the right of the head (under 1-run length encoding) are all even. (This doesn't mean it is a strict invariant, but it is an invariant when considering macro transitions only.)

T10' tells us that it suffices to understand what happens when the first integer to the right of the head is 0, 2, 4. If it is 0, we have changed directions and are now going left. Otherwise, this is answered by T11 to T13.

==== Some other interesting macro-rules ====
T14: A | >0 80 →[127] A 0| >0 0026

== Shift rule ==
The shift rule that is responsible for this machine being a translated cycler is
'''û r''' →[17620] '''r' û''',
where

* '''û''' = <code>A >010111111110110110110111101101111110111111011011011011110111111110110110110110111111110110110110111111110110111111</code>,
* '''r''' = <code>0118</code>,
* '''r'''' = <code>1011011010101101010010101011011011011010110110110110101010110110110110110100101101011010101011011011011011011011010110</code>.

In the run length encoding described above, this is
* '''û''' = <code>A >01822242662224822228222826</code>,
* '''r''' = <code>0118</code>,
* '''r'''' = <code>2132|41112111411111|2241111112</code>. (Note: the 2 at the beginning borrows a 0 from the end of the previous instance of '''r''''.)

== Permutations ==
The Turing machine '''1RB0RC_1LB1LD_0RA0LD_1LA1RC''' has one LNF permutation '''1RB1LC_1LD0LC_0LB0RA_1RD1RA'''. This Turing machine is also a translated cycler with period 17620, but with preperiod 157757 and offset -118.

1RB0RC 1LB1LD 0RA0LD 1LA1RC

2024-11-13T00:29:20Z

Icy: /* Shift rule */

{{machine|1RB0RC_1LB1LD_0RA0LD_1LA1RC}}[[File:1RB0RC 1LB1LD 0RA0LD 1LA1RC.png|thumb|A spacetime diagram of '''p17620 s158491''' up to 262144 steps.]]'''{{TM|1RB0RC_1LB1LD_0RA0LD_1LA1RC}}''' (also known as '''p17620 s158491''' or '''p17620''') is a non-halting Turing machine with 4 states and 2 symbols. It is a [[translated cycler]] with period 17,620, preperiod 158,491, and offset 118. The behavior of this Turing machine before entering its period can be classified as [[spaghetti]], but as shown below, it is possible to analyze its computation to some extent.

== Analysis ==

=== Summary ===
When the head is going from right to left, it takes the 01-run length encoding (separated by 1s) of the left side, doubles each run length, and interprets it as a 1-run length encoding (separated by 0s) and outputs it to the right side. It does this until it hits two consecutive 0s in a row, at which point it changes direction.

When the head is going from left to right, the behavior is more complicated but has a mod 3 theme. A run length that is 0 mod 3 causes the head to change direction.

=== Details ===
We adopt the following notation:

* To the left of the head, we represent strings in 01-run length encoding, separated by 1s. That is, the non-negative integer ''n'' represents the string <code>01n 1</code>. In addition, the vertical bar <code>|</code> represents a 0 which is not part of any 01 blocks.
* To the right of the head, we represent strings in 1-run length encoding, separated by 0s. That is, the non-negative integer ''n'' represents the string <code>1n 0</code>.
* The variables ''x'' and ''y'' stand for integers.
* Every macro transition in the below analysis goes from state A to state A.

==== Example ====
At step 1656, the machine's tape is
A 0∞ 1011101101011010110110100110 >0 00111101111 0∞.
In the aforementioned run length encoding, this is
A 0∞ |2012211|10| >0 0044 0∞.
Note that the first integer is a 2 because we "borrow" a 0 from the leading 0∞.

==== Going left ====
T1: A x|1| >0 0y →[13] A x+1| >0 (y+2)
T2: A x|10| >0 0y →[16] A x+1| >0 0(y+2)
T3: A x|100| >0 0y →[19] A x+1| >0 00(y+2)
T4: A x|0|0| >0 0 →[19] A (x+1)0| >0

T5: A (x+1)| >0 0y →[13] A x0| >0 (y+2)
T6: A (x+1)0| >0 0y →[16] A x0| >0 0(y+2)
T7: A (x+1)00| >0 0y →[19] A x0| >0 00(y+2)
T8: A (x+1)000| >0 0y →[22] A x0| >0 000(y+2)
Combining these, we can show, for any integers ''x'' and ''b'' and any string ''s'':
T9: A x|sb0| >0 0y → A x0| >0 0 (2*s) (y+2*(b+1))

==== Going right ====
T10: A x| >0 (y+3) →[15] A (x+1)0| >0 y
T10': A x| >0 (y+6) →[30] A (x+1)10| >0 y

T11: A x| >0 20 →[27] A (x+2)0| >0
T12: A x| >0 2(y+2) →[17] A (x+1)|1| >0 y
T13: A x| >0 4 →[21] A (x+1)1| >0

The first thing we can notice from the previous section is that we only need to analyze tapes whose integers to the right of the head (under 1-run length encoding) are all even. (This doesn't mean it is a strict invariant, but it is an invariant when considering macro transitions only.)

T10' tells us that it suffices to understand what happens when the first integer to the right of the head is 0, 2, 4. If it is 0, we have changed directions and are now going left. Otherwise, this is answered by T11 to T13.

==== Some other interesting macro-rules ====
T14: A | >0 80 →[127] A 0| >0 0026

== Shift rule ==
The shift rule that is responsible for this machine being a translated cycler is
'''û r''' →[17620] '''r' û''',
where

* '''û''' = <code>>010111111110110110110111101101111110111111011011011011110111111110110110110110111111110110110110111111110110111111</code>,
* '''r''' = <code>0118</code>,
* '''r'''' = <code>1011011010101101010010101011011011011010110110110110101010110110110110110100101101011010101011011011011011011011010110</code>.

In the run length encoding described above, this is
* '''û''' = <code>>01822242662224822228222826</code>,
* '''r''' = <code>0118</code>,
* '''r'''' = <code>2132|41112111411111|2241111112</code>.

== Permutations ==
The Turing machine '''1RB0RC_1LB1LD_0RA0LD_1LA1RC''' has one LNF permutation '''1RB1LC_1LD0LC_0LB0RA_1RD1RA'''. This Turing machine is also a translated cycler with period 17620, but with preperiod 157757 and offset -118.

1RB0RC 1LB1LD 0RA0LD 1LA1RC

2024-11-13T00:26:26Z

Icy: /* Shift rule */

{{machine|1RB0RC_1LB1LD_0RA0LD_1LA1RC}}[[File:1RB0RC 1LB1LD 0RA0LD 1LA1RC.png|thumb|A spacetime diagram of '''p17620 s158491''' up to 262144 steps.]]'''{{TM|1RB0RC_1LB1LD_0RA0LD_1LA1RC}}''' (also known as '''p17620 s158491''' or '''p17620''') is a non-halting Turing machine with 4 states and 2 symbols. It is a [[translated cycler]] with period 17,620, preperiod 158,491, and offset 118. The behavior of this Turing machine before entering its period can be classified as [[spaghetti]], but as shown below, it is possible to analyze its computation to some extent.

== Analysis ==

=== Summary ===
When the head is going from right to left, it takes the 01-run length encoding (separated by 1s) of the left side, doubles each run length, and interprets it as a 1-run length encoding (separated by 0s) and outputs it to the right side. It does this until it hits two consecutive 0s in a row, at which point it changes direction.

When the head is going from left to right, the behavior is more complicated but has a mod 3 theme. A run length that is 0 mod 3 causes the head to change direction.

=== Details ===
We adopt the following notation:

* To the left of the head, we represent strings in 01-run length encoding, separated by 1s. That is, the non-negative integer ''n'' represents the string <code>01n 1</code>. In addition, the vertical bar <code>|</code> represents a 0 which is not part of any 01 blocks.
* To the right of the head, we represent strings in 1-run length encoding, separated by 0s. That is, the non-negative integer ''n'' represents the string <code>1n 0</code>.
* The variables ''x'' and ''y'' stand for integers.
* Every macro transition in the below analysis goes from state A to state A.

==== Example ====
At step 1656, the machine's tape is
A 0∞ 1011101101011010110110100110 >0 00111101111 0∞.
In the aforementioned run length encoding, this is
A 0∞ |2012211|10| >0 0044 0∞.
Note that the first integer is a 2 because we "borrow" a 0 from the leading 0∞.

==== Going left ====
T1: A x|1| >0 0y →[13] A x+1| >0 (y+2)
T2: A x|10| >0 0y →[16] A x+1| >0 0(y+2)
T3: A x|100| >0 0y →[19] A x+1| >0 00(y+2)
T4: A x|0|0| >0 0 →[19] A (x+1)0| >0

T5: A (x+1)| >0 0y →[13] A x0| >0 (y+2)
T6: A (x+1)0| >0 0y →[16] A x0| >0 0(y+2)
T7: A (x+1)00| >0 0y →[19] A x0| >0 00(y+2)
T8: A (x+1)000| >0 0y →[22] A x0| >0 000(y+2)
Combining these, we can show, for any integers ''x'' and ''b'' and any string ''s'':
T9: A x|sb0| >0 0y → A x0| >0 0 (2*s) (y+2*(b+1))

==== Going right ====
T10: A x| >0 (y+3) →[15] A (x+1)0| >0 y
T10': A x| >0 (y+6) →[30] A (x+1)10| >0 y

T11: A x| >0 20 →[27] A (x+2)0| >0
T12: A x| >0 2(y+2) →[17] A (x+1)|1| >0 y
T13: A x| >0 4 →[21] A (x+1)1| >0

The first thing we can notice from the previous section is that we only need to analyze tapes whose integers to the right of the head (under 1-run length encoding) are all even. (This doesn't mean it is a strict invariant, but it is an invariant when considering macro transitions only.)

T10' tells us that it suffices to understand what happens when the first integer to the right of the head is 0, 2, 4. If it is 0, we have changed directions and are now going left. Otherwise, this is answered by T11 to T13.

==== Some other interesting macro-rules ====
T14: A | >0 80 →[127] A 0| >0 0026

== Shift rule ==
The shift rule that is responsible for this machine being a translated cycler is
'''û r''' →[17620] '''r' û''',
where

* '''û''' = <code>>010111111110110110110111101101111110111111011011011011110111111110110110110110111111110110110110111111110110111111</code>,
* '''r''' = <code>0118</code>,
* '''r'''' = <code>1011011010101101010010101011011011011010110110110110101010110110110110110100101101011010101011011011011011011011010110</code>.

In the run length encoding described above, this is
* '''û''' = <code>>01822242662224822228222826</code>,
* '''r''' = <code>0118</code>,
* '''r'''' = <code>|2132|41112111411111|22411111120|</code>.

== Permutations ==
The Turing machine '''1RB0RC_1LB1LD_0RA0LD_1LA1RC''' has one LNF permutation '''1RB1LC_1LD0LC_0LB0RA_1RD1RA'''. This Turing machine is also a translated cycler with period 17620, but with preperiod 157757 and offset -118.

1RB0RC 1LB1LD 0RA0LD 1LA1RC

2024-11-13T00:26:07Z

Icy: /* Shift rule */

{{machine|1RB0RC_1LB1LD_0RA0LD_1LA1RC}}[[File:1RB0RC 1LB1LD 0RA0LD 1LA1RC.png|thumb|A spacetime diagram of '''p17620 s158491''' up to 262144 steps.]]'''{{TM|1RB0RC_1LB1LD_0RA0LD_1LA1RC}}''' (also known as '''p17620 s158491''' or '''p17620''') is a non-halting Turing machine with 4 states and 2 symbols. It is a [[translated cycler]] with period 17,620, preperiod 158,491, and offset 118. The behavior of this Turing machine before entering its period can be classified as [[spaghetti]], but as shown below, it is possible to analyze its computation to some extent.

== Analysis ==

=== Summary ===
When the head is going from right to left, it takes the 01-run length encoding (separated by 1s) of the left side, doubles each run length, and interprets it as a 1-run length encoding (separated by 0s) and outputs it to the right side. It does this until it hits two consecutive 0s in a row, at which point it changes direction.

When the head is going from left to right, the behavior is more complicated but has a mod 3 theme. A run length that is 0 mod 3 causes the head to change direction.

=== Details ===
We adopt the following notation:

* To the left of the head, we represent strings in 01-run length encoding, separated by 1s. That is, the non-negative integer ''n'' represents the string <code>01n 1</code>. In addition, the vertical bar <code>|</code> represents a 0 which is not part of any 01 blocks.
* To the right of the head, we represent strings in 1-run length encoding, separated by 0s. That is, the non-negative integer ''n'' represents the string <code>1n 0</code>.
* The variables ''x'' and ''y'' stand for integers.
* Every macro transition in the below analysis goes from state A to state A.

==== Example ====
At step 1656, the machine's tape is
A 0∞ 1011101101011010110110100110 >0 00111101111 0∞.
In the aforementioned run length encoding, this is
A 0∞ |2012211|10| >0 0044 0∞.
Note that the first integer is a 2 because we "borrow" a 0 from the leading 0∞.

==== Going left ====
T1: A x|1| >0 0y →[13] A x+1| >0 (y+2)
T2: A x|10| >0 0y →[16] A x+1| >0 0(y+2)
T3: A x|100| >0 0y →[19] A x+1| >0 00(y+2)
T4: A x|0|0| >0 0 →[19] A (x+1)0| >0

T5: A (x+1)| >0 0y →[13] A x0| >0 (y+2)
T6: A (x+1)0| >0 0y →[16] A x0| >0 0(y+2)
T7: A (x+1)00| >0 0y →[19] A x0| >0 00(y+2)
T8: A (x+1)000| >0 0y →[22] A x0| >0 000(y+2)
Combining these, we can show, for any integers ''x'' and ''b'' and any string ''s'':
T9: A x|sb0| >0 0y → A x0| >0 0 (2*s) (y+2*(b+1))

==== Going right ====
T10: A x| >0 (y+3) →[15] A (x+1)0| >0 y
T10': A x| >0 (y+6) →[30] A (x+1)10| >0 y

T11: A x| >0 20 →[27] A (x+2)0| >0
T12: A x| >0 2(y+2) →[17] A (x+1)|1| >0 y
T13: A x| >0 4 →[21] A (x+1)1| >0

The first thing we can notice from the previous section is that we only need to analyze tapes whose integers to the right of the head (under 1-run length encoding) are all even. (This doesn't mean it is a strict invariant, but it is an invariant when considering macro transitions only.)

T10' tells us that it suffices to understand what happens when the first integer to the right of the head is 0, 2, 4. If it is 0, we have changed directions and are now going left. Otherwise, this is answered by T11 to T13.

==== Some other interesting macro-rules ====
T14: A | >0 80 →[127] A 0| >0 0026

== Shift rule ==
The shift rule that is responsible for this machine being a translated cycler is
'''û r''' →[17620] '''r' û''',
where

* '''û''' = <code>>010111111110110110110111101101111110111111011011011011110111111110110110110110111111110110110110111111110110111111</code>,
* '''r''' = <code>0118</code>,
* '''r'''' = <code>1011011010101101010010101011011011011010110110110110101010110110110110110100101101011010101011011011011011011011010110</code>.

In the run length encoding describe above, this is
* '''û''' = <code>>01822242662224822228222826</code>,
* '''r''' = <code>0118</code>,
* '''r'''' = <code>|2132|41112111411111|22411111120|</code>.

== Permutations ==
The Turing machine '''1RB0RC_1LB1LD_0RA0LD_1LA1RC''' has one LNF permutation '''1RB1LC_1LD0LC_0LB0RA_1RD1RA'''. This Turing machine is also a translated cycler with period 17620, but with preperiod 157757 and offset -118.

1RB0RC 1LB1LD 0RA0LD 1LA1RC

2024-11-13T00:25:56Z

Icy: Shift rule

{{machine|1RB0RC_1LB1LD_0RA0LD_1LA1RC}}[[File:1RB0RC 1LB1LD 0RA0LD 1LA1RC.png|thumb|A spacetime diagram of '''p17620 s158491''' up to 262144 steps.]]'''{{TM|1RB0RC_1LB1LD_0RA0LD_1LA1RC}}''' (also known as '''p17620 s158491''' or '''p17620''') is a non-halting Turing machine with 4 states and 2 symbols. It is a [[translated cycler]] with period 17,620, preperiod 158,491, and offset 118. The behavior of this Turing machine before entering its period can be classified as [[spaghetti]], but as shown below, it is possible to analyze its computation to some extent.

== Analysis ==

=== Summary ===
When the head is going from right to left, it takes the 01-run length encoding (separated by 1s) of the left side, doubles each run length, and interprets it as a 1-run length encoding (separated by 0s) and outputs it to the right side. It does this until it hits two consecutive 0s in a row, at which point it changes direction.

When the head is going from left to right, the behavior is more complicated but has a mod 3 theme. A run length that is 0 mod 3 causes the head to change direction.

=== Details ===
We adopt the following notation:

* To the left of the head, we represent strings in 01-run length encoding, separated by 1s. That is, the non-negative integer ''n'' represents the string <code>01n 1</code>. In addition, the vertical bar <code>|</code> represents a 0 which is not part of any 01 blocks.
* To the right of the head, we represent strings in 1-run length encoding, separated by 0s. That is, the non-negative integer ''n'' represents the string <code>1n 0</code>.
* The variables ''x'' and ''y'' stand for integers.
* Every macro transition in the below analysis goes from state A to state A.

==== Example ====
At step 1656, the machine's tape is
A 0∞ 1011101101011010110110100110 >0 00111101111 0∞.
In the aforementioned run length encoding, this is
A 0∞ |2012211|10| >0 0044 0∞.
Note that the first integer is a 2 because we "borrow" a 0 from the leading 0∞.

==== Going left ====
T1: A x|1| >0 0y →[13] A x+1| >0 (y+2)
T2: A x|10| >0 0y →[16] A x+1| >0 0(y+2)
T3: A x|100| >0 0y →[19] A x+1| >0 00(y+2)
T4: A x|0|0| >0 0 →[19] A (x+1)0| >0

T5: A (x+1)| >0 0y →[13] A x0| >0 (y+2)
T6: A (x+1)0| >0 0y →[16] A x0| >0 0(y+2)
T7: A (x+1)00| >0 0y →[19] A x0| >0 00(y+2)
T8: A (x+1)000| >0 0y →[22] A x0| >0 000(y+2)
Combining these, we can show, for any integers ''x'' and ''b'' and any string ''s'':
T9: A x|sb0| >0 0y → A x0| >0 0 (2*s) (y+2*(b+1))

==== Going right ====
T10: A x| >0 (y+3) →[15] A (x+1)0| >0 y
T10': A x| >0 (y+6) →[30] A (x+1)10| >0 y

T11: A x| >0 20 →[27] A (x+2)0| >0
T12: A x| >0 2(y+2) →[17] A (x+1)|1| >0 y
T13: A x| >0 4 →[21] A (x+1)1| >0

The first thing we can notice from the previous section is that we only need to analyze tapes whose integers to the right of the head (under 1-run length encoding) are all even. (This doesn't mean it is a strict invariant, but it is an invariant when considering macro transitions only.)

T10' tells us that it suffices to understand what happens when the first integer to the right of the head is 0, 2, 4. If it is 0, we have changed directions and are now going left. Otherwise, this is answered by T11 to T13.

==== Some other interesting macro-rules ====
T14: A | >0 80 →[127] A 0| >0 0026

== Shift rule ==
The shift rule that is responded for this machine being a translated cycler is
'''û r''' →[17620] '''r' û''',
where

* '''û''' = <code>>010111111110110110110111101101111110111111011011011011110111111110110110110110111111110110110110111111110110111111</code>,
* '''r''' = <code>0118</code>,
* '''r'''' = <code>1011011010101101010010101011011011011010110110110110101010110110110110110100101101011010101011011011011011011011010110</code>.

In the run length encoding describe above, this is
* '''û''' = <code>>01822242662224822228222826</code>,
* '''r''' = <code>0118</code>,
* '''r'''' = <code>|2132|41112111411111|22411111120|</code>.

== Permutations ==
The Turing machine '''1RB0RC_1LB1LD_0RA0LD_1LA1RC''' has one LNF permutation '''1RB1LC_1LD0LC_0LB0RA_1RD1RA'''. This Turing machine is also a translated cycler with period 17620, but with preperiod 157757 and offset -118.

User:Icy

2024-11-11T22:56:25Z

Icy: /* Interesting Turing machines */

Hey! It's Icy 🧊. I'm also sometimes known as Fiery 🔥.

I like to do a lot of things. Lately one of them has been studying the behaviors of non-halting Turing machines.

I made a nice and fast Turing machine visualizer over at https://fiery.pages.dev/turing. Try it!

[https://1drv.ms/x/s!AsDOgQh8h9nChfRbOkzxJllwONZeQA?e=ef4q6C My database of Turing machines (.xlsx)]

== Interesting Turing machines ==

=== 5 states ===
* [https://fiery.pages.dev/turing/1RB0LC_0LA0RD_1LA1LC_1RE0RA_1LC0RB 1RB0LC_0LA0RD_1LA1LC_1RE0RA_1LC0RB] (checkerboard-like fractal?)
* [https://fiery.pages.dev/turing/1RB0LC_0LA1RD_1LA1LB_1RE0RA_0LC0RD 1RB0LC_0LA1RD_1LA1LB_1RE0RA_0LC0RD] (bell-counter thingy)
* [https://fiery.pages.dev/turing/1RB0LC_0LA1RD_1LA1LC_1RC0RE_1LE0RC 1RB0LC_0LA1RD_1LA1LC_1RC0RE_1LE0RC]
* [https://fiery.pages.dev/turing/1RB0LC_0LA1RD_1LA1LC_1RB0RE_0RB1RE 1RB0LC_0LA1RD_1LA1LC_1RB0RE_0RB1RE] (bouncer with Sierpinski triangle etched)
* [https://fiery.pages.dev/turing/1RB0LC_0LA1RD_1LA0RD_1LB1RE_0RD0RE 1RB0LC_0LA1RD_1LA0RD_1LB1RE_0RD0RE] (translated cycler '''p197394-s81173''')
* [https://fiery.pages.dev/turing/1RB0LC_0LA0RD_1LA0LE_1RC0RD_1RE0RA 1RB0LC_0LA0RD_1LA0LE_1RC0RD_1RE0RA] (complex and unaccelerable, has translated cycler qualities)
* [https://fiery.pages.dev/turing/1RB0LC_0LA0RD_0RD1LA_1LE1RE_1LA0RB 1RB0LC_0LA0RD_0RD1LA_1LE1RE_1LA0RB]
* [https://fiery.pages.dev/turing/1RB0RC_0LD1RA_0RE1LB_0LC1LC_1RA0RD 1RB0RC_0LD1RA_0RE1LB_0LC1LC_1RA0RD] (Christmas tree counter)

=== 3 × 3 ===

* [https://fiery.pages.dev/turing/1RB1RA2RA_0LB2LC1RB_2RA2LB1LC 1RB1RA2RA_0LB2LC1RB_2RA2LB1LC] quasi-bouncer with cool checkerboard pattern

* [https://fiery.pages.dev/turing/1RB1LC2LC_0LA2RB1LB_2RB0LA1RC 1RB1LC2LC_0LA2RB1LB_2RB0LA1RC] quartic bell, structural bouncer with linearly expanding exons

== My pages ==

* [[Non-halting Turing machine]]
* [[1RB0RC 1LB1LD 0RA0LD 1LA1RC]]

== Current sandboxes ==

2024-11-11T14:32:29Z

Icy:

An example of a spaghetti. 65536 steps.