# 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.