Brainfuck with while 0 loops
Jump to navigation
Jump to search
This page is proof that brainfuck with unbounded tape and while 0 loops is Turing complete, which is proven by simulation of Cyclic Tag.
Initialise data
put +>>
at the start of a program then initialise program with 0
being >+>
and 1
being >>
. After initialising data append >+<<[<<]>>[
Simulating Cyclic Tag
Replace every ;
with +>>
, 0
with +>[[>>]->+>+<<[<<]->+]<[+>-<]-
and 1
with +>[[>>]->>+<<[<<]->+]<[+>-<]-
. End program with ]
. It also proves that it is Turing-complete with nesting depth of 3
Explanation
To simulate Cyclic Tag in this version of brainfuck we will use following layout:
10 xy xy xy ... 1
x
is 1 if bit is deleted and 0 otherwise. y
is 1 if bit is 0 and 0 if bit is 1.