BrainIf Turing-completeness proof
Jump to navigation
Jump to search
It can be shown that BrainIf is Turing-complete by translating Cyclic tag system into the language. This construction is itself based on brainfuck minus - proof due to inability to decrement the cell. Only programs that don't halt can be translated, although it's possible to edit the translation for supporting them
Definitions
Because of it's length a couple of definitions are used:
n- first command in each translated section- Moving right:
move right = if 1 goto n+4 if 0 move right if 0 goto n+7 if 1 goto n+7 if 1 move right if 0 goto n+7 if 0 goto n+7
- Moving left:
move left = if 1 goto n+4 if 0 move left if 0 goto n+7 if 1 goto n+7 if 1 move left if 0 goto n+7 if 0 goto n+7
Initialisation
Program starts with this commands:
if 0 move right if 0 move right if 0 move right
Then Cyclic Tag data is initialised:
- 0 becomes:
if 0 increment if 1 move right if 0 move right if 0 move right
- 1 becomes:
if 0 increment if 1 move right if 0 move right if 0 increment if 1 move right
After that there are two ways of moving pointer to the start of data queue:
- One works with queues of all lengths:
move left if 0 move left if 0 goto n+6 if 1 move left if 0 goto n if 1 goto n if 0 move right if 0 move right if 0 move right
- Second one is to move manually (
xhere refers to a queue bit, starting from the end):
if x move left if 0 move left if 1 move left
Repeated times the length of a queue, with last copy having the last command removed.
Translation of CT program
- 0 becomes:
if 1 move right if 0 goto n+6 if 1 move right move right move right if 1 goto n+2 if 0 move right if 0 goto n+17 if 1 move right if 0 goto n+14 if 1 move right move right move right if 1 goto n+10 if 0 increment if 0 move right if 0 move right if 0 move left if 0 move left if 1 move left move left move left if 1 goto n+19 if 0 move right if 0 move right if 0 move right
- 1 becomes:
if 1 move right if 0 goto n+6 if 1 move right move right move right if 1 goto n+2 if 0 move right if 0 goto n+18 if 1 move right if 0 goto n+14 if 1 move right move right move right if 1 goto n+10 if 0 increment if 0 move right if 0 move right if 0 increment move left if 0 move left if 1 move left move left move left if 1 goto n+20 if 0 move right if 0 move right if 0 move right
- Production ends with this:
if 1 move right if 0 goto n+6 if 1 move right move right move right if 1 goto n+2 if 0 increment if 1 move left if 1 move left move left move left if 1 goto n+8 if 0 move right if 0 move right if 0 move right
At the end of a program this line is put:
if 1 goto s
Where s is the start of Cyclic Tag program