B^2 Turing Completeness

From Esolang
Jump to navigation Jump to search

This page will convert brainfuck, a known Turing complete language, into B2. B2 is not turing complete but is a bounded-storage machine (see "Counter Argument" for details).

Required For Turing-Completeness

Brainfuck B2 Equivalent
x = add x 1 ;
x = sub x 1 ;
while ( x == 0 ) {
< No exact match.
> No exact match.

Not Required

Brainfuck B2 Equivalent
output x ;
number x = input ;
decimal x = input ;


If one argues that < and > could also be represented using variables, B2 is still not turing complete. These variables are all of limited size, and only a limited amount of them are accessible. Even a program like this:

number cell = firstCell ;
if ( currentCell == 1 ) {
cell = secondCell ;
if ( currentCell == 2 ) {
cell = thirdCell ;

for however many variables/cells are used, that's still a limited amount of variables — and although that would be Turing-complete if variables were unbounded, they're not, and since a finite amount of variables times a finite size for each of those variables equals a finite amount of storage, while a Turing machine needs an infinite (or unbounded) amount of storage, B2 isn't Turing complete. Since bounded storage machines have finite storage, but are the same as Turing machines in all other respects (just like B2), B2 is not Turing-complete but is a bounded-storage machine.