Brainfuck - полный язык программирования Тьюринга, который использует только 8 символов (6, если вы игнорируете ввод / вывод).

Две наиболее заметные из них , которые толкают его на Тьюринга полнота [и ], по существу , этикетки и Гото Brainfuck в.

Обычно программы в Brainfuck используют несколько наборов [], но мне было интересно, сколько именно пар этих скобок нужно использовать, чтобы завершить Brainfuck Turing?

Проще говоря, какое наименьшее количество скобок необходимо для моделирования машины Тьюринга с n состояниями (укажите количество скобок для машин Тьюринга с 1, 2 и тремя состояниями)?

Примечания:

Мы предполагаем бесконечную ленту и без вычислительных ограничений.

Это машина Тьюринга с двумя символами

Это дальнейшее развитие ответа @ ais523 , сокращение его до двух наборов скобок, а также использование более компактного размещения ячеек на основе теории линейки Голомба. ais523 создал компилятор для этой конструкции , а также для этого сеанса TIO, показывающего пример результирующей BF-программы, работающей с трассировкой отладки счетчиков TWM.

Как и в оригинале, это начинается с программы в The Waterfall Model , с некоторыми ограничениями, которые не теряют общности:

1. Все счетчики имеют одинаковое значение самовозврата ; то есть отображение триггера TWM имеет свойство для всех .$R$$f$$f(x,x)=R$$x$
2. Существует один счетчик остановки .$h$
3. Число счетчиков равно ( p - 1 ) / 2 для некоторого простого числа p .$c$$(p-1)/2$$p$

Правитель Голомба

Мы объединяем конструкцию Эрдеша – Турана с функцией перестановки массива Уэлча – Костаса , чтобы получить линейку Голомба с необходимыми свойствами.

(Я уверен, что эта комбинированная конструкция не может быть новой идеей, но мы только что нашли и соединили эти две части из Википедии.)

Пусть $r$ примитивный корень из $p=2c+1$ . Определить функцию

1. $g$ - линейка Голомба порядка . То есть разность уникальна для каждой пары различных чисел .2 c g ( i ) - g ( j ) i , j ∈ { 0 , … , 2 c - 1 }$2c$$g(i)-g(j)$$i,j \in \{0,\ldots,2c-1\}$
2. $g(k)\bmod(2c)$0 , … , 2 c - 1 принимает каждое значение ровно один раз.$0,\ldots,2c-1$

Структура ленты

Для каждого счетчика TWM мы назначаем две позиции ячейки ленты BF, запасную ячейку и ячейку значения :$x\in \{0,\ldots,c-1\}$u ( x ) v ( x ) $u(x)$ $v(x)$

Вторым свойством является ровно два разных значения на выбор.$g$$k_1,k_2$

Содержимое резервной ячейки большую часть времени будет поддерживаться на уровне , за исключением случаев, когда ее счетчик только что был посещен, когда он будет на уровне , вдвое превышая значение самосброса счетчика. Ячейка значения будет сохраняться в два раза больше значения соответствующего счетчика TWM.$0$$2R$

Все остальные ячейки, которые могут быть достигнуты при выполнении программы BF (конечное число), будут храниться с нечетными значениями, так что они всегда тестируются как ненулевые. После инициализации это происходит автоматически, потому что все настройки ячейки делятся на четные суммы.

При желании все положения ячеек могут быть смещены вправо на постоянную величину, чтобы избежать смещения влево от исходного положения ленты BF.

Структура программы BF

Пусть будет расстоянием между значением счетчика остановки и резервными ячейками, и пусть будет достаточно большим числом, чтобы для всех счетчиков . Тогда основная структура программы BF$H = v(h)-u(h)$$N$$cN+1 \geq v((x+1)\bmod c) - u(x)$$x$

инициализация корректировки[ >$\times (H+cN+1)$ [ <$\times c$ × H] <$\times H$ ]

инициализация

Инициализации фазы устанавливает все клетки достижимы программой их начальные значения, в состоянии , как будто только что посетил последний счетчик и только что активная ячейка была ее резервной ячейки :$u(c-1)$

1. Ячейки значений инициализируются для удвоения начального содержимого соответствующего счетчика TWM, за исключением того, что счетчик предварительно уменьшен.$0$
2. Резервные ячейки установлены в , за исключением ячейки , которая установлена ​​в .$0$$u(c-1)$$2R$
3. Все остальные ячейки, доступные программе (конечное число), устанавливаются в .$1$

Затем указатель ленты перемещается в положение (всегда ненулевая ячейка), прежде чем мы достигнем первой программы .$u(c-1)-H$[

Начало внешнего цикла

В начале итерации внешнего цикла указатель ленты будет иметь значение или для счетчика .$u(x)-H$$v(x)-H$$x$

Пусть будет следующим счетчиком для посещения.$y=((x+1)\bmod c)$

Движение помещает указатель ленты в позицию, а не слева от .>$\times (H+cN+1)$$\equiv y\pmod c$$v(y)$

Внутренний цикл теперь ищет влево с шагом нулевую ячейку. Если счетчик равен нулю, он остановится на ячейке (ноль) значения ; в противном случае он найдет запасную ячейку .[ <$\times c$ ]$c$$y$$v(y)$$u(y)$

Какая бы ячейка ни была найдена, она становится новой активной клеткой.

корректировок

Регулировки фазы регулирует различные клетки на ленте на основе их положения относительно активной ячейки. Этот раздел содержит только +-><команды, и поэтому эти корректировки происходят безоговорочно. Однако, поскольку все связанные со счетчиком ячейки находятся в шаблоне линейки Голомба, любые корректировки, которые не являются подходящими для текущей активной ячейки, будут пропускать все важные ячейки и вместо этого настраивать некоторую нерелевантную ячейку (сохраняя ее нечетной).

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

Необходимые корректировки:

1. Отрегулируйте ячейку предыдущего счетчика на .$u(x)$$-2R$
2. Отрегулируйте запасную ячейку текущего счетчика на , за исключением случаев, когда текущая активная ячейка и поэтому мы должны остановиться.$u(y)$$2R$v ( h )$v(h)$
3. Настройте ячейку значения следующего счетчика на (уменьшение счетчика).$v((y+1)\bmod c)$$-2$
4. Когда активная ячейка является ячейкой значения (таким образом, счетчик достиг нуля), отрегулируйте все ячейки значения на из карты триггеров TWM. Сам настраивается на .$v(y)$$y$$v(z)$$2f(y,z)$$v(y)$$2R$

Первая и вторая корректировка выше сделана необходима тот факт , что все активные клетки должны регулировать себя одним и тем же значение, которое для значений ячеек, и , таким образом , также и для резервных клеток. Это требует подготовки и очистки резервных ячеек, чтобы гарантировать, что они возвращаются к как в ветви значений, так и в резервных ветвях.$2R$$0$

Конец внешнего цикла

Движение означает, что в конце фазы регулировки указатель ленты перемещается на слева от активной ячейки.<$\times H$$H$

Для всех активных клеток других , чем значение ячейки Остановки счетчика , это не имеет значения ячейки, и так нечетно и не равно нулю, и внешний цикл продолжается в течение следующей итерации.$v(h)$

Для вместо этого указатель помещается в соответствующую запасную ячейку , для которой мы сделали выше исключение, чтобы держать его равным нулю, и поэтому программа выходит из финала и останавливается.$v(h)$$u(h)$]

Я не уверен на 100%, что это невозможно сделать с помощью двух наборов скобок. Однако, если ячейки ленты BF допускают неограниченные значения, достаточно трех наборов скобок. (Для простоты я также предполагаю, что мы можем переместить головку ленты влево от ее начальной точки, хотя, поскольку эта конструкция использует только конечную область ленты, мы могли бы снять это ограничение, добавив достаточно много >команд в начале Программа.) Конструкция ниже требует предположения Артинуметь составлять произвольно большие программы; однако, даже если гипотеза Артина неверна, все равно будет возможно косвенно показать полноту по Тьюрингу посредством перевода интерпретатора языка, полного по Тьюрингу, в BF, используя конструкцию, приведенную ниже, и запуска произвольных программ, передавая их в качестве входных данных для этого интерпретатора.

Завершающим по Тьюрингу языком, который мы собираем в неограниченный BF, является Модель Водопада , которая является одной из простейших известных вычислительных моделей. Для людей, которые его еще не знают, он состоит из ряда счетчиков (и начальных значений для них) и функции от пар счетчиков до целых чисел; Выполнение программы состоит из многократного вычитания 1 из каждого счетчика, затем, если любой счетчик равен 0, добавление к каждому счетчику (программа написана таким образом, что это никогда не случается с несколькими счетчиками одновременно). За моей ссылкой есть доказательство полноты по Тьюрингу для этого языка. Без ограничения общности будем считать, что все счетчики имеют одинаковое значение самовозврата (т.е.$f$$x$$f(x,y)$$y$$f(x,x)$ одинаково для всех ); это безопасное предположение, потому что для любого конкретного добавление одной и той же константы к каждому не изменит поведение программы.$x$$x$$f(x,y)$

Пусть будет числом счетчиков; без ограничения общности (предполагая гипотезу Артина), предположим, что имеет первообразный корень 2. Пусть будет , где - наименьшая степень 2, превышающая . Без ограничения общности будет меньше ( ограничено полиномиально, растет экспоненциально, поэтому любой достаточно большой будет работать).$p$$p$$q$$p(1+s+s^2)$$s$$p$$2q$$2^p$$2q$$2^p$$p$

Расположение ленты следующее: мы нумеруем каждый счетчик целым числом (и без потери общности мы предполагаем, что есть один счетчик останова и нумеруем его ). Значение большинства счетчиков хранится в ленте , за исключением счетчика 0, который хранится в ленте . Для каждой нечетной ячейки ленты от ячейки -1 до включительно включительно$0 \leq i < p$$2$$2^i$$2q$$2^{p+1}+2p+1$, эта ячейка ленты всегда содержит 1, если она не находится непосредственно слева от счетчика, в этом случае она всегда содержит 0. Ячейки ленты с четным номером, которые не используются в качестве счетчиков, имеют не имеющие значения (которые могут быть или не быть 0 ); и нечетные ячейки ленты вне указанного диапазона также имеют не относящиеся к делу значения. Обратите внимание, что установка ленты в соответствующее начальное состояние требует инициализации только конечного числа элементов ленты постоянными значениями, что означает, что мы можем сделать это с помощью последовательности <>+-инструкций (фактически, только >+необходимых), то есть без скобок. В конце этой инициализации мы перемещаем указатель ленты в ячейку -1.

Общая форма нашей программы будет выглядеть так:

инициализация корректировка[>>>[ >$\times(2^p-1)$ [ <$\times(2p)$ ]>-] <<<]

Инициализация помещает ленту в ожидаемую форму и указатель на ячейку -1. Это не ячейка слева от счетчика (0 не является степенью 2), поэтому она имеет значение 1, и мы входим в цикл. Инвариант цикла для этого самого внешнего цикла состоит в том, что указатель ленты находится (в начале и в конце каждой итерации цикла) на три ячейки слева от счетчика; можно видеть, что цикл, таким образом, будет выходить только в том случае, если мы на три ячейки слева от счетчика 2 (каждый счетчик имеет 1 три ячейки слева, так как наличие 0 означает, что позиции ленты двух счетчиков были 2 ячейки друг от друга, только две степени 2, которые отличаются на 2, являются и , и двоичное представление изменяется от строк с до строк$2^1$$2^2$$q$$0$$1$s или наоборот по крайней мере четыре раза и, следовательно, не может быть 1 от степени 2).

Второй цикл многократно повторяет счетчики, уменьшая их. Инвариант цикла состоит в том, что указатель ленты всегда указывает на счетчик; таким образом, цикл завершится, когда какой-то счетчик станет равным 0. Уменьшение равно -; путь от одного счетчика к другому более сложен. Основная идея состоит в том, что перемещение пробелов вправо от поместит нас в нечетную ячейку , которая находится справа от любого счетчика ( последний счетчик, положительный, потому что положительный); по модулю это значение конгруэнтно (по малой теореме Ферма) . Внутренняя петля многократно перемещается влево$2^p-1$$2^x$$2^p+2^x-1$$2^p$$2^x-1$$x$$2p$$2^x+1$$2p$ пробелы, также не изменяющие индекс ячейки ленты по модулю , и должны в конечном итоге найти ячейку, конгруэнтную по модулю которая имеет значение (которое будет ячейкой слева от некоторого счетчика); из-за нашего примитивного корневого требования есть ровно одна такая ячейка ( соответствует по модулю , а соответствует для любого другой , где - дискретный логарифм по основанию 2 по модулю ). Дополнительно видно, что положение указателя ленты по модулю$2p$$2^x+1$$2p$$2q-1$$-1$$2p$$2^{\log_{2,p}(r)+1}-1$$2r-1$$r$$\log_{2,p}$$p$$2p$увеличивается на каждый раз вокруг средней петли. Таким образом, указатель ленты должен циклически переключаться между всеми счетчиками (в порядке их значений по модулю ). Таким образом, каждые итераций мы уменьшаем каждый счетчик (по мере необходимости). Если цикл прерывается на полпути через итерацию, мы возобновим уменьшение при повторном входе в цикл (поскольку остальная часть самого внешнего цикла не вносит никаких изменений в позицию указателя ленты).$2$$p$$2p$$p$

Когда счетчик достигает 0, средний цикл обрывается, что приводит нас к коду «корректировки». Это в основном просто кодировка ; для каждой пары , это добавляет на элемент ленты , который на одинаковом расстоянии слева / справа от текущего указателя на магнитной ленте в качестве счетчика «ы местоположения ленточного влево / вправо счетчика » ы местоположение ленты (а затем удаляет указатель ленты обратно туда, где она началась). Всякий раз, когда , это расстояние оказывается уникальным:$f$$(x,y)$$f(x,y)$$y$$x$$x\neq y$

• Разница между двумя степенями 2 - это двоичное число, состоящее из строки 1 или более с, за которой следует строка 0 или более с (со значениями места начала числа и начала строки в зависимости от большего и меньшего соответственно и ); таким образом, все эти различия различны. * Что касается разности степени 2 и , она должна содержать не менее двух переходов между строками с и с ($1$$0$$0$$x$$y$$q$$1$$0$$q$ содержит не менее четырех таких переходов, вычитание может удалить только 2), таким образом, отличается от всех различий двух степеней двух, и эти различия, очевидно, также отличаются друг от друга.

Для мы, очевидно, находим, что пройденное расстояние равно 0. Но поскольку все равны, мы можем просто использовать это как корректировку для текущей ячейки. И можно видеть, что код корректировки, таким образом, реализует эффект «когда счетчик достигает 0» для каждого счетчика; все ячейки, которые фактически представляют счетчики, будут корректироваться на правильную величину, а все остальные настройки будут влиять на нечетные ячейки с четными номерами (разница между двумя четными числами четная), которые не влияют на поведение программы.$x=y$$f(x,y)$

Таким образом, теперь у нас есть рабочая компиляция любой программы в The Waterfall Model для BF (включая поведение при остановке, но не включая ввод-вывод, который не нужен для полноты по Тьюрингу), используя только три пары скобок и, таким образом, три пары скобок достаточно для полноты по Тьюрингу.