Sceql Turing-completeness proof

This is a proof that Sceql is a Turing-complete language. This is done by preparing a small Turing-complete language sceqlfuck and presenting a translation table for translating sceqlfuck into Sceql.

sceqlfuck

The language is a mixture between brainfuck and Sceql. It has two stacks, which is enough for a Turing-complete language. Adding more stacks would be possible and even easy, but as said, more isn't needed. It's easy to emulate array with two stacks, and that way for example normal brainfuck wouldn't be difficult to translate into sceqlfuck and then to Sceql. Initially both stacks are empty, and the first one chosen, although it doesn't matter which one is initially chosen. The language has the following instructions:

+   increase current cell
-   decrease current cell
*   push a new zero value into chosen stack
!   pop chosen stack
=   change stack
[   loop start (begins if current cell non-zero)
]   loop end (ends if current cell zero)
,   push input into chosen stack (zero on EOF)
.   output value on top of chosen stack

sceqlfuck to Sceql

First add

!!!!!!!!!_==_===_==_=

in to the beginning of the Sceql program! Then translate the sceqlfuck program to Sceql with the following:

+   _
-   -
*   =\==/=\=/=\==/=\=/=!!\==/=\=/=\==/=\=/=_=
!   =\==/=\=/=\==/=\=/_==\-/==
=   =\==/=\=/==
[   \
]   /
,   &!=\==/=\=/=\==/=\=/===_\==/=\=/=\==/=\=/==
.   *\==/=\=/=\==/=\=/==

Meta

The Sceql programs created with these translations have the following memory structure (in this presentation the amount of trash cells and value cells is more than one just for clarity):

0tttt01a1a0tttt01a1a

'0' presents a zero, 't' presents trash (trash cells have value 1), "1a" marks a cell, with '1' indicating there is a cell and 'a' representing its value. Both stacks have a trash line because in Sceql anything put into queue can't be removed from it, only its value altered. Thus, when sceqlfuck instruction '!' is used to pop a stack, the value goes to trash line. As mentioned before, both stacks are initially empty, even if the intialization code creates a zero cell for both arrays -- but this isn't count, it's just there to avoid (possible) problems with zero-length stacks. In the beginning of every instruction the memory state is so that the top-most value of a chosen stack is selected. This allows short code for +, -, [, and ] instructions.

An example

Here is a sceqlfuck program that prints out sequence "10110111011110111110...", never terminating.

**+
[
  =*=
  [
    +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++ .
    =*+=
    !
  ]
  +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++ .
  !
  =*+
]

Translated into Sceql it becomes

!!!!!!!!!_==_===_==_==\==/=\=/=\==/=\=/=!!\==/=\=/=\==/=\=/=_==\==/=\=/=\==/=\=/
=!!\==/=\=/=\==/=\=/=_=_\=\==/=\=/===\==/=\=/=\==/=\=/=!!\==/=\=/=\==/=\=/=_==\=
=/=\=/==\________________________________________________*\==/=\=/=\==/=\=/===\=
=/=\=/===\==/=\=/=\==/=\=/=!!\==/=\=/=\==/=\=/=_=_=\==/=\=/===\==/=\=/=\==/=\=/_
==\-/==/________________________________________________*\==/=\=/=\==/=\=/===\==
/=\=/=\==/=\=/_==\-/===\==/=\=/===\==/=\=/=\==/=\=/=!!\==/=\=/=\==/=\=/=_=_/

and can (obviously) be run in a Sceql interpreter.