View source for 1RB0RC 1LB1LD 0RA0LD 1LA1RC

{{machine|1RB0RC_1LB1LD_0RA0LD_1LA1RC}}

[[File:1RB0RC 1LB1LD 0RA0LD 1LA1RC.png|thumb]]'''{{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 and preperiod 158,491. 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>01<sup>n</sup> 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>1<sup>n</sup> 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<sup>∞</sup> 1011101101011010110110100110 >0 00111101111 0<sup>∞</sup>.
In the aforementioned run length encoding, this is 
 A 0<sup>∞</sup> |2012211|10| >0 0044 0<sup>∞</sup>.
Note that the first integer is a 2 because we "borrow" a 0 from the leading 0<sup>∞</sup>.

==== 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
 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
 T14:  A  x| >0 6       →[30]   A (x+1)10| >0 0
 T15:  A   | >0 80      →[127]  A       0| >0 0026
It is much less clear what is going on here, but we can see the mod 3 theme, as T10 decrements the integer to the right of the head by 3.

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