Машины Минского. 
Дискретный анализ. 
Формальные системы и алгоритмы

Необычайно простую универсальную модель вычислений предложил Марвин Минский [20, 21]. Машина Минского снабжена конечным числом регистров, R_n, каждый из которых содержит неотрицательное целое число. Договоримся обозначать через Vi содержимое регистра с номером г. Программа для машины Минского состоит из конечного нумерованного списка команд. Команды бывают трёх следующих типов:

• • inc i., j увеличить значение регистра г на 1 и передать управление команде с номером j;
• • dec i, j. к если значение регистра г равно 0, то передать управление команде с номером j, в противном случае уменьшить на 1 значение регистра г, а управление передать команде с номером к;
• • halt остановиться.

В начальной конфигурации значения всех регистров, кроме первого, равны 0. Результатом работы является значение первого регистра после остановки.

Как это ни удивительно, но такая вычислительная модель универсальна.

Выше была доказана теорема 4.38, которая фактически утверждает универсальность машин Тыоринга в двухбуквенном алфавите. Так что достаточно показать, что на машинах Минского можно моделировать работу машины Тыоринга в алфавите {0,1}.

Приведём несколько примеров программ для машин Минского, они потребуются в дальнейшем для моделирования работы машин Тыоринга. Рассматривайте эти примеры и как задачи — докажите сделанные в них утверждения.

Пример 4.44 (Обнуление регистра). Рассмотрим такую программу:

1: dec г, n, 1.

Она уменьшает значение регистра i до нуля, после чего передаёт управление команде с номером п.

Пример 4.45 (Копирование регистра). Программа.

• 1: dec г, п, 2
• 2: inc j, 3
• 3: inc к, 1

увеличивает содержимое регистров j, к на содержимое регистра г, а после этого передаёт управление команде с номером п. Содержимое регистра г в конце работы программы равно 0. Если перед началом выполнения этой программы регистры j, к были пусты (содержали нули), а регистр г содержал число, то после выполнения этой программы уже два регистра будут содержать значение г?*. Поэтому мы называем эту программу копированием регистра. Упрощённый вариант этой программы.

• 1: dec i, n, 2
• 2: inc j, 1

переносит значение регистра г в регистр j (если последний пуст перед началом выполнения программы).

Комбинируя эти две программы, можно написать программу, которая копирует значение регистра % в регистр j, сохраняя в конце работы значение в регистре г. Для этого требуется один вспомогательный регистр.

Пример 4.46 (Проверка чётности). Программа.

• 1: dec i, n, 2
• 2: dec г, га, 1

уменьшает значение регистра i до 0 и передаёт управление команде с номером п, если в начале работы регистр i содержал чётное число, в противном случае управление передаётся команде с номером га.

Задача 4.12. Напишите программы для машины Минского, которые решают следующие задачи:

• (а) удвоение регистра г (в начале работы значение регистра равно и, в конце 2v)
• (б) нахождение остатка от деления на 2 (в начале работы значение регистра равно v, в конце v mod 2);
• (в) нахождение частного от деления на 2 (в начале работы значение регистра равно v, в конце у/2).

Используйте в пунктах (а) и (в) не более двух вспомогательных регистров. Для пункта (б) можно составить программу без вспомогательных регистров.

Описанных в этих примерах возможностей машин Минского уже достаточно для моделирования работы произвольной машины Тьюринга в алфавите {0,1}. Напомним, что символ 0 мы считаем пустым. Поэтому любой конфигурации такой машины Тыориига uqv, u, v Е {0,1}*, можно сопоставить состояние q и два числа ? и г, двоичные записи которых имеют вид и, v^R соответственно (v^R обозначает слово, записанное в обратном порядке).

На каждом такте машина Тыориига меняет символ, над которым находится головка (младший бит числа г), и сдвигает головку на одну позицию влево или вправо. Изменение символа меняет число г на г — 1 (если 1 заменяется на 0) или на г + 1 (если 0 меняется на 1). Возможные изменения чисел ? и г зависят от направления движения и чётности чисел ? и г. Например, если оба числа чётные, а сдвиг происходит вправо, то ? увеличится в два раза (к двоичной записи добавляется 0 в конце), а г уменьшится в два раза. Если ? чётное, а г нечётное и головка сдвигается вправо, то ? заменяется на 2? + 1, а г — на (г — 1)/2.

Задача 4.13. Составьте таблицу изменений чисел ? и г, кодирующих состояние ленты машины Тьюринга, для всех возможных вариантов чётности чисел и направления движения (всего будет, как нетрудно понять, 8 различных вариантов).

Задача 4.14. Напишите программы для машин Минского, которые меняют значения Си г по правилам, найденным в предыдущей задаче. Используйте при этом не более двух вспомогательных регистров.

После решения этих задач легко построить машину Минского, которая моделирует работу некоторой машины Тьюринга в алфавите {0,1}. У этой машины два основных регистра (которые хранят числа С иг) и два вспомогательных регистра.

Команды машины Минского разбиваются на группы, которые соответствуют состояниям машины Тьюринга. Каждая группа начинается с команд, копирующих во вспомогательный регистр число г и определяющих его чётность, т. е. символ под головкой моделируемой машины. Далее меняется значение г (или не меняется — в зависимости от текущего состояния и символа); после чего выполняется одна из найденных в решении задачи 4.14 программ. Далее управление передаётся начальной команде той группы, которая отвечает новому состоянию моделируемой машины Т ыоринга.

Замечание 4.47. Машины Минского являются фактически ограниченным вариантом RAM. Следующие фрагменты RAM-программ реализуют команды машины Минского:

Здесь мы предполагаем, что регистры машины Минского — это ячейки памяти RAM. Нетрудно дополнить эти фрагменты командами чтения входа и записи выхода и получить моделирующую машину Минского RAM-программу.

Отсюда следуют два важных вывода. Во-первых, машины Минского моделируются на машинах Тыоринга с помощью описанного в разделе 4.3.3.2 моделирования RAM на машине Тыоринга. Во-вторых, из доказанной выше универсальности машин Минского следует универсальность RAM.