Будет ли реализация языка программирования Brainfuck, по-прежнему будет завершена, если его ячейки памяти будут иметь 1 бит вместимость вместо обычных 8 бит?Brainfuck с ячейками памяти 1 бит?
Инструкции + и - становятся идентичными, однако это не должно быть проблемой.
Я не вижу проблем с, например, 4-битными ячейками памяти, но я не могу сработать, если это масштабируется до одноразрядных значений.
Да, результирующий язык по-прежнему будет Тьюрингом. На самом деле существует несколько таких языков. Один из них - Boolfuck. Он делает именно то, что вы предлагаете: каждая ячейка должна быть одним битом и избавляться от -, потому что она избыточна. Он также использует ; вместо . для вывода. The official website содержит сокращение от Brainfuck до Boolfuck, что доказывает завершенность Boolfuck's Turing. Я вновь сокращение здесь, чтобы сделать ответ самодостаточным:
Brain. Bool.
+ >[>]+<[+<]>>>>>>>>>[+]<<<<<<<<<
- >>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>[+]<<<<<<<<<
< <<<<<<<<<
> >>>>>>>>>
, >,>,>,>,>,>,>,>,<<<<<<<<
. >;>;>;>;>;>;>;>;<<<<<<<<
[ >>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>[+<<<<<<<<[>]+<[+<]
] >>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>]<[+<]
Других битовой основой Brainfuck производные включают Smallfuck и BitChanger. This article также может представлять для вас интерес, который проходит несколько шагов по минимизации языка Brainfuck путем удаления избыточности (включая использование битов вместо байтов).