1RB0RC 1LB1LD 0RA0LD 1LA1RC

1RB0RC_1LB1LD_0RA0LD_1LA1RC (bbch) (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 01ⁿ 1. In addition, the vertical bar | 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 1ⁿ 0.
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  →  x0| >0 0 (2*s) (y+2*(b+1))

Going right

T10:  A  x| >0 (y+3)   →[15]    (x+1)0| >0 y
T11:  A  x| >0 20      →[27]    (x+2)0| >0
T12:  A  x| >0 2(y+2)  →[17]   (x+1)|1| >0 y
T13:  A  x| >0 4       →[21]    (x+1)1| >0
T14:  A  x| >0 6       →[30]   (x+1)10| >0 0
T15:  A   | >0 80      →[127]        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.