binary - Brainfuck 与 1 位存储单元？

Question

如果其存储单元的容量为 1 位，而不是通常的 8 位，那么编程语言 Brainfuck 的实现是否仍然是图灵完整的？

+ 和 - 指令变得相同，但这不一定是问题。

例如，我认为 4 位存储单元没有问题，但是我无法确定这是否一直扩展到单个位值。

Answer 1

是的，由此产生的语言仍然是图灵完备的。事实上，存在几种这样的语言。其中之一是Boolfuck .它完全按照您的建议执行:将每个单元格设为一位并摆脱 - ，因为它是多余的。它还使用 ;相反 .为输出。 The official website包含从 Brainfuck 到 Boolfuck 的简化，这证明了 Boolfuck 的图灵完备性。我在这里重申减少以使答案独立:

Brain.  Bool.
+       >[>]+<[+<]>>>>>>>>>[+]<<<<<<<<<
-       >>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>[+]<<<<<<<<<
<       <<<<<<<<<
>       >>>>>>>>>
,       >,>,>,>,>,>,>,>,<<<<<<<<
.       >;>;>;>;>;>;>;>;<<<<<<<<
[       >>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>[+<<<<<<<<[>]+<[+<]
]       >>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>]<[+<]

其他基于位的 Brainfuck 衍生物包括 Smallfuck和 BitChanger . This article您可能也会感兴趣，它通过删除冗余(包括使用位而不是字节)来最小化 Brainfuck 语言的几个步骤。