patternMinor
How does Rogozhin's (2, 18) universal turing machine work?
Viewed 0 times
universalrogozhinworkdoeshowturingmachine
Problem
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:
For example, using an initial input of
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:
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:
At this stage, Rogozhin claims the tape should be:
P2P1P'0R'At
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!?
I would expect something like:
through a simple 2-tag encoding that I believe should loop forever:
a -> aaFor example, using an initial input of
aaa:aaa
aaa
aaa
.... etcApologies 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 |AtRunning 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 cAt this stage, Rogozhin claims the tape should be:
P2P1P'0R'At
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!! |AtI would expect something like:
Solution
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}}$
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.
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.
Code Snippets
c⃖₁ c⃖₁ b b 1 1 b 1 b b >1 c 1 c 1 c
^ ^
!!! !!!Context
StackExchange Computer Science Q#110031, answer score: 3
Revisions (0)
No revisions yet.