How does Rogozhin's (2, 18) universal turing machine work?

Question

I am trying to understand Rogozhin's (2, 18) universal turing machine by stepping through a simple 2-tag encoding that I believe should loop forever:

a -> aa

For example, using an initial input of aaa:

aaa
  aaa
    aaa
      .... etc

Apologies for the extremely specific question, but it's what I've narrowed my issue down to and I've been stuck for a while!

Following the instructions in part 10 / pp22 and page 6 I believe this system should be encoded as:

c⃖₁ c⃖₁ b  b  1  b  1  b >b  1  c  1  c  1  c
|P2   |P1           |P0   |Ar   |As   |At  

Running this, however, results in termination rather than an infinite loop. Following the trace I have managed to identify something I can't explain and that seems wrong, but have not been able to figure out a resolution.

Following the first stage of modelling:

On the first stage, the UTM searches the code P, corresponding to the code A, and then the UTM deletes the codes A, and A, (i.e. it deletes the mark between them)

...

if the head of the UTM moves to the right and meets the mark c, then the first stage of modelling is over. The UTM deletes this mark and the second stage of modelling begins

Gives the following trace:

c⃖₁ c⃖₁ b  b  1  b  1  b >b  1  c  1  c  1  c
c⃖₁ c⃖₁ b  b  1  b  1  b  b⃖ >1  c  1  c  1  c
c⃖₁ c⃖₁ b  b  1  b  1  b >b⃖  c₂ c  1  c  1  c
c⃖₁ c⃖₁ b  b  1  b  1 >b  b  c₂ c  1  c  1  c
c⃖₁ c⃖₁ b  b  1  b  1  b⃖ >b  c₂ c  1  c  1  c
c⃖₁ c⃖₁ b  b  1  b  1  b⃖  b⃖ >c₂ c  1  c  1  c
c⃖₁ c⃖₁ b  b  1  b  1  b⃖  b⃖  1⃖ >c  1  c  1  c
c⃖₁ c⃖₁ b  b  1  b  1  b⃖  b⃖ >1⃖  1⃗  1  c  1  c

At this stage, Rogozhin claims the tape should be:

P₂P₁P'₀R'A_t

Notice in particular R'A_t

R’ consists of 1⃖ and 1⃗ and the head of the UTM is located on the R’ in the state Q2

But to me, it appears that only A_r has been deleted!?

c⃖₁ c⃖₁ b  b  1  b  1  b⃖  b⃖ >1⃖  1⃗  1  c  1  c
|P2   |P1           |P'0  |R'   |As!! |At  

I would expect something like:

c⃖₁ c⃖₁ b  b  1  b  1  b⃖  b⃖ >1⃖  1⃗  1⃖  1⃗  1  c
|P2   |P1           |P'0  |R'         |At  

I have identified the following potential errors I have made, but have double checked each and have not been able to identify any:

• Understanding of 2-tag system.
• Encoding of 2-tag system.
• Execution of rules (programming bug).
• Formatting of trace.
• Interpretation of trace.

Can anyone spot what I'm missing? Am hoping it's something obvious!

Supplementary materials

• Spreadsheet to generate tape
• Ruby program I'm using to generate traces
• Full trace showing that aaa terminates when I think it shouldn't
• Original motivation and how I ended up here in the first place

Answer 1

I see (at least) two errors:

The head position should be at the beginning of $S$; and there is an extra 1 at each $P_i, i > 1$: $P_i = bb 1^{N_{i_{m_i}}}1b....b1^{N_{i_2}}1b1^{N_{i_1}}$

c⃖₁ c⃖₁ b  b  1  1  b  1  b b >1  c  1  c  1  c
                 ^            ^
                !!!          !!!

Don't forget that the rest of the tape should be fille with $1^{\leftarrow}$ (the balnk symbol).

A few years ago I also examined its behaviour; you can find the javascript version I made here: click "Small" to load it, then fill the tape (click on the second gray row to place the head), and click "Step". You can compare it with your implementation.