Математическая логика - Нормальные алгоритмы Маркова

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

Алфавитом (как и прежде) называется любое непустое множество. Его элементы называются буквами, а любые последовательности букв — словами в данном алфавите. Для удобства рассуждений допускаются пустые слова (они не имеют в своем составе ни одной буквы). Пустое слово будем обозначать $\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)$ . Следующий пример демонстрирует нормальный алгоритм в расширенном алфавите, вычисляющий данную функцию.