brainfuck - Brainfuck 修改版本的图灵完备性

Question

如果单元格是位，并且 + 和 - 操作只是稍微翻转一下，Brainfuck Turing 是否完整？是否有一个简单的证据证明类似 Brainfuck 的语言无论单元大小如何都是图灵完备的，还是我需要考虑一个模拟图灵机的程序？如果没有，我怎么知道？

编辑：我找到了问题的答案：Brainfuck with bit cells 被称为Boolfuck。普通的 Brainfuck 可以简化为它，所以 Boolfuck 是图灵完备的。

Answer 1

这个答案应该很适合你；它对使语言图灵完备的特性有一个非常具体的定义。

这是它的要点：

一般来说，要使命令式语言成为图灵完备的，它需要：

1. 有条件重复或有条件跳转的一种形式（例如while, if+ goto）

2. 一种读取和写入某种形式的存储（例如，变量、磁带）的方法

Answer 2

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

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