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:

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


Notice in particular R'At

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


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

  • $\begingroup$ "extra in at each P" doh! Good catch. I must have read that formula 10 times. "and the head of the UTM is located on the left side of the code S in the state q1 (in the case of the machine in UTM(2,18) the head of the UTM is located on the right side of the code PO in the state 41)." This sentence is why I placed the head where I did - the initial part suggests S but the bracketed part seems pretty clear about putting on right side of P0 rather than S. "blank symbol" got that, am just not printing it in my tracer :) "JS version" this will be most helpful, thanks $\endgroup$ Commented May 30, 2019 at 11:44
  • $\begingroup$ I found two other errors: my rules for bR1 and bL1 in Q2 were wrong. Now it appears to work! All of these errors though (including the ones you pointed out), don't actually change the trace of the tape up to the point in my question, so I'm still unsure how to interpret what rogozhin meant here. $\endgroup$ Commented May 31, 2019 at 8:07
  • $\begingroup$ Have you tried to run it on my simulator; see initial configuration here: ibb.co/x6sYHmv (on my simulator it never halts) $\endgroup$
    – Vor
    Commented May 31, 2019 at 9:04
  • $\begingroup$ yes sorry I wasn't clear: my result now matches your simulator. $\endgroup$ Commented May 31, 2019 at 9:09
  • $\begingroup$ So now the trace doesn't halt, right? I don't remember the exact meaning of the symbols, but it seems that the $1c1c1c$ si "moving " rightward (as it should) $\endgroup$
    – Vor
    Commented May 31, 2019 at 9:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.