@!+-() Turing-completeness Proof

@!+-() is Turing complete because it can simulate brainfuck but we need to compile it to intermediate language called "queuefuck"

Queuefuck

Queuefuck has following commands:

. - enqueue zero
+ - dequeue, increment, enqueue again
- - dequeue, decrement, enqueue again
^ - dequeue and enqueue again
" - dequeue and enqueue 2 times
[ - dequeue and if zero go past matching ]
] - go back to matching [
; - dequeue and output
: - enqueue user input
/ - dequeue

Compiling n-cell brainfuck to queuefuck

Note than x(n) means that command x is repeated n times.

initalisation - .(n)
+ - +^(n-1)
- - -^(n-1)
> - ^
< - ^(n-1)
[ - "^(n-1)[
] - "^(n-1)]
. - "^(n-1);
, - /:^(n-1)

Compiling queueuefuck to @!+-()

. - (-)@
+ - !+@
- - !-@
^ - !@
[ - !(
] - !)
; - !,
: - .@
/ - !
" - !@@