B^2 Turing Completeness
This page will convert brainfuck, a known Turing complete language, into B^{2}. B^{2} is not turing complete but is a bounded-storage machine (see "Counter Argument" for details).
Required For Turing-Completeness
Brainfuck | B^{2} Equivalent |
---|---|
+ |
x = add x 1 ; |
- |
x = sub x 1 ; |
[ |
while ( x == 0 ) { |
] |
} |
< |
No exact match. |
> |
No exact match. |
Not Required
Brainfuck | B^{2} Equivalent |
---|---|
. |
output x ; |
, |
number x = input ;or decimal x = input ; |
Counter-argument
If one argues that <
and >
could also be represented using variables, B^{2} 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, B^{2} isn't Turing complete. Since bounded storage machines have finite storage, but are the same as Turing machines in all other respects (just like B^{2}), B^{2} is not Turing-complete but is a bounded-storage machine.