Rotary/Proof of Turing completeness
The following proof will assume that circles are always 34 characters. From the specification, the X in this diagram is the start of a circle, the next instruction would be the 2, and execution halts if the X is reached again (but it is not executed the second time).
!!!X2!
!!! !!!
! !
! !
! !
! !
! !
!!! !!!
!!!!!!
Since the circle pointer wraps, we can construct a full program loop by having v as the final instruction of a circle, for all circles. Since we have access to a stack with a full rotate command, tag seems obvious. The top of stack is to be the front of the queue. To add something to the back of the word, push it to the stack using some number of $ then issue a corresponding number of rotations @. To remove from the start, simply pop ~. With this, Bitwise Cyclic Tag can be implemented, with 1 or 2 circles per instruction, although more efficient encodings are certainly possible. On the stack, a 0 is encoded as 1, with 1 being 2. This allows for the empty word to be detected since pops from an empty stack result in 0.
0 command
The zero instruction unconditionally removes a bit from the word. It is also the only way for the word to become empty.
It pops from the word. It then pops again, if it was not 0 it pushes it back onto the stack and ensures the tape returns to an all zeroes state. If it was 0, it means the stack was empty and the circle is allowed to be exhausted and the program halts.
Notably, the first of these two circles is the only one in the entire system which is able to reach the end. Due to the fact that after a pop from an empty stack, any further pops will still return zero, even if circles had looping behavior this would still behave properly. The only difference would be that it would infinitely loop rather than explicitly halt.
Unwrapped (reaching X halts)
pop, pop, if nonzero go to next circle, otherwise halt ~~*v!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!X push, dec, if nonzero dec, next $-*-v!!!!!!!!!!!!!!!!!!!!!!!!!!!!!X
Wrapped
!!!~~*
!!! v!!
! !
! !
! !
! !
! !
!!! !!!
!!!!!!
!!!$-*
!!! -v!
! !
! !
! !
! !
! !
!!! !!!
!!!!!!
10 command
The conditional append instructions pop and push, then check this peeked value before issuing a push.
Unwrapped
pop, push, decrement, if nonzero push, if nonzero rotate, if nonzero dec, next ~$-*$*@*-v!!!!!!!!!!!!!!!!!!!!!!!!X
Pseudocode
x = pop() push(x) x-- if (x) # the popped value was 2 (encoded) = 1 (value) push(x) # remember, a stored 0 value is encoded as 1 on the stack rotate() x-- # ensures x (tape cell) is always 0 at the end
Wrapped
!!!~$-
!!! *$*
! @
! *
! -
! v
! !
!!! !!!
!!!!!!
11 command
Unwrapped
pop, push, decrement, if nonzero inc, if nonzero push, if nonzero rotate, if nonzero dec, if nonzero dec, next ~$-*+*$*@*-*-v!!!!!!!!!!!!!!!!!!!!X
Pseudocode
x = pop() push(x) x-- if (x) x++ push(x) rotate() x-- x--
!!!~$-
!!! *+*
! $
! *
! @
! *
! -
!!! v-*
!!!!!!
Starting word from input
To input a starting word, a few starting circles can be used.
This basic pair loops, appending symbols to the word until a 0 is encountered
,*$*@v!!!!!!!!!!!!!!!!!!!!!!!!!!!!X x = input() if (x) push(x) rotate() next ?v^!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!X if (x == 0) next else prev
All that needs to be done is ensure that this pair only executes once. This satisfies such a requirement, but only if the first cell starts nonzero
?v,*$*@v!!!!!!!!!!!!!!!!!!!!!!!!!!X ?v^!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!X
Assume we have circles which invert the cell under the pointer, then programs could be structured like
cell invert circles ?v,*$*@v!!!!!!!!!!!!!!!!!!!!!!!!!!X ?v^!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!X # the tape is now all zeroes no matter what actual code circles # the tape remains all zeroes due to the behavior of the rules +v!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!X
This would only ever execute the input code once, at the start, since once the loop is exited the final + circle ensures that the inversion will result in a 0 under the cell, skipping the loop. Since the code does not ever alter the tape from all zeroes for more than 2 circles, the inversion code can use arbitrarily many cells to work. It will only ever be given the tape state of all zeroes, or a 1 followed by all zeroes. Therefore, inversion can be done like so:
?v->/+v!!!!!!!!!!!!!!!!!!!!!!!!!!!X *v+>/+v!!!!!!!!!!!!!!!!!!!!!!!!!!!X -<\v!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!X
The first circle checks if the current cell is zero and skips. Otherwise, it makes it zero and makes the cell after it 1. The second circle checks if the current cell is one and skips. Otherwise, it makes it one and makes the cell after it 1. The final circle makes the second cell 0, and returns to the first cell.
Consider the two cases:
The tape is all zero.
- In this case the first cell is zero, meaning the first circle gets skipped.
- Since the first cell is still zero, the second circle doesn't skip. So the cell is now set to one, and the second cell also gets set to one.
- Finally the third circle sets the second cell to zero and returns to the first cell.
The tape is 1 followed by all zeroes.
- In this case the first cell is one, so the first cell is not skipped. The first cell gets set to zero, and the second cell gets set to 1.
- Since the pointer is on the second cell and it is one, the second circle gets skipped.
- Finally the third circle sets the second cell to zero and returns to the first cell.
This code successfully inverts the first cell of the tape.
The overall unwrapped program structure is therefore:
?v->/+v!!!!!!!!!!!!!!!!!!!!!!!!!!!X *v+>/+v!!!!!!!!!!!!!!!!!!!!!!!!!!!X -<\v!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!X ?v,*$*@v!!!!!!!!!!!!!!!!!!!!!!!!!!X ?v^!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!X code circles according to the above command sections +v!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!X
And wrapped:
!!!?v-
!!! >/+
! v
! !
! !
! !
! !
!!! !!!
!!!!!!
!!!*v+
!!! >/+
! v
! !
! !
! !
! !
!!! !!!
!!!!!!
!!!-<\
!!! v!!
! !
! !
! !
! !
! !
!!! !!!
!!!!!!
!!!?v,
!!! *$*
! @
! v
! !
! !
! !
!!! !!!
!!!!!!
!!!?v^
!!! !!!
! !
! !
! !
! !
! !
!!! !!!
!!!!!!
code circles here
!!!+v!
!!! !!!
! !
! !
! !
! !
! !
!!! !!!
!!!!!!
Initial word of 1
BCT is Turing complete even if the word starts as just 1, since an initial word can be encoded into the program. We can ensure that the word starts as just 1 without altering the word after first startup like so:
*v+$v!!!!!!!!!!!!!!!!!!!!!!!!!!!!!X # skip if the tape was set, otherwise push a 1 and keep it on the tape to be cleared later -v!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!X # clears the tape actual code here +v!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!X # sets the tape
!!!*v+
!!! $v!
! !
! !
! !
! !
! !
!!! !!!
!!!!!!
!!!-v!
!!! !!!
! !
! !
! !
! !
! !
!!! !!!
!!!!!!
code here
!!!+v!
!!! !!!
! !
! !
! !
! !
! !
!!! !!!
!!!!!!