Brainfuck с 1-битными ячейками памяти?

Question

Будет ли реализация языка программирования Brainfuck по-прежнему завершена, если его ячейки памяти будут иметь емкость 1 бит вместо обычных 8 бит?

Инструкции + и - становятся идентичными, однако это не должно быть проблемой.

Я не вижу проблем с, например, 4-битными ячейками памяти, но я не могу решить, если это масштабируется до однобитовых значений.

Answer 1

Да, итоговый язык все равно будет завершен по Тьюрингу. На самом деле существует несколько таких языков. Одним из них является Boolfuck. Это именно то, что вы предлагаете: каждая клетка должна быть единственной и избавиться от -потому что это избыточно. Он также использует ; вместо . для вывода. Официальный сайт содержит сокращение от Brainfuck до Boolfuck, что доказывает полноту по Тьюрингу. Я повторяю сокращение здесь, чтобы сделать ответ автономным:

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

Другие основанные на битах производные Brainfuck включают Smallfuck и BitChanger. Эта статья также может быть интересна для вас, которая состоит из нескольких этапов минимизации языка Brainfuck путем удаления избыточности (включая использование битов вместо байтов).