如果编程语言Brainfuck的存储单元容量为1bit，而不是通常的8bit，那么它的实现是否仍然是图灵完整的？
+ 和 - 指令变得相同，但这不一定是问题。
例如，我认为 4 位存储单元没有问题，但我无法确定这是否一直扩展到一位值。
是的，生成的语言仍然是图灵完备的。事实上，有几种这样的语言存在。其中之一是Boolfuck。它完全按照您的建议执行：让每个单元格都是一个位并摆脱-，因为它是多余的。它还使用;而不是.输出。官方网站包含从Brainfuck到Boolfuck的简化，这证明了Boolfuck的图灵完备性。我在这里重申减少以使答案自成一体：
Brain. Bool.
+ >[>]+<[+<]>>>>>>>>>[+]<<<<<<<<<
- >>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>[+]<<<<<<<<<
< <<<<<<<<<
> >>>>>>>>>
, >,>,>,>,>,>,>,>,<<<<<<<<
. >;>;>;>;>;>;>;>;<<<<<<<<
[ >>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>[+<<<<<<<<[>]+<[+<]
] >>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>]<[+<]
其他基于位的Brainfuck衍生产品包括Smallfuck和BitChanger。本文也可能引起您的兴趣，它通过删除冗余(包括使用位而不是字节(来最小化 Brainfuck 语言的几个步骤。