Variations on Cyclic Tag

[r.e.s.]

I've been playing with simple variations of cyclic tag systems,
and am wondering if anyone has ideas for proof/disproof of Turing
completeness of the following primitive programming language ...

Any string of bits L...R, when read in cyclic sequence (rightward
from L, with L next after R), parses into a unique sequence of
instructions from the set {0, 10, 11}. Thus, any such string can
be interpreted as a self-modifying program whose instructions are
executed in cyclic sequence as follows (with labels L/R revised
appropriately when a bit is deleted/appended):

Instruction Execution
----------- ---------------------
0 delete L
1x if L>0: append x to R

Program execution halts if and when the program deletes itself.

(This is essentially the Turing tarpit "BCT", but with the data-
string identified with the program-string itself. For BCT, see
http://r.s.home.mindspring.com/tag/ )

Example (^ or ^^ indicating the current instruction as 0 or 1x):

Step Program-string
----- ----------------------
00001 1011110111
^^
00002 10111101110
^^
00003 101111011101
^^
00004 1011110111011
^
00005 011110111011
^^
00006 011110111011
^^
00007 011110111011
^^
00008 011110111011
^
00009 11110111011
^^
00010 111101110111
^^
00011 1111011101111
^
00012 111011101111
^^
00013 1110111011111
^^
00014 11101110111110
^^
00015 111011101111101
^^
00016 1110111011111011
^^
00017 11101110111110110
^^
00018 111011101111101101
^
00019 11011101111101101
^ ^
00020 110111011111011011
^^
... ...
43074 (empty)

I suspect that this language too is a Turing tarpit, and that
in the 43,074 we're already seeing some characteristicly rapid
growth in the associated noncomputable Rado S-sequence.

--r.e.s.

[r.e.s.]

"r.e.s." <r...@ZZmindspring.com> wrote ...

> Step Program-string
> ----- ----------------------
> 00001 1011110111

[...]
> 43074 (empty)

Oops, I misnumbered all the steps except the last one --
the initial program should be listed at step *0*, etc.,
and the program finally deletes itself at step 43074.