Talk:Spain without the S

TC proof sketch

I belive the language is Turing-complete, and I have unfinished proof for it, for simplicity I used brainfuck-like syntax for the language in my proof

Command	Description
Spain without the S	[
Spain without the p	-
Spain without the a	>
Spain without the i	]
Spain without the n	*
Spain without the Spain	.
Spain without the pain	,

For proving Turing-completeness we will compile a version of Cyclic Tag in which data string is always non-zero into the language. The structure of memory will be similar to brainfuck minus - and look as follows

127 0 127 0 0 0 x y z x y z x y z ... 0

Where memory is represented as

x y z 

Where x means cell exists, y is the value of cell, and z that cell was removed. Becsue of the way the commands work last bit that was removed would still be 0, while the ones that were before it would be marked We will also use - once for each cell, to not make code very long by writing more than 100 of them for incrementing the cell. Another difficulty is that it has do-while loops, so code should also be adapted for it.

Initialisation

We start our code with this code:

*>-*>*>-*>*>*>

Adding this to memory:

127 0 127 0 0 0

Then we initialise the data, 0 becomes:

*>-*>*>

Adding this to menory:

127 0 0

1 becomes:

*>-*>-*>

Adding this to memory:

127 127 0

Then it follows with this code to finish initialisation:

*>>

Which adds another 0 to the end of data and wraps around to the first cell, finishing initialisation.

Translating the program into it

Program would be inside an infinite loop so it starts like that:

[

Simplest instruction to translate would be deleting front bit of the data, which look like this:

>>[>>>]->[>>>]>

Basic idea is that it would first move to the third cell and start a loop, moving pointer three times forward, and when it stops it means that it skipped all of the deleted bits and is now at the end of the last removed bit we set it to 127, making so that the bit after it be the removed bit, then we move to the next cell and then search for the end of data, after that move to the first cell and the program continues, checking whether the first data bit is zero or not is the most difficult part of it. I am not sure how I would do that, but I think it is possible