1RB0RC 1LB1LD 0RA0LD 1LA1RC

A spacetime diagram of p17620 s158491 up to 262144 steps.

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, 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 01n 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 1n 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  →  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

• û = A >010111111110110110110111101101111110111111011011011011110111111110110110110110111111110110110110111111110110111111,
• r = 0118,
• r' = 1011011010101101010010101011011011011010110110110110101010110110110110110100101101011010101011011011011011011011010110.

In the run length encoding described above, this is

• û = A >01822242662224822228222826,
• r = 0118,
• r' = 2132|41112111411111|2241111112. (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.