用 1 位存储单元进行 Brainfuck？

Question

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

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

我看不出任何问题，例如 4 位存储单元，但我无法计算出它是否一直扩展到单个位值。

Answer 1

是的，生成的语言仍然是 Turing-complete。事实上，存在几种这样的语言。其中之一是 Boolfuck. It does exactly what you suggest: have each cell be a single bit and get rid of -, because it's redundant. It also uses ; instead . for output. The official website 包含从 Brainfuck 到 Boolfuck 的减少，这证明了 Boolfuck 的 Turing-completeness。我在这里重申减少以做出答案 self-contained:

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

Other bit-based Brainfuck-derivatives include Smallfuck and BitChanger. This article 您可能也感兴趣，它通过几个步骤通过删除冗余来最小化 Brainfuck 语言（包括使用位而不是字节).

用 1 位存储单元进行 Brainfuck？

Brainfuck with 1bit memory cells?

binary

brainfuck

turing-complete

esoteric-languages