Теория нормальных алгоритмов (или алгорифмов, как называл их создатель теории) была разработана советским математиком А. А. Марковым (1903–1979) в конце 1940-х — начале 1950-х гг. XX в. Эти алгоритмы представляют собой некоторые правила по переработке слов в каком-либо алфавите, так что исходные данные и искомые результаты для алгоритмов являются словами в некотором алфавите.

Марковские подстановки

Алфавитом (как и прежде) называется любое непустое множество. Его элементы называются буквами, а любые последовательности букв — словами в данном алфавите. Для удобства рассуждений допускаются пустые слова (они не имеют в своем составе ни одной буквы). Пустое слово будем обозначать $\Lambda$ . Если $A$ и $B$ — два алфавита, причем $A\subseteq B$ , то алфавит $B$ называется расширением алфавита $A$ .

Слова будем обозначать латинскими буквами: $P,\,Q,\,R$ (или этими же буквами с индексами). Одно слово может быть составной частью другого слова. Тогда первое называется подсловом второго или вхождением во второе. Например, если $A$ — алфавит русских букв, то можем рассмотреть такие слова: $P_1= \text{paragraf},$ $P_2= \text{graf},$ $P_3=\text{ra}$ . Слово $P_2$ является подсловом слова $P_1$ , а $P_3$ — подсловом $P_1$ и $P_2$ , причем в $P_1$ оно входит дважды. Особый интерес представляет первое вхождение.

Определение 34.1. Марковской подстановкой называется операция над словами, задаваемая с помощью упорядоченной пары слов $(P,Q)$ , состоящая в следующем. В заданном слове $R$ находят первое вхождение слова $P$ (если таковое имеется) и, не изменяя остальных частей слова $R$ , заменяют в нем это вхождение словом $Q$ . Полученное слово называется результатом применения марковской подстановки $(P,Q)$ к слову $R$ . Если же первого вхождения $P$ в слово $R$ нет (и, следовательно, вообще нет ни одного вхождения $P$ в $R$ ), то считается, что марковская подстановка $(P,Q)$ неприменима к слову $R$ .

Частными случаями марковских подстановок являются подстановки с пустыми словами:

$(\Lambda,Q),\qquad (P,\Lambda),\qquad (\Lambda,\Lambda).$

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

Преобразуемое слово	Марковская подстановка	Результат
138 578 926	(8 578 9, 00)	130 026
тарарам	(ара, Λ)	трам
шрам	(ра, ар)	шарм
функция	(Λ, ζ-)	ζ-функция
логика	(ика, Λ)	лог
книга	(Λ, Λ)	книга
поляна	(пор, т)	[неприменима]

Для обозначения марковской подстановки $(P,Q)$ используется запись $P\to Q$ . Она называется формулой подстановки $(P,Q)$ . Некоторые подстановки $(P,Q)$ будем называть заключительными (смысл названия станет ясен чуть позже). Для обозначения таких подстановок будем использовать запись $P\to\,.\,Q$ , называя ее формулой заключительной подстановки. Слово $P$ называется левой частью, а $Q$ — правой частью в формуле подстановки.

Нормальные алгоритмы и их применение к словам

Упорядоченный конечный список формул подстановок

$\begin{cases}P_1\to (.)Q_1,\\ P_2\to (.)Q_2,\\ \cdots\cdots\cdots\cdots\\ P_r\to (.)Q_r, \end{cases}$

в алфавите $A$ называется схемой (или записью) нормального алгоритма в $A$ . (Запись точки в скобках означает, что она может стоять в этом месте, а может отсутствовать.) Данная схема определяет (детерминирует) алгоритм преобразования слов, называемый нормальным алгоритмом Маркова. Дадим его точное определение.

Определение 34.3. Нормальным алгоритмом (Маркова) в алфавите $A$ называется следующее правило построения последовательности $V_i$ слов в алфавите $A$ , исходя из данного слова ${V}$ в этом алфавите. В качестве начального слова $V_0$ последовательности берется слово ${V}$ . Пусть для некоторого $i\geqslant 0$ слово $V_i$ построено и процесс построения рассматриваемой последовательности еще не завершился. Если при этом в схеме нормального алгоритма нет формул, левые части которых входили бы в $V_i$ , то $V_{i+1}$ полагают Равным $V_i$ , и процесс построения последовательности считается завершившимся. Если же в схеме имеются формулы с левыми частями, входящими в $V_i$ , то в качестве $V_{i+1}$ берется результат марковской подстановки правой части первой из таких формул вместо первого вхождения ее левой части в слово $V_i$ ; процесс построения последовательности считается завершившимся, если на данном шаге была применена формула заключительной подстановки) и продолжающимся — в противном случае. Если процесс построения упомянутой последовательности обрывается, то говорят, что рассматриваемый нормальный алгоритм применим к слову ${V}$ . Последний член ${W}$ последовательности называется результатом применения нормального алгоритма к слову ${V}$ . Говорят, что нормальный алгоритм перерабатывает ${V}$ и ${W}$ .

Последовательность $V_i$ будем записывать следующим образом:

$V_0 ~\Rightarrow~ V_1~ \Rightarrow~ V_2~ \Rightarrow~ \ldots~ \Rightarrow~ V_{m-1} ~\Rightarrow~ V_m$ , где $V_0=V$ и $V_m=W$ .

Мы определили понятие нормального алгоритма в алфавите $A$ . Если же алгоритм задан в некотором расширении алфавита $A$ , то говорят, что он есть нормальный алгоритм над $A$ .

Рассмотрим примеры нормальных алгоритмов.

Пример 34.4. Пусть $A=\{a,b\}$ — алфавит. Рассмотрим следующую схему нормального алгоритма в $A\colon$

$\begin{cases}a\to\,.\,\Lambda,\\ b\to b.\end{cases}$

Нетрудно понять, как работает определяемый этой схемой нормальный алгоритм. Всякое слово ${V}$ в алфавите $A$ , содержащее хотя бы одно вхождение буквы $a$ , он перерабатывает в слово, получающееся из ${V}$ вычеркиванием в нем самого левого (первого) вхождения буквы а. Пустое слово он перерабатывает в пустое. (Алгоритм не применим к таким словам, которые содержат только букву $b$ .) Например,

$aabab~ \Rightarrow~ abab,\quad ab~ \Rightarrow~ b,\quad aa~ \Rightarrow~a,\quad bbab~\Rightarrow~bbb,\quad baba~ \Rightarrow~ bba.$

Пример 34.5. Пусть $A=\{a_0,a_1,\ldots,a_n\}$ — алфавит. Рассмотрим схему

$\begin{cases}a_0\to \Lambda,\\ a_1\to \Lambda,\\ \cdots\cdots\cdots\cdots\\ a_n\to \Lambda,\\ \Lambda\to\,.\,\Lambda. \end{cases}$

Она определяет нормальный алгоритм, перерабатывающий всякое слово (в алфавите $A$ ) в пустое слово. Например,

$\begin{gathered}a_1a_2a_1a_3a_0~ \Rightarrow~ a_1a_2a_1a_3~ \Rightarrow~ a_2a_1a_3~ \Rightarrow~ a_2a_3~ \Rightarrow~ a_3~ \Rightarrow~ \Lambda;\\[2pt] a_0a_2a_2a_1a_3a_1~ \Rightarrow~ a_2a_2a_1a_3a_1~ \Rightarrow~ a_2a_2a_3a_1~ \Rightarrow~ a_2a_2a_3~ \Rightarrow~ a_2a_3~ \Rightarrow~ a_3~ \Rightarrow~\Lambda. \end{gathered}$

Нормально вычислимые функции и принцип нормализации Маркова

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

Пример 34.6. В алфавите $A=\{A\}$ схема $\Lambda\to.1$ определяет нормальный алгоритм, который к каждому слову в алфавите $A=\{A\}$ (все такие слова суть следующие: $\Lambda,\,1,\,11,\,111,\,1111,\,11111$ и т.д.) приписывает слева 1. Следовательно, алгоритм реализует (вычисляет) функцию $f(x)=x+1$ .

Пример34.7. Дана функция $\varphi_3(11\ldots1)= \begin{cases} 1,&\text{if}~n~ \text{delitsya na}~3,\\ \Lambda,&\text{if}~n~\text{ne delitsya na}~3,\end{cases}$ где $n$ — число единиц в слове $11\ldots1$ . Рассмотрим нормальный алгоритм в алфавите $A=\{1\}$ со следующей схемой:

$\begin{cases}111\to \Lambda,\\ 11\to.\Lambda,\\ 1\to.\Lambda,\\ \Lambda\to.1. \end{cases}$

Этот алгоритм работает по такому принципу: пока число букв 1 а слове не меньше 3, алгоритм последовательно стирает по три буквы. Если число букв меньше 3, но больше 0, то оставшиеся буквы 1 или 11 стираются заключительно; если слово пусто, оно заключительно переводится в слово 1. Например:

$\begin{aligned}&1111111~ \Rightarrow~ 1111~ \Rightarrow~ 1~ \Rightarrow~ \Lambda;\\ &111111111~ \Rightarrow~ 111111~ \Rightarrow~ 111~ \Rightarrow~ \Lambda~ \Rightarrow~1. \end{aligned}$

Таким образом, рассмотренный алгоритм реализует (или вычисляет) данную функцию.

Сформулируем теперь точное определение такой вычислимости функций.

Определение 34.8. Функция $f$ , заданная на некотором множестве слов алфавита $A$ , называется нормально вычислимой, если найдется такое расширение $B$ данного алфавита $(A\subseteq B)$ и такой нормальный алгоритм в $B$ , что каждое слово ${V}$ (в алфавите $A$ ) из области определения функции $f$ этот алгоритм перерабатывает в слово $f(V)$ .

Таким образом, нормальные алгоритмы примеров 34.6 и 34.7 показывают, что функции $f(x)=x+1$ и $\varphi_3(x)$ нормально вычислимы. Причем соответствующие нормальные алгоритмы удалось построить в том же самом алфавите $A$ , на словах которого были заданы рассматривавшиеся функции, т.е. расширять алфавит не потребовалось $(B=A)$ . Следующий пример демонстрирует нормальный алгоритм в расширенном алфавите, вычисляющий данную функцию.

Пример 34.9. Построим нормальный алгоритм для вычисления Функции $f(x)=x+1$ не в одноичной системе (как сделано в примере 34.6), а в десятичной. В качестве алфавита возьмем перечень арабских цифр $A=\{0,1,2,3,4,5,6,7,8,9\}$ , а нормальный алгоритм будем строить в его расширении $B=A\cup\{a,b\}$ . Вот схема этого нормального алгоритма (читается по столбцам):

$\begin{array}{ccc}0b\to.1&\quad a0\to0a&\quad \\ 1b\to.2 &\quad a1\to1a&\quad 1a\to1b\\ 2b\to.3 &\quad a2\to2a&\quad 2a\to2b\\ 3b\to.4 &\quad a3\to3a&\quad 3a\to3b\\ 4b\to.5 &\quad a4\to4a&\quad 4a\to4b\\ 5b\to.6 &\quad a5\to5a&\quad 5a\to5b\\ 6b\to.7 &\quad a6\to6a&\quad 6a\to6b\\ 7b\to.8 &\quad a7\to7a&\quad 7a\to7b\\ 8b\to.9 &\quad a8\to8a&\quad 8a\to8b\\ 9b\to b0 &\quad a9\to9a&\quad 9a\to9b\\ b\to.1 &\quad 0a\to0b&\quad \Lambda\to a \end{array}$

Попытаемся применить алгоритм к пустому слову $\Lambda$ . Нетрудно понять, что на каждом шаге должна будет применяться самая последняя формула данной схемы. Получается бесконечный процесс:

$\Lambda~ \Rightarrow~ a~ \Rightarrow~ aa~\Rightarrow~ aaa~\Rightarrow~ aaaa~\Rightarrow~\ldots$

Это означает, что к пустому слову данный алгоритм не применим.

Если применить теперь алгоритм к слову 499, получим следующую последовательность слов: $499 \Rightarrow a499$ (применена последняя формула) $\Rightarrow 4a99$ (формула из середины второго столбца) $\Rightarrow 49a9 \Rightarrow 499b$ (дважды применена формула из конца второго столбца) $\Rightarrow 499b$ (предпоследняя формула) $\Rightarrow 49b0 \Rightarrow 4b00$ (дважды применена предпоследняя формула первого столбца) $\Rightarrow 500$ (применена формула из середины первого столбца).

Таким образом, слово 499 перерабатывается данным нормальным алгоритмом в слово 500. Предлагается проверить, что $328 \Rightarrow 329,~ 789 \Rightarrow 790$ .

В рассмотренном примере нормальный алгоритм построен в алфавите $B$ , являющемся существенным расширением алфавита $a$ (т.е. $A\subseteq B$ и $A\ne B$ ), но данный алгоритм слова в алфавите $a$ перерабатывает снова в слова в алфавите $A$ . В таком случае говорят, что алгоритм задан над алфавитом $A$ .

Создатель теории нормальных алгоритмов советский математик А. А. Марков выдвинул гипотезу, получившую название "Принцип нормализации Маркова". Согласно этому принципу, для нахождения значений функции, заданной в некотором алфавите, тогда и только тогда существует какой-нибудь алгоритм, когда функция нормально вычислима.

Сформулированный принцип, как и тезисы Тьюринга и Чёрча, носит внематематический характер и не может быть строго доказан. Он выдвинут на основании математического и практического опыта.

Все, что в предыдущих параграфах было сказано о тезисах Тьюринга и Чёрча, можно с полным правом отнести к принципу нормализации Маркова. Косвенным подтверждением этого принципа служат теоремы следующего пункта, устанавливающие эквивалентность и этой теории алгоритмов теориям машин Тьюринга и рекурсивных функций.

Совпадение класса всех нормально вычислимых функций с классом всех функций, вычислимых по Тьюрингу

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

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

Доказательство

Пусть машина Тьюринга с внешним алфавитом $A=\{a_0,a_1, \ldots,a_m\}$ и алфавитом внутренних состояний $Q=\{q_0,q_1,\ldots, q_n\}$ вычисляет некоторую функцию $f$ , заданную и принимающую значения в множестве слов алфавита $A$ (словарную функцию на $A$ ). Попытаемся представить программу этой машины Тьюринга в виде схемы некоторого нормального алгоритма. Для этого нужно каждую команду машины Тьюринга $q_{\alpha}a_i\to q_{\beta}a_jX$ представить в виде совокупности марковских подстановок. Конфигурации, возникающие в машине Тьюринга в процессе ее работы, представляют собой слова в алфавите $A\cup Q$ . Эти слова имеют вид: $a_{i_1}\ldots a_{i_k}q_{\alpha} a_{i_{k+1}}\ldots a_{i}$ . Нам понадобится различать начало слова и его конец (или его левый и правый концы). Для этого к алфавиту $A\cup Q$ добавим еще два символа (не входящие ни в $A$ , ни в $Q$ ): $A\cup Q\cup \{u,v\}$ . Эти символы будем ставить соответственно в начало и конец каждого машинного слова $w\colon\, uwv$ .

Пусть на данном шаге работы машины Тьюринга к машинному слову ${w}$ предстоит применить команду $q_{\alpha}a_i\to q_{\beta}a_jX$ . Это означает, что машинное слово ${w}$ (а вместе с ним и слово $uwv$ ) содержит подслово $q_{\alpha} a_i$ . Посмотрим, какой совокупностью марковских подстановок можно заменить данную команду в каждом из следующих трех случаев:

а) $X=C$ , т.е. команда имеет вид: $q_{\alpha}a_i\to q_{\beta}a_j$ . Ясно, что в этом случае следующее слово получается из слова $uwv$ с помощью подстановки $q_{\alpha}a_i\to q_{\beta}a_j$ , которую мы и будем считать соответствующей команде $q_{\alpha}a_i\to q_{\beta}a_j$ ;

б) $X=L$ , т.е. команда имеет вид: $q_{\alpha}a_i\to q_{\beta}a_jL$ . Нетрудно понять, что в этом случае для получения из слова $uwv$ следующего слова надо к слову $uwv$ применить ту подстановку из совокупности

$\begin{aligned}&a_0q_{\alpha}a_i~\to~ q_{\beta}a_0a_j\,;\\ &a_1q_{\alpha}a_i~\to~ q_{\beta}a_1a_j\,;\\ &\quad\vdots\\ &a_mq_{\alpha}a_i~\to~ q_{\beta}a_ma_j\,;\\ &uq_{\alpha}a_i~\to~ uq_{\beta}a_0a_j\,,\end{aligned}$

которая применима к слову $uwv$ . В частности, последняя подстановка применима только тогда, когда $q_{\alpha}$ — самая левая буква в слове ${w}$ , т.е. когда надо пристраивать ячейку слева;

в) $X=\Pi$ , т.е. команда имеет вид: $q_{\alpha}a_i\to q_{\beta}a_j\Pi$ . В этом случае аналогично, чтобы получить из слова $uwv$ следующее слово, нужно к слову $uwv$ применить ту из подстановок совокупности

$\begin{aligned}&q_{\alpha}a_ia_0~ \to~ a_jq_{\beta}a_0\,;\\ &q_{\alpha}a_ia_1~ \to~ a_jq_{\beta}a_1\,;\\ &\quad\vdots\\ &q_{\alpha}a_ia_m~ \to~ a_jq_{\beta}a_m\,;\\ &q_{\alpha}a_iv~ \to~ a_jq_{\beta}a_0v\,. \end{aligned}$

которая применима к слову $uwv$ .

Поскольку слово $q_{\alpha}a_i$ входит в слово ${w}$ только один раз, то к слову $uwv$ применима только одна из подстановок, перечисленных в пунктах б,в. Поэтому порядки следования подстановок в этих пунктах безразличны, важны лишь их совокупности.

Заменим каждую команду из программы машины Тьюринга указанным способом совокупностью марковских подстановок. Мы получим схему некоторого нормального алгоритма. Теперь ясно, что применить к слову ${w}$ данную машину Тьюринга — это все равно, что применить к слову uwv построенный нормальный алгоритм. Другими словами, действие машины Тьюринга равнозначно действию подходящего нормального алгоритма. Это и означает, что всякая функция, вычислимая по Тьюрингу, нормально вычислима.

Верно и обратное утверждение.

Теорема 34.11. Всякая нормально вычислимая функция вычислима по Тьюрингу.

Эквивалентность различных теорий алгоритмов

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

Теорема 34.12. Следующие классы функций {заданных на натуральных числах и принимающих натуральные значения) совпадают:
а) класс всех функций, вычислимых по Тьюрингу;
б) класс всех частично рекурсивных функций;
в) класс всех нормально вычислимых функций.

Полезно уяснить смысл и значение этого важного результата. В разное время в разных странах ученые независимо друг от друга, изучая интуитивное понятие алгоритма и алгоритмической вычислимости, создали теории, описывающие данное понятие, которые оказались равносильными. Этот факт служит мощным косвенным подтверждением адекватности этих теорий опыту вычислений, справедливости каждого из тезисов Тьюринга, Чёрча и Маркова. В самом деле, ведь если бы один из этих классов оказался шире какого-либо другого класса, то соответствующий тезис Тьюринга, Чёрча или Маркова был бы опровергнут. Например, если бы класс нормально вычислимых функций оказался шире класса рекурсивных функций, то существовала бы нормально вычислимая, но не рекурсивная функция. В силу ее нормальной вычислимости она была бы алгоритмически вычислима в интуитивном понимании алгоритма, и предположение о ее нерекурсивности опровергало бы тезис Чёрча. Но классы Тьюринга, Чёрча и Маркова совпадают, и таких функций не существует. Это и служит еще одним косвенным подтверждением тезисов Тьюринга, Маркова и Чёрча.

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

Математический форум (помощь с решением задач, обсуждение вопросов по математике).

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

Список статей » Список форумов

Часовой пояс: UTC + 3 часа [ Летнее время ]