Is brainfuck still Turing complete if opening brackets do nothing

169 Views Asked by At

I am working on a physical breadboard 8bit CPU that directly interpret brainfuck.

The language specification indicates that both opening and closing brackets have logic :

[ => Jump to matching ] If Zero

] => Jump to matching [ Unless Zero

But with the way I made my CPU I can't implement the first rule, finding the matching closing bracket will be hard.

What would be the consequences of changing the opening bracket logic to doing nothing and only keep the closing bracket logic ? Does it affect the Turing completeness of the language ?

I know it won't really be Brainfuck anymore and existing programs may no longer work properly, for example :

[+.]

classic brainfuck: won't do anything

my modified brainfuck: will print every character from 0 to 255 (or an overflow error if cells don't loop back to 0)

2

There are 2 best solutions below

0
typhon On

In that case, it would not be Turing complete, as it lacks conditionals. The best you would be able to do would be changing numbers by constants, or changing user input by constants (e.g. a -> c, b -> d).

To make your CPU Turing complete, you could try another esoteric programming language, one that interprets parameters for a particular instruction as opposed to symbols.

0
Daniel Cristofani On

In discussion here, Int-e showed this "do-while brainfuck" variant to be Turing-Complete by reduction from a slightly limited form of regular brainfuck (must get all input at the beginning). If you want, I can translate my universal Turing machine program to this variant.