Как физика полна абстракций типа абсолютно черного тела, абсолютно твёрдого тела, материальной точки и т.п., так теория алгоритмов славится своими абстрактными вычислительными машинами. Одной из них является так называемая "машина с неограниченными регистрами" или сокращённо МНР. Поскольку пару дней назад пришлось с этой машиной познакомиться, напишу здесь то, что удалось про неё узнать.
Итак, что это за штука? Представим себе последовательность ячеек, в которых хранятся натуральные числа. Эти ячейки можно занумеровать: 1, 2, 3 и т.п. Манипулирование ячейками производится при помощи программы, то есть, последовательности строк, содержащих некие команды:
1 : какая-то команда
2 : какая-то команда
3 : какая-то команда
и т.д.
Работа программы состоит в последовательном проходе строк и выполнении содержащихся в них команд. Эта пара, "последовательность ячеек + программа" и составляет МНР.
Команды для МНР бывают всего четырёх типов:
- Z(n) - обнулить число, хранящееся в ячейке под номером n;
- S(n) - увеличить число, хранящееся в ячейке под номером n, на единицу;
- T(n, m) - скопировать число, хранящееся в ячейке n, в ячейку m;
- J(n, m, q) - условный переход, работающий так: если число в ячейке с комером n равно числу в ячейке с номером m, то программа переходит к обработке команды, содержащейся в строке q (и далее по списку).
Как видим, выбор небольшой. Тем не менее, даже с этим набором можно изрядно портить жизнь студентам, задавая им заковыристые задачи. Рассмотрим же возможности МНР подробнее.
Во-первых, МНР допускает пустой оператор. Сделать его просто. Если, например, программа добралась до строки 20, то пустой оператор выглядит так:
20: J(1, 1, 21)
То есть, поскольку значение в первой ячейке всегда равно само себе, то будет осуществлён переход на следующую строку. Так же просто выглядит оператор безусловного перехода:
... : J(1, 1, номер_строки_куда_хотим_перейти)
Во-вторых, любую группу строк можно "изолировать" от основной программы следующей конструкцией:
...
// перескакиваем строки 101-199
100 : J(1, 1, 200)
//строки 101-199 не будут выполняться
101 : ...
...
199 : ...
// продолжаем работу
200 : ...
Идём дальше. Медитирование над вышеперечисленным набором команд привело меня к ужасающему открытию: в этой МНР невозможно устроить условный переход на строку, номер которой будет задаваться значением, хранящемся в памяти! Это очень плохо: нам оказываются недоступны динамические массивы и рекурсивный вызов функций, когда функция F вызывает функцию G, которая, в свою очередь, вызывает функцию F и т.д.
Однако некоторым утешением - правда, довольно слабым - может служить следующая конструкция. Рассмотрим пример. Пусть у нас в ячейках с номерами 1001, 1002, 1003 и т.п. хранятся заранее заготовленные константы 1, 2, 3, 4, и т.д. И пусть у нас есть желание переходить на строки программы q₁, q₂, q₃ и т.д. в зависимости от значения, которое лежит в ячейке 1000. Добиться этого поможет следующая конструкция:
... : J(1000, 1001, q₁)
... : J(1000, 1002, q₂)
... : J(1000, 1003, q₃)
...
Рассмотрим, как это работает. Запихнём, например, в ячейку с номером 1000 число 3. Тогда первые две из этой группы команд машина проскочит, а третья команда, поскольку числа в ячейках 1000 и 1003 совпадают, вызовет переход к строке q₃. Как говорится: ну, хоть так.
Имея в арсенале пару этих нехитрых приёмов - изолирование строк и условные переходы - можно приступить к созданию подпрограмм.
Подпрограммы организовать достаточно просто. Поскольку подпрограмма использует конечную область памяти, а динамических массивов нам бог не дал, то можно заранее отвести ей какой-нибудь достаточно большой интервал ячеек, и пусть там крутится как хочет.
Например, напишем подпрограмму, вычисляющую максимум из двух натуральных чисел.
Отведём этой подпрограмме для жизни ячейки 10000-19999. Для того, чтобы вычислить максимум из двух чисел, этого ей хватит за глаза. Пусть входные данные будут выглядеть следующим образом:
- ячейка 10000 - хранит число, соответствующее точке возврата из подпрограммы;
- ячейки 10001 и 10002 - хранят числа, максимум из которых надо вычислить;
- ячейка 10003 - будет содержать результат, то есть, максимум из двух чисел, заданных в ячейках 10001 и 10002.
Будем считать, что подпрограмме отведены строки 100-199. Получаем:
// безусловный переход, перескакивающий подпрограмму
100 : J(1, 1, 199)
// НАЧАЛО подпрограммы
// обнуляем ячейку с будущим результатом
101 : Z(10003)
// заводим дополнительные ячейки для счётчиков
102 : Z(10004)
103 : Z(10005)
// заводим константу 2
104 : Z(10006)
105 : S(10006)
106 : S(10006)
// если одно из чисел - ноль, то ответ очевиден
107 : J(10001, 10003, 117)
108 : J(10002, 10003, 119)
// оба числа ненулевые - начинаем в цикле увеличивать
// счётчик в ячейке 10004, пока он не "пройдёт" оба аргумента
109 : S(10003)
110 : S(10004)
// если счётчик в ячейке 10004 добрался до одного из аргументов,
// обрабатываем это событие
111 : J(10004, 10001, 114)
112 : J(10004, 10002, 114)
// ничего интересного не произошло,
// крутим цикл дальше
113 : J(1, 1, 109)
// счётчик в ячейке 10004 сравнялся с одним
// из чисел, увеличиваем счётчик в ячейке 10005
114 : S(10005)
// если значение счётчика в ячейке 10005 равно 2,
// значит, максимум найден, выходим
115 : J(10005, 10006, 121)
// а иначе крутим цикл дальше
116 : J(1, 1, 109)
// первое число оказалось нулём
117 : T(10002, 10003)
118 : J(1, 1, 121)
// второе число оказалось нулём
119 : T(10001, 10003)
120 : J(1, 1, 121)
// завершение подпрограммы - переход, куда скажет ячейка 10000
121 : J(10000, 1001, q₁)
122 : J(10000, 1002, q₂)
123 : J(10000, 1003, q₃)
...
// КОНЕЦ подпрограммы
199 : J(1, 1, 200)
Вызвать эту подпрограмму не составит труда. Пусть, например, нам понадобился в строке 500 основной программы максимум двух чисел, хранящихся в ячейках с номерами 1 и 2. Поступаем так:
// строка 121 подпрограммы теперь выглядит так:
121 : J(10000, 1001, 504)
...
// говорим подпрограмме, вычисляющей максимум, куда ей вернуться
500 : T(1001, 10000)
// передаём список аргументов
501 : T(1, 10001)
502 : T(2, 10002)
// вызываем подпрограмму, вычисляющую максимум
// переданных аргументов
503 : J(1, 1, 101)
// обрабатываем результат, копируя его в ячейку с номером 3
504 : T(10003, 3)
Таким образом, программа для МНР может быть представлена в следующем виде:
Правда, как я уже сказал, мне не удалось понять, как устраивать рекурсивный вызов подпрограммы №1 из подпрограммы №2, вызванной, в свою очередь, из подпрограммы №1, поскольку повторный вызов подпрограммы №1, созданной по вышеприведенному рецепту, затрёт первоначальную точку перехода, но в остальном получается вполне рабочая машинка, в которой уж арифметику-то реализовать достаточно просто, даже для отрицательных и рациональных чисел.
Действительно, на первый взгляд кажется, что МНР не приспособлена для обработки отрицательных чисел. Даже если нам удастся, сломав систему, записать в ячейку какое-нибудь -2, мы с этим числом ничего сделать не сможем, только последовательностью S-команд увеличивать. Однако выход из этой ситуации достаточно прост: нужно для хранения целых чисел отвести по две ячейки. Тогда, например:
... 5 0 ... - будет соответствовать целому числу +5
... 0 5 ... - будет соответствовать целому числу -5
Таким же образом можно охватить рациональные числа, отведя для них по три ячейки и считая, что:
... 5 0 2 ... - соответствует +5/2
... 0 5 2 ... - соответствует -5/2
С иррациональностями такой номер, конечно, не пройдёт, но их можно приближать, как в обычном компьютере, рациональными с любой точностью.
Ну и в качестве маленького приложения: вариант программы МНР для вычисления определителя целочисленной матрицы. Правда, оговорюсь, это не совсем классическая программа, поскольку в качестве переходов использованы не номера строк, а осмысленные имена меток, но при желании эти имена можно заменить на номера (хоть это и то ещё удовольствие) .
