Абак, алгорифмы Маркова, равнодоступная адресная машина

Абак

Абак наряду с машинами Тьюринга является одной из простейших универсальных моделей вычислений. Это числовая модель; элементами информации являются целые неотрицательные числа.

Память представляет собой потенциально бесконечный набор ячеек, каждая ячейка может содержать любое целое неотрицательное число. Считается, что ячейки пронумерованы числами $$1, 2, \ldots$$.

Исполняющее устройство способно выполнять всего две операции (элементарные команды) над числами, это прибавление (increment) и вычитание (decrement) единицы из указанного в команде числа. Команды имеют вид $${\rm inc}(x)$$ и $${\rm dec}(x)$$, где $$x$$ — номер ячейки. Поскольку в каждом конкретном алгоритме может быть использовано лишь конечное число ячеек и с номерами ячеек никаких операций не производится, мы будем обозначать их в примерах для наглядности отдельными буквами, возможно, с использованием индексов.

Программа (алгоритм) — это ориентированный граф, вершинам которого приписаны элементарные команды указанного выше вида. Из каждой вершины, помеченной командой вида $${\rm inc}(x)$$, выходит одна дуга в вершину со следующей командой. Из каждой вершины, помеченной командой вида $${\rm dec}(x)$$, выходят две дуги. Одна из них помечается знаком " $$+$$ " и ведет в вершину, помеченную командой, которая должна выполняться следующей в случае, если перед ее выполнением в ячейке $$x$$ находилось число, отличное от нуля. Вторая дуга помечается знаком " $$-$$ " и ведет в вершину, помеченную командой, которая должна выполняться следующей в случае, если перед ее выполнением в ячейке $$x$$ находилось число нуль. Одна из вершин графа помечается как входная, в нее ведет дуга "из ниоткуда", выходных вершин может быть несколько.

Несмотря на простоту этой модели вычислений, она "эквивалентна по силе" любой из изучавшихся универсальных моделей вычислений и относительно нее можно сформулировать тезис, аналогичный тезису Черча, который может выглядеть следующим образом. Любая интуитивно вычислимая функция может быть вычислена на абаке. При этом, конечно, надо условиться о том, где располагаются входные аргументы и куда следует поместить результат (значение вычисляемой функции).

Примеры программ. В рассмотренных ниже примерах операция $${\rm inc}(x)$$ обозначается для краткости через $$x^+$$, а операция $${\rm dec}(x)$$ — через $$x^-$$. Основные операции изображены кружками. Прямоугольниками изображены операции, для которых в предыдущих примерах построены алгоритмы. Знак " $$-$$ " на соответствующих дугах опущен. Сформулируйте инварианты циклов во всех рассмотренных ниже примерах.

Программа $$\fbox{x: = 0}$$

В языках программирования эта операция обычно является элементарной. На абаке это действие можно выполнить следующей программой:

Программа $$\fbox{y := x}$$

Программа $$\fbox{x := x + y}$$

Программа $$\fbox{z := x + y}$$

Программа $$\fbox{x: = x \ast y}$$

Программа $$\fbox{z := x\ast y}$$

Программа $$\fbox{z := x^y}$$

Примеры неразрешимости

Функцию $$p\colon N \to N$$ назовем вычислимой на абаке, если существует программа $$P$$, которая, получив в некоторой, заранее обусловленной ячейке $$x$$ значение аргумента $$n$$, а в остальных ячейках — нули, через конечное число шагов остановится, и в ячейке $$y$$ будет находиться $$p(n)$$.

Проблема построения невычислимой функции известна как "проблема усердного бобра". Пусть $$A$$ — абак-программа и $$y$$ — номер некоторой ячейки. Определим величину $$f(A, y)$$ следующим образом. Если в начальный момент все ячейки содержат число 0 и программа $$A$$ через конечное число шагов останавливается, то $$f(A, y)$$ равно числу $$[y]$$ в момент остановки. Если же программа работает бесконечно, то считаем $$f(A, y) = 0$$. Величину $$f(A, y)$$ назовем $$y$$ -продуктивностью программы $$A$$.

Обозначим через $$\wt{A}(n)$$ множество всех абак-программ, состоящих из $$n$$ команд. Определим функцию $$p(n)$$ как максимум $$f(A, y)$$ по всем программам $$A$$ из $$\wt{A}(n)$$ и ячейкам $$y$$. Очевидно, эта функция определена при всех натуральных значениях аргумента и строго монотонна.

Лемма. Для любого натурального числа $$n$$ выполняется неравенство$$\eq*{ p(n + 17) \ge 2n. }$$

Для доказательства достаточно рассмотреть программу, которая сначала запишет $$0$$ в ячейку $$x$$, затем прибавит к ней $$n$$ раз 1, скопирует содержимое ячейки $$x$$ в ячейку $$y$$ и добавит к ней содержимое ячейки $$x$$. Очевидно, после выполнения такой программы в ячейке $$y$$ будет число $$2n$$, а подсчет числа команд показывает, что их будет $$n + 17$$. Наличие такой программы (рис. 12.1) доказывает требуемое неравенство.

Предположим теперь, что $$p(n)$$ вычислима некоторой программой $$P$$, состоящей из $$k$$ команд, которая, получив $$n$$ в ячейке $$x$$, поместит ответ в ячейку $$y$$.

Тогда для каждого натурального $$n$$ можно построить программу, вычисляющую $$p(p(n + 17))$$, состоящую из $$n + 2k + 25$$ команд. Эта программа сначала запишет $$0$$ в ячейку $$x$$, затем прибавит к ней $$n + 17$$ раз единицу, затем с помощью программы $$P$$ в ячейке $$y$$ вычислит $$p(n + 17)$$, скопирует $$y$$ в $$x$$ и, наконец, опять с помощью программы $$P$$ вычислит $$p(p(n + 17))$$.

Наличие такой программы (рис. 12.2) означало бы, что при любом натуральном $$n$$ выполняется неравенство

Поскольку функция $$p(n)$$ монотонна, получаем

Сопоставляя это неравенство с неравенством в утверждении леммы, получим

что приводит к противоречию, например, при $$n = 2k + 26$$.

Итак, предположение о вычислимости функции $$p(n)$$ привело к противоречию.

На рис. 12.2 команда $$x^+$$ повторяется $$n + 17$$ раз, общее количество команд в программе $$n + 2k + 25$$, в ячейке $$y$$ вычисляется $$p(p(n + 17))$$.

Рассмотрим произвольную инъективную нумерацию $$g$$ программ, то есть нумерацию, ставящую в соответствие каждой программе $$P$$ ее номер $$g(P)$$, причем разным программам ставятся в соответствие разные номера. Программу назовем самоприменимой относительно ячейки $$x$$, если она, получив в ячейке $$x$$ свой номер, а в остальных ячейках — нули, через конечное число шагов завершает вычисления.

Рассмотрим функцию $$p\colon N \to N$$, определяемую следующим образом:

Докажем, что функция $$p$$ не вычислима никакой программой. Предположим, что $$p$$ вычисляется программой $$P$$, которая, получив в ячейке $$x$$ число $$n$$, остановится через конечное число шагов и в ячейке $$y$$ оставит $$p(n)$$. Рассмотрим программу $$P'$$, изображенную на рис. 12.3.

Если $$P'$$ самоприменима относительно ячейки $$x$$, то $$p(g(P')) = 1$$, поэтому, когда проработает программа $$P$$, в ячейке $$y$$ будет записана 1 и остальная часть программы $$P$$ — будет работать без остановки. Следовательно, $$P$$ — не самоприменима относительно $$x$$.

Если же $$P'$$ не самоприменима относительно ячейки $$x$$, то $${p(g(P')) = 0}$$, следовательно, когда проработает программа $$P$$, в ячейке $$y$$ будет записан 0 и тогда остальная часть программы $$P$$ — сразу же завершит работу. Следовательно, $$P$$ — самоприменима относительно $$x$$.

Итак, предположение о вычислимости функции $$p(n)$$ в любом случае приводит к противоречию.

Алгорифмы Маркова

Термин "алгорифм" является устаревшим вариантом современного термина "алгоритм", однако по отношению к алгоритмам Маркова принято использовать авторский вариант.

Информация, обрабатываемая алгорифмом Маркова, представляется словом в некотором фиксированном алфавите $$A$$.

Алгорифм (программа) представляется последовательностью пар слов в алфавите $$A$$. Пары, составляющие алгорифм, называются также подстановками и записываются в виде$$\eq*{ \al \to \beta, }$$ где $$\al$$, $$\beta$$ — слова в алфавите $$A$$, причем $$\beta$$ может быть пустым (обозначаем $$\lm$$ ). Программа имеет вид $$\begin{gather*} \al_1 \to \bt_1\\ \al_2 \to \bt_2\\ \mdots{2cm}\\ \al_i \to \bt_i!\\ \mdots{2cm}\\ \al_n \to \bt_n. \end{gather*} $$ Некоторые подстановки помечаются восклицательным знаком и называются заключительными.

Функционирование. Во входном слове ищется фрагмент, совпадающий с левой частью первой подстановки. Если фрагмент находится, то самый левый такой фрагмент во входном слове заменяется на ее правую часть, в противном случае рассматривается вторая подстановка из алгорифма и так далее. Вычисления заканчиваются, когда ни одна из левых частей подстановок не является фрагментом обработанного к данному моменту слова или когда выполнена заключительная подстановка. Заметим, что описанный таким образом процесс может оказаться и бесконечным.

Замечание. Алгорифмы Маркова составляют теоретическую основу системы программирования, использующую язык РЕФАЛ.

Пример. Алфавит $$A = \{1, +\}$$. Здесь запятая не является символом алфавита.

Рассмотрим программу$$\begin{align*} 1. \q 1+ \to +1,\\ 2. \q ++ \to +,\\ 3. \q + \to \lm! \end{align*}$$ Убедитесь в том, что она входное слово вида $$11\ldots 1 + 11\ldots 11$$ переработает в слово $$11\ldots 1$$, в котором число символов "1" — такое же, как во входном слове. Можно считать, что программа выполняет сложение натуральных чисел, представленных в унарной системе счисления.

Пример. Алфавит $$A = \{1, \ast, v, z\}$$.

Программа$$\begin{align*} 1. \q *11 \to v*1 \\ 2. \q *1 \to v\\ 3. \q 1v \to v1z\\ 4. \q zv \to vz\\ 5. \q z1 \to 1z\\ 6. \q v1 \to v\\ 7. \q vz \to z\\ 8. \q z \to 1 \\ 9. \q 1 \to 1! \end{align*}$$

Рассмотрим протокол вычислений на входном слове $$11\ast 111$$. Справа указаны применяемые подстановки.$$\begin{align*} 11\ast 111 \ast11 \to v \ast 1\\[-1pt] 11v \ast 11 \ast 11 \to v \ast 1\\[-1pt] 11 vv\ast 1 \ast 1 \to v\\[-1pt] 11vvv 1v \to v1z\\[-1pt] 1v1zvv 1v \to v1z\\[-1pt] v1z1zvv zv \to vz\\[-1pt] v1z1vzv 1v \to v1z\\[-1pt] v1zv1zzv zv \to vz\\[-1pt] v1vz1zzv 1v \to v1z\\[-1pt] vv1zz1zzv zv \to vz\\[-1pt] vv1zz1zvz zv \to vz\\[-1pt] vv1zz1vzz 1v \to v1z\\[-1pt] vv1zzv1zzz zv \to vz\\[-1pt] vv1zvz1zzz zv \to vz\\[-1pt] vv1vzz1zzz 1v \to v1z\\[-1pt] vvv1zzz1zzz z1 \to 1z\\[-1pt] vvv1zz1zzzz z1 \to 1z\\[-1pt] vvv1z1zzzzz z1 \to 1z\\[-1pt] vvv11zzzzzz v1 \to v\\[-1pt] vvv1zzzzzz v1 \to v\\[-1pt] vvvzzzzzz vz \to z\\[-1pt] vvzzzzzz vz \to z\\[-1pt] vzzzzzz vz \to z\\[-1pt] zzzzzz z \to 1\\[-1pt] 1zzzzz z \to 1\\[-1pt] 11zzzz z \to 1\\[-1pt] 111zzz z \to 1\\[-1pt] 1111zz z \to 1\\[-1pt] 11111z z \to 1\\[-1pt] 111111 1 \to 1! \end{align*}$$ Если считать, что во входном слове закодирована задача умножения $$2\ast 3$$ в унарной системе счисления, то в выходном слове получен ответ 6.

Докажите, что программа дает верный ответ при любом корректном входном слове.

Равнодоступная адресная машина

Равнодоступная адресная машина (РАМ) — это числовая модель вычислительного устройства. Эта модель является наиболее близкой из рассмотренных к реальным вычислительным машинам и позволяет наиболее реалистично применять теоретические оценки сложности алгоритмов к реальным вычислениям.

Память машины состоит из регистров (ячеек). Каждый регистр имеет адрес и может содержать произвольное число. Регистр с номером 0 называется сумматором.

Программа — последовательность пронумерованных команд. Команда имеет вид$$\eq*{ \langle \t{код операции}\rangle\langle \t{операнд}\rangle }$$

Коды операций$$\eq*{ {\rm Load}, {\rm Store}, {\rm Add}, {\rm Sub}, {\rm Mult}, {\rm Div}, {\rm Read}, {\rm Write}, {\rm Jump}, {\rm JgtZ}, {\rm Jzero}, {\rm Halt}. }$$

Операнд может быть одного из трех видов

где $$i$$ — натуральное число.

Содержимое регистра с номером $$i$$ обозначим через $$c(i)$$. Значение $$v(a)$$ операнда $$a$$ определяется в зависимости от его вида следующим образом.$$\eqa*{ v(a)\t{ — число}\ i,\ \t{если}\ a\ \t{имеет вид} = i,\\ v(a)\t{ — число}\ c(i),\ \t{если}\ a\ \t{имеет вид} i,\\ v(a)\t{ — число}\ c(c(i)),\ \t{если}\ a\ \t{имеет вид} \ast i. }$$

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

При определении веса команды используется функция $$L\colon Z \to Z$$, выражающая длину записи числа$$\eq*{ L(i)=\left\{\begin{aligned} \log(i)+1 \t{при}\ i\ne 0, \\ 1 \t{при}\ i=0. \end{aligned} \right. }$$

Основание логарифма при получении асимптотических оценок не имеет существенного значения.

Вес $$t(a)$$ операнда $$a$$ определяется в зависимости от его вида следующим образом:$$\eqa*{ t(a) = L(i),\ \t{если}\ a\ \t{имеет вид} = i,\\ \\ t(a) = L(i) + c(i),\ \t{если}\ a\ \t{имеет вид} i,\\ \\ t(a) = L(i) + L(c(i)) + L(c(c(i))),\ \t{если}\ a\ \t{имеет вид} \ast i. }$$

Например, команда $${\rm Add} \ast i$$ имеет логарифмический вес$$\eq*{ L(c(0)) + L(i) + L(c(i)) + L(c(c(i))). }$$

Временная сложность программы определяется как сумма весов всех выполненных команд с учетом их многократного выполнения.

Емкостная сложность программы определяется как сумма по всем регистрам длин максимальных чисел, побывавших в этих регистрах.

Пример. Рассмотрим вычисление $$n^n$$:

$$\formula{ {\rm Read}(r);\\ \t if\ r < 0\ \t then\ \t{write}(0)\ \t else\\ \{r_2:= r;\ r_3:= r_1-1;\ \t while\ r_3< 0\ \t do\ \{r_2:= r_2 \ast r;\ r_3:= r_3-1\};\ \t{write}\ (r_2)\}. }$$

Этот псевдокод легко может быть заменен РАМ-программой, представленной в таблице 12.2.

Когда команда $$15$$ выполняется $$i$$ -й раз, сумматор содержит $$n^i$$, а $$r2$$ содержит $$n$$. Эта команда выполняется $$({n}-1)$$ раз. При равномерном весовом критерии суммарное время — $$O(n)$$. При логарифмическом весовом критерии суммарное время равно $$\suml(L(n^i) + L(n))$$, где суммирование ведется по $$i = 1,2\dts n$$. Поскольку $$(L(n^i) + L(n))\sim(i + 1) \log (n)$$, получаем$$\eq*{ \suml(L(n^i)+L(n))= O(n^2 \log n). }$$

Емкостная сложность программы при равномерном критерии равна $$O(1)$$, при логарифмическом — $$O(n \log n)$$.