binary - 用 1 位记忆细胞来搞脑筋？

Question

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

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

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

Answer 1

是的，生成的语言仍然是图灵完备的。事实上，存在几种这样的语言。其中之一是Boolfuck。它完全按照您的建议进行：让每个单元格都是一个位并摆脱-，因为它是多余的。它也用于;输出.。官方网站包含从 Brainfuck 到 Boolfuck 的简化，这证明了 Boolfuck 的图灵完备性。我在这里重申减少以使答案自成一体：

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

其他基于位的 Brainfuck 衍生工具包括Smallfuck和BitChanger。您可能也对这篇文章感兴趣，它通过消除冗余（包括使用位而不是字节）来最小化 Brainfuck 语言的几个步骤。