a -> aa
For example, using an initial input of
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:
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!