Тьюринг-полнота модифицированной версии Brainfuck

Question

Является ли Brainfuck Turing-завершенным, если ячейки являются битами, а операции + и - просто слегка меняются? Есть ли простое доказательство того, что языки, подобные Brainfuck, полны по Тьюрингу независимо от размера ячейки, или мне нужно подумать о программе, которая имитирует машину Тьюринга? Как я узнаю, что его нет?

РЕДАКТИРОВАТЬ: Я нашел ответ на мой вопрос: Brainfuck с битовыми клетками называется Boolfuck. Обычный Brainfuck может быть уменьшен до этого, так что Boolfuck завершен по Тьюрингу.

Answer 1

This answer should suit you well; it has a very specific definition of what features make a language turing complete.

Вот суть этого:

В общем, для того, чтобы императивный язык был полным по Тьюрингу, ему необходимо:

1. A form of conditional repetition or conditional jump (eg, while, if+goto)

2. Способ чтения и записи некоторой формы хранения (например, переменные, лента)

Answer 2

Полный язык Тьюринга может "имитировать любую лентопротяжную машину Тьюринга". Brainfuck и Boolfuck оба завершены по Тьюрингу, потому что они следуют спецификациям.

Также обратите внимание, что если один завершен по Тьюрингу, другой должен быть, потому что они почти одинаковы. С помощью brainfuck вы перемещаетесь в байтах, но в boolfuck вы используете биты, которые составляют байты.