图灵完整性修改版Brainfuck

Question

是Brainfuck图灵完备如果细胞位,+和-操作简单地拨动了一下？是否有一个简单的证据表明,无论细胞大小如何,类似Brainfuck的语言都是图灵完整的,或者我是否需要考虑一个模拟图灵机的程序？我怎么知道是否没有？

编辑:我找到了一个问题的答案:带有位单元的Brainfuck被称为Boolfuck.普通的Brainfuck可以减少到它,所以Boolfuck是Turing-complete.

Answer 1

图灵完备语言可以“模拟任何单磁带图灵机”。Brainfuck 和 Boolfuck 都是图灵完备的，因为它们遵循规范。

另请注意，如果一个是图灵完备的，则另一个一定是图灵完备的，因为它们几乎相同。在 Brainfuck 中，您以字节为单位移动，但在 boolfuck 中，您使用的是构成字节的位。