Brainfuck与1位存储单元？

Question

编程语言Brainfuck的实现,如果其存储单元的容量为1位,而不是通常的8位,仍然可以完成吗？

+和 - 指令变得相同,但这不一定是个问题.

我认为没有问题,例如4位存储器单元,但如果它一直扩展到单个位值,我就无法解决.

Answer 1

是的,结果语言仍然是图灵完成的.实际上,存在几种这样的语言.其中一个是Boolfuck.它完全符合你的建议:让每个单元格成为一个单位并摆脱-它,因为它是多余的.它还使用;,而不是.用于输出.官方网站包含从Brainfuck到Boolfuck的减少,这证明了Boolfuck的图灵完整性.我在此重申减少以使答案自成一体:

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

其他基于比特的Brainfuck衍生产品包括Smallfuck和BitChanger.本文也可能是您感兴趣的,它通过删除冗余(包括使用位而不是字节)来完成最小化Brainfuck语言的几个步骤.