1bitのメモリセルを使って脳死？

Question

プログラミング言語Brainfuckの実装は、メモリセルが通常の8ビットではなく1ビットの容量であれば、まだ完成していますか？

+と - の命令は同じになりますが、これは問題である必要はありません。

たとえば、4ビットのメモリセルでは問題はありませんが、これが単一ビット値にまで拡張されていればうまくいかないことがあります。

Answer 1

はい、結果として得られる言語はまだチューリング完了です。実際、そのような言語がいくつか存在します。そのうちの1つはBoolfuckです。それはまさにあなたが示唆していることです：それぞれのセルを1ビットにして、冗長であるので-を取り除きます。出力には.の代わりに;が使用されます。 The official websiteにはBrainfuckからBoolfuckへの還元が含まれており、BoolfuckのTuring-completeを証明しています。私は答えは自己完結型にするためにここに削減を繰り返し強調しています：

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

他のビットベースのBrainfuck誘導体はSmallfuckとBitChangerが含まれます。 This articleは、冗長性を取り除いてBrainfuck言語を最小限にするいくつかのステップ（バイトの代わりにビットを使うことを含む）にも関心があります。