% исправлены опечатки 20.04.2000
\chapter{Машины~Тьюринга}\label{chapt09}
        \index{Машина!Тьюринга}%
        \glossary{Тьюринг@\Тьюринг}%
        \index{Тьюринга машина}%

\section[Зачем нужны простые вычислительные модели?]
        {Зачем нужны простые вычислительные\\модели?}\label{chapt09-1}

До сих пор нам было удобно ссылаться на программистский опыт,
говоря об алгоритмах, программах, интерпретаторах, пошаговом
выполнении \итд Это позволяло нам игнорировать детали
построения тех или иных алгоритмов под тем предлогом, что
читатель их легко восстановит (или хотя бы поверит\т всё\д таки
не каждый читатель в своей жизни писал интерпретатор паскаля на
        \index{Паскаль}%
паскале).

Но в некоторых случаях этого недостаточно. Пусть, например, мы
хотим доказать алгоритмическую неразрешимость какой\д то задачи, в
определении которой ничего не говорится о программах (в этом
разделе, например, мы докажем неразрешимость проблемы равенства
        \index{Проблема!равенства слов}%
слов в полугруппах, заданных образующими и соотношениями). Это
обычно делается так. Мы показываем, что проблема остановки
        \index{Проблема!остановки}%
сводится к этой задаче. Для этого мы моделируем работу
произвольного алгоритма в терминах рассматриваемой задачи (что
это значит, будет видно из приводимого ниже примера). При этом
нам важно, чтобы определение алгоритма было как можно проще.

Таким образом, наш план таков. Мы опишем довольно просто
определяемый класс машин (его можно выбирать по\д разному, мы
будем использовать так называемые машины~Тьюринга), затем
        \index{Машина!Тьюринга}%
        \index{Тьюринга машина}
объявим, что всякая вычислимая функция может быть вычислена на
такой машине, а затем покажем, что вопрос об остановке машины~Тьюринга
можно свести к вопросу о равенстве слов в полугруппе.

Другая причина, по которой важны простые вычислительные модели
(таких моделей много\т разные виды машин~Тьюринга, адресные
машины \итп), связана с теорией сложности вычислений, когда
нас начинает интересовать время выполнения
программ. Но этот вопрос выходит за рамки классической теории
алгоритмов.

\section{Машины~Тьюринга: определение}\label{chapt09-2}
        \index{Машина!Тьюринга}%
        \index{Тьюринга машина}

\emph{Машина~Тьюринга} имеет бесконечную в обе стороны \emph{ленту},
разделённую на квадратики (\emph{ячейки}). В каждой ячейке может быть
записан некоторый символ из фиксированного (для данной машины)
конечного множества, называемого \emph{алфавитом} данной машины.
        \index{Алфавит}%
Один из символов алфавита выделен и называется \лк пробелом\пк\т
        \index{Пробела символ}%
предполагается, что изначально вся лента пуста, то есть
заполнена пробелами.

Машина~Тьюринга может менять содержимое ленты с помощью
        \index{Лента}%
специальной читающей и пишущей \emph{головки}, которая движется
        \index{Головка}%
вдоль ленты. В каждый момент головка находится в одной из ячеек.
Машина~Тьюринга получает от головки информацию о том, какой
символ та видит, и в зависимости от этого (и от своего
внутреннего состояния) решает, что делать, то есть какой символ
записать в текущей ячейке и куда сдвинуться после этого (налево,
направо или остаться на месте). При этом также меняется
внутреннее состояние машины (мы предполагаем, что машина\т не
        \index{Состояние}%
считая ленты\т имеет конечную память, то есть конечное число
внутренних состояний). Ещё надо договориться, с чего мы начинаем
и когда кончаем работу.

Таким образом, чтобы задать машину~Тьюринга, надо указать
следующие объекты:
        %
\begin{itemize}
        \item
произвольное конечное множество~$A$ (\emph{алфавит}); его элементы
        \index{Алфавит}%
        \index{Символ}%
                             называются \emph{символами};
        \item
некоторый выделенный символ~$a_0\hm\in A$ (\emph{пробел}, или
        \index{Пробела символ}%
        \index{Пустой символ}%
                   \emph{пустой символ});
        \item
конечное множество~$S$, называемое множеством \emph{состояний};
        \index{Состояние}%
        \item
некоторое выделенное состояние~$s_0\hm\in S$, называемое \emph{начальным};
        \index{Начальное состояние}%
        \index{Состояние!начальное}%
        \item
\emph{таблицу переходов}, которая определяет поведение машины в зависимости
        \index{Таблица переходов}%
от состояния и текущего символа (см.~ниже);
        \item
некоторое подмножество~$F\hm\subset S$, элементы которого называются
        \index{Состояние!заключительное}%
        \index{Заключительное состояние}%
\emph{заключительными состояниями} (попав в такое состояние, машина
останавливается).
        %
\end{itemize}

Таблица переходов устроена следующим образом: для каждой
        \index{Таблица переходов}%
пары~$\langle$текущее состояние, текущий символ$\rangle$
указана тройка~$\langle$новое состояние, новый символ,
сдвиг$\rangle$. Здесь сдвиг\т одно из чисел~$-1$~(влево),
$0$~(на месте) и~$1$~(направо). Таким образом, таблица переходов
есть функция типа~$S\hm\times A \hm\to S\hm\times A \hm\times\{-1,0,1\}$,
определённая на тех парах, в которых состояние не является
заключительным.

Остаётся описать поведение машины~Тьюринга. В каждый момент
        \index{Конфигурация машины Тьюринга}%
имеется некоторая \emph{конфигурация}, складывающаяся из
содержимого ленты (формально говоря, содержимое ленты есть
произвольное отображение~$\bbZ\hm\to A$), текущей позиции
головки (некоторое целое число) и текущего состояния машины
(элемент~$S$). Преобразование конфигурации в следующую
происходит по естественным правилам: мы смотрим в таблице, что
надо делать для данного состояния и для данного символа, то есть
выясняем новое состояние машины, меняем символ на указанный и
после этого сдвигаем головку влево, вправо или оставляем на
месте. При этом, если новое состояние является одним из
заключительных, работа машины заканчивается. Остаётся
договориться, как мы подаём информацию на вход машины и что
считается результатом её работы. Будем считать, что алфавит
машины, помимо пробела, содержит символы~$0$ и~$1$ (а также,
возможно, ещё какие\д то символы). Входом и выходом машины будут
        \index{Вход машины Тьюринга}%
        \index{Результат работы}%
конечные последовательности нулей и единиц (двоичные слова).
Входное слово записывается на пустой ленте, головка машины
ставится в его первую клетку, машина приводится в начальное
состояние и запускается. Если машина останавливается,
результатом считается двоичное слово, которое можно прочесть,
начиная с позиции головки и двигаясь направо (пока не появится
символ, отличный от~$0$ и~$1$).

Таким образом, любая машина~Тьюринга задаёт некоторую частичную
функцию на двоичных словах. Все такие функции естественно
назвать \emph{вычислимыми на машинах~Тьюринга}.
        \index{Функция!вычислимая на машине Тьюринга}%
        \index{Вычислимость!на машине Тьюринга}%

\section{Машины~Тьюринга: обсуждение}\label{chapt09-3}

        \index{Тьюринга машина}%
        \index{Машина!Тьюринга}%
Разумеется, наше определение содержит много конкретных деталей,
которые можно было бы изменить. Например, лента может быть
бесконечной только в одну сторону. Можно придать машине две
ленты. Можно считать, что машина может либо написать новый
символ, либо сдвинуться, но не то и другое вместе. Можно
ограничить алфавит, считая, скажем, что в нём должно быть
ровно~$10$~символов. Можно потребовать, чтобы в конце на ленте ничего
не было, кроме результата работы (остальные клетки должны быть
пусты). Все перечисленные и многие другие изменения не меняют
класса вычислимых на машинах~Тьюринга функций. Конечно, есть и
небезобидные изменения. Например, если запретить машине
двигаться налево, то это радикально поменяет дело\т по существу
лента станет бесполезной, так как к старым записям уже нельзя
будет вернуться.

Как понять, какие изменения безобидны, а какие нет? Видимо,
тут необходим некоторый опыт практического программирования
на машинах~Тьюринга, хотя бы небольшой. После этого уже
можно представлять себе возможности машины, не выписывая
программы полностью, а руководствуясь лишь приблизительным
описанием. В качестве примера опишем
        \index{Удвоение слова}%
машину, которая удваивает входное слово (изготавливает слово~$XX$,
если на входе было слово~$X$).

Если машина видит пробел (входное слово пусто), она
кончает работу. Если нет, она запоминает текущий символ и ставит
пометку (в алфавите помимо символов~$0$ и~$1$ будут ещё их \лк
помеченные варианты\пк~$\overline 0$ и~$\overline 1$). Затем она
движется направо до пустой клетки, после чего пишет там копию
запомненного символа. Затем она движется
налево до пометки; уткнувшись в пометку, отходит назад и
запоминает следующий символ и так далее, пока не скопирует всё
слово.

Имея некоторый опыт, можно за всеми этими фразами видеть
конкретные куски программы для машины~Тьюринга. Например, слова
\лк запоминает символ и движется направо\пк\ означают, что есть
две группы состояний, одна для ситуации, когда запомнен нуль,
другая\т когда запомнена единица, и внутри каждой группы
запрограммировано движение направо до первой пустой клетки.

Имея ещё чуть больше опыта, можно понять, что в этом описании
есть ошибка\т не предусмотрен механизм остановки, когда всё
слово будет скопировано, поскольку копии символов ничем не
отличаются от символов исходного слова. Ясно и то, как ошибку
исправить\т надо в качестве копий писать специальные
символы~$\tilde 0$ и~$\tilde 1$, а на последнем этапе
все пометки удалить.

\begin{problem}
        %
Покажите, что функция \лк обращение\пк, переворачивающая
слово задом наперёд, вычислима на машине Тьюринга.
        %
\end{problem}

Другой пример неформального рассуждения: объясним,
почему можно не
использовать дополнительных символов, кроме~$0$, $1$ и пустого
        \index{Алфавит!сокращение}%
символа. Пусть есть машина с большим алфавитом из~$N$ символов.
Построим новую машину, которая будет моделировать работу старой,
но каждой клетке старой будет соответствовать блок из~$k$ клеток
новой. Размер блока~(число~$k$) будет фиксирован так, чтобы внутри
блока можно было бы закодировать нулями и единицами все символы
большого алфавита. Исходные символы~$0$, $1$ и пустой будем
кодировать как~$0$, за которым идут $(k-1)$~пустых символов, $1$,
за которым идут $(k-1)$~пустых символов, и группу из $k$~пустых
символов. Для начала надо раздвинуть буквы входного слова на
расстояние~$k$, что можно сделать без дополнительных символов
(дойдя до крайней буквы, отодвигаем её, затем дойдя до
следующей, отодвигаем её и крайнюю и так далее); надо только
понимать, что можно идентифицировать конец слова как позицию, за
которой следует более $k$~пустых символов. Ясно, что в этом
процессе мы должны хранить в памяти некоторый конечный объём
информации, так что это возможно. После этого уже можно
моделировать работу исходной машины по шагам, и для этого тоже
достаточно конечной памяти (\те конечного числа состояний),
так как нам важна только небольшая окрестность головки
моделируемой машины. Наконец, надо сжать результат обратно.

Утверждение о том, что всякая вычислимая функция вычислима на
машине~Тьюринга, называют \emph{тезисом~Тьюринга}.
        \index{Тьюринга тезис}%
        \index{Тезис Тьюринга}%
        \index{Тьюринга машина}%
        \index{Машина!Тьюринга}%
Конечно, его смысл зависит от того, что понимать под словами \лк
вычислимая функция\пк. Если понимать их в
расплывчато\д интуитивном смысле (\лк функция
вычисляется алгоритмически, то есть по чётким,
недвусмысленным, однозначным правилам\пк\ или что\д то в таком
роде), конечно, ни о каком доказательстве тезиса~Тьюринга не
может быть речи. Можно лишь говорить, что многовековая практика
человечества от~Евклида до~Кнута не встретилась с примером
алгоритма, который нельзя было бы записать как программу
машины~Тьюринга \итп Впрочем, ещё один (не слишком убедительный)
аргумент приведён~ниже.

Но если понимать слово \лк вычислимая\пк\ в тезисе~Тьюринга как
\лк вычислимая с помощью программы на паскале\пк\ и представить
        \index{Паскаль}%
себе на минуту, что синтаксис и семантика паскаль\д программ точно
определены, то тезис~Тьюринга станет уже чётким утверждением,
которое может быть истинным или ложным, и которое можно
доказывать. Конечно, такое доказательство по необходимости
должно использовать формальное описание синтаксиса и семантики
паскаля, и потому никем не проводилось, но для более простых
вычислительных моделей это действительно можно формально
доказать. Впрочем, такого рода доказательства сродни
доказательству корректности длинной программы, и потому желающих
их писать и тем более читать немного.

В заключение обсуждения приведём обещанный выше аргумент в
пользу того, что любая вычислимая функция вычислима на машине
        \index{Тьюринга тезис}%
        \index{Тезис Тьюринга}%
        \index{Тьюринга машина}%
        \index{Машина!Тьюринга}%
Тьюринга. Пусть есть функция, которую человек умеет вычислять.
При этом, он, естественно, должен использовать карандаш и
бумагу, так как количество информации, которое он может хранить
\лк в уме\пк, ограничено. Будем считать, что он пишет на
отдельных листах бумаги. Помимо текущего листа, есть стопка
бумаг справа и стопка слева; в любую из них можно положить
текущий лист, завершив с ним работу, а из другой стопки взять
следующий. У человека есть карандаш и ластик. Поскольку очень
мелкие буквы на листе неразличимы, число отчётливо различных
состояний листа конечно, так что можно считать, что в каждый
момент на листе записана одна буква из некоторого конечного
(хотя и весьма большого) алфавита. Человек тоже имеет конечную
память, так что его состояние есть элемент некоторого конечного
множества. При этом можно составить некоторую таблицу, в которой
записано, чем кончится его работа над листом с данным
содержимым, начатая в данном состоянии (что будет на листе, в
каком состоянии будет человек и из какой пачки будет взят
следующий лист). Теперь уже видно, что действия человека как раз
соответствуют работе машины~Тьюринга с большим (но конечным)
        \index{Алфавит}%
        \index{Состояние}%
алфавитом и большим (но конечным) числом внутренних состояний.

\section{Ассоциативные исчисления}\label{chapt09-4}
        \index{Ассоциативное исчисление}%
        \index{Исчисление!ассоциативное}%

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

Напомним, что \emph{алфавитом} называют конечное множество,
        \index{Алфавит}%
элементы его называют \emph{символами}, или
        \index{Символ}%
        \index{Буква}%
        \index{Слово}%
\emph{буквами}, а конечные
последовательности букв\т \emph{словами}.

Пусть фиксирован алфавит~$A$. Будем называть \emph{правилом}
        \index{Правило}%
произвольную запись вида~$P\hm\to Q$, где~$P$ и~$Q$\т слова этого
алфавита (мы считаем, что сама стрелка не является буквой
алфавита). Будем называть \emph{ассоциативным
        \index{Ассоциативное исчисление}%
        \index{Исчисление!ассоциативное}%
исчислением} конечный набор правил. (Порядок правил в наборе не
играет роли.) Каждое правило рассматривается как правило
преобразования слов. Именно, мы говорим, что к слову~$X$ можно
применить правило~$P\to Q$, если в слове~$X$ есть участок из
        \index{Подслово}%
подряд идущих букв (подслово), совпадающий с~$P$. В этом случае
его разрешается заменить на~$Q$. Таких участков может быть
несколько, так что к одному и тому же слову можно применить одно
и то же правило несколькими разными способами. Кроме того, в
исчислении может быть несколько правил, применимых к данному
слову, и тогда можно применять любое из них. После этого можно
снова применить то же самое или другое правило исчисления, и так
далее.

Повторим это определение более формально. Говорят, что
\emph{слово~$X$ можно преобразовать в слово~$Y$ по правилам
        \index{Преобразование слов}%
исчисления~$I$}, если существует конечная последовательность
слов
        $$
X = Z_0, Z_1, Z_2, \ldots, Z_{k-1}, Z_k = Y,
        $$
в которой каждое слово~$Z_i$ получается из предыдущего слова~$Z_{i-1}$
по одному из правил исчисления~$I$, то есть в~$I$ существует
такое правило~$P\hm\to Q$, что~$Z_{i-1}\hm=RPS$ и~$Z_{i}\hm=RQS$
для некоторых слов~$R$ и~$S$.

Таким образом, каждому исчислению соответствует некоторое
множество пар слов\т множество таких пар~$\langle X,Y\rangle$,
что~$X$ можно преобразовать в~$Y$ по правилам этого исчисления.

\begin{theorem}
        \label{post-markov-theorem}%
Для всякого исчисления это множество перечислимо.
        \index{Ассоциативное исчисление!неразрешимое}%
        \index{Неразрешимое ассоциативное исчисление}%
        \index{Исчисление!неразрешимое}%
Существует исчисление, для которого это множество неразрешимо.
        %
\end{theorem}

Мы докажем эту теорему в следующем разделе.
Первая её часть доказывается легко: множество всех
последовательностей~$Z_0\hm\to Z_1\hm\to\ldots\hm\to Z_k$, согласованных
с правилами исчисления, разрешимо и потому перечислимо. Если от
каждой из них оставить только начало и конец, получится
перечисление искомого множества.

Осталось построить пример неразрешимого ассоциативного
        \index{Ассоциативное исчисление!неразрешимое}%
        \index{Неразрешимое ассоциативное исчисление}%
        \index{Исчисление!неразрешимое}%
исчисления (исчисления, для которого указанное множество
неразрешимо). Для этого мы покажем, что работу любой машины
Тьюринга можно в некотором смысле моделировать с помощью
ассоциативного исчисления, а затем возьмём исчисление,
соответствующее машине с неразрешимой проблемой остановки.

\section{Моделирование машин~Тьюринга}\label{chapt09-5}
        \index{Моделирование}%

\begin{theorem}
        \label{turing-associative-simulation}%
Пусть $M$\т машина~Тьюринга, алфавит которой включает~$0$
и~$1$. Тогда можно построить ассоциативное исчисление~$I$ с
таким свойством: двоичное слово~$Y$ является результатом работы
машины на двоичном слове~$X$ тогда и только тогда, когда слово
\verb|[|$\:X\:$\verb|]| по правилам исчисления~$I$ можно
преобразовать в слово~$Y$.
        %
\end{theorem}

Напомним, что результат работы машины мы определили как
максимальный блок нулей и единиц, начиная с позиции головки.
Заметим также, что алфавит исчисления~$I$ содержит символы~$0$ и~$1$,
дополнительные символы~\verb|[|~и~\verb|]| и может содержать
другие символы.

\begin{problem}
        %
Покажите, что если без дополнительных символов~\verb|[|~и~\verb|]|
утверждение теоремы не будет верным. (Указание: если
слово~$Y$ можно получить из слова~$X$ по правилам исчисления,
то слово~$PYQ$ можно получить из слова~$PXQ$ по правилам
исчисления.)
        %
\end{problem}

\begin{proof}
        %
Идея моделирования
состоит в следующем. Будем кодировать конфигурацию машины~Тьюринга
        \index{Конфигурация машины Тьюринга}%
(со\-дер\-жи\-мое ленты, положение головки, состояние) в виде
слова. Тогда переход от конфигурации к следующей по правилам
машины~Тьюринга соответствует применению правила ассоциативного
исчисления.

Конечно, для этого надо правильно выбрать кодирование. Мы будем
делать это так: конфигурация
      $$
\epsffile{chapt09.1}
      $$
кодируется словом~\verb|[|$P$s$Q$\verb|]|. Таким образом,
алфавит нашего исчисления будет включать все буквы алфавита
машины~Тьюринга, включая пробел (который мы изображаем
как~\лк\verb|_|\пк), и все её состояния (мы считаем, что множество
состояний не пересекается с алфавитом), а также специальные
символы~\verb|[| и~\verb|]|. Заметим, что кодирование не
однозначно  за счёт того, что слово~$P$ может начинаться с
пробела, а слово~$Q$ им кончаться. Например, если \verb|a|,
\verb|b| и~\verb|c|\т буквы алфавита, а \verb|s|\т
состояние, то слово~\verb|[absc]| соответствует состоянию~\verb|s|,
ленте~\verb|...abc...| и головке напротив~\verb|c|;
слова~\verb|[_absc]| и~\verb|[absc_]| соответствуют той же
конфигурации. Другие примеры кодирования конфигураций:
слово~\verb|[sabc]| соответствует состоянию~\verb|s|,
ленте~\verb|...abc...| и
головке напротив~\verb|a|, слово~\verb|[abcs]|\т
ленте~\verb|...abc...| c головкой справа от~\verb|c|, а
слово~\verb|[s]| соответствует пустой ленте.{\looseness=1\par}

Теперь надо написать правила нашего исчисления. Мы хотим,
чтобы к коду любой конфигурации было применимо ровно одно правило
и чтобы получающееся при его применении слово было кодом следующей
конфигурации. Это можно сделать, построчно переводя таблицу
        \index{Таблица переходов}%
переходов машины~Тьюринга на язык правил. Пусть, например,
в таблице есть инструкция \лк находясь в состоянии~$s$ и читая
букву~$x$, перейти в состояние~$s'$, напечатать букву~$x'$ и
остаться на месте\пк. Тогда мы включаем в наше исчисление
правило
        $$
     sx\to s'x'.
        $$

Инструкция \лк находясь в состоянии~$s$ и читая букву~$x$,
перейти в состояние~$s'$, напечатать
букву~$x'$ и сдвинуться влево\пк\ порождает правила
        $$
     \alpha s x \to s'\alpha x'
        $$
для всех букв~$\alpha$ алфавита машины~Тьюринга.

Инструкция \лк находясь в состоянии~$s$ и читая букву~$x$,
перейти в состояние~$s'$, напечатать
букву~$x'$ и сдвинуться вправо\пк\ порождает правило
        $$
     s x \to x's'.
        $$

Но надо ещё позаботиться о ситуации, когда слова~$P$ или~$Q$
пусты. Для этого нужны такие правила:
\begin{center}
\begin{tabular}{|p{0.5\textwidth}|c|}
\hline
если в таблице есть инструкция\ldots & правило \\
\hline
& \\[-2.4ex]
\hline
   читая~$x$ в состоянии~$s$, перейти в состояние~$s'$,
   напечатать~$x'$ и сдвинуться налево
        &
\vbox to 3pt{%
     \vskip 1ex
     \hbox to 8em{\hss$ \verb|[| s  x \to \verb|[| s' \verb|_| x'$\hss}%
 \vss
}\\
\hline
   читая пробел в состоянии~$s$, перейти в состояние~$s'$,
   напечатать~$x'$ и остаться на месте
        &
\vbox to 3pt{%
     \vskip 1ex
     \hbox to 8em{\hss $s \verb|]|  \to s' x' \verb|]|$\hss}%
 \vss
}\\
\hline
   читая пробел в состоянии~$s$, перейти в состояние~$s'$,
   напечатать~$x'$ и сдвинуться налево
        &
\vbox to 7pt{%
     \vskip 1ex
 \hbox to 8em{\hss$\alpha s \verb|]|  \to s' \alpha x' \verb|]|$\hss}%
 \vskip 0.5 ex%
 \hbox to 8em{\hss\phantom{0}$\verb|[| s \verb|]|
         \to \verb|[| s' \verb|_| x' \verb|]|$\hss}%
 \vss
}\\
\hline
   читая пробел в состоянии~$s$, перейти в состояние~$s'$,
   напечатать~$x'$ и сдвинуться направо
        &
\vbox to 3pt{%
     \vskip 1ex
     \hbox to 8em {\hss $s \verb|]|  \to  x' s' \verb|]|$\hss}%
 \vss
}\\
\hline
\end{tabular}
\end{center}
        %
Особые случаи, рассмотренные в этой таблице\т это случай
пробела под головкой и пустого слова~$Q$, а также сдвига налево
при пустом слове~$P$.

Применение этих правил шаг за шагом моделирует процесс
вычисления машины~Тьюринга. Но надо ещё \лк подготовить вход\пк\
и \лк очистить выход\пк. После завершения работы
машина оказывается в некотором заключительном состоянии~$s$, и код
конфигурации имеет вид~$\verb|[|PsQ\verb|]|$. А нам надо получить
слово, являющееся результатом работы машины. То есть, по нашим
правилам определения результата, надо удалить~$P$ и открывающуюся
скобку, а также в~$Q$ выделить максимальное начало из нулей и
единиц, и всё последующее удалить. Вот как это делается.
Введём дополнительный символ~$\triangleleft$,
правила~$s\hm\to\triangleleft$ для каждого заключительного состояния~$s$,
правила~$\alpha\,\triangleleft\hm\to\triangleleft$ для всех букв~$\alpha$
и правило~$\verb|[|\triangleleft\hm\to\triangleright$.
Тогда символ~$\triangleleft$ появится на месте заключительного
состояния, съест всё слева от себя, а в конце встретит скобку
и превратится в новый символ~$\triangleright$. Для этого
символа мы используем правила~$\triangleright\,0 \hm\to 0\,\triangleright$,
$\triangleright\,1\hm\to 1\,\triangleright$ и~$\triangleright\,\alpha\hm\to
\triangledown\alpha$ (последнее правило\т для всех~$\alpha$
из алфавита машины, кроме~$0$ и~$1$, а также для~$\alpha=\verb|]|$).
Символ~$\triangleright$ пропускает результат налево от себя и
превращается в символ~$\triangledown$. А этот символ
уничтожает всё справа от себя и затем самоуничтожается в паре с
закрывающейся скобкой; правила
таковы:~$\triangledown\alpha\hm\to\triangledown$ для всех
символов~$\alpha$ из алфавита машины, а
также~$\triangledown\verb|]|\hm\to\Lambda$ ($\Lambda$~обозначает
пустое слово).{\looseness=1\par}
        %
Эти правила позволяют выделить результат работы машины из кода
заключительной конфигурации. Теперь уже можно сказать, что
машина на входе~$X$ даёт результат~$Y$ тогда и только тогда,
когда по этим правилам из слова~$\verb|[|s_0 X\verb|]|$ можно
получить слово~$Y$. Единственное различие с формулировкой
теоремы состоит в том, что там нет символа~$s_0$, но это
исправить легко: добавим ещё один символ~$\verb|[|'$,
правило~$\verb|[|\hm\to \verb|[|'s_0$, и во всех остальных правилах
заменим~$\verb|[|$ на $\verb|[|'$.

Теперь уже всё в точности соответствует формулировке теоремы,
и доказательство можно считать завершённым. (Увы, аккуратное
проведение почти очевидной идеи часто требует перечисления
многих деталей, в которых к тому же легко пропустить какой\д нибудь
случай или допустить ошибку.)
        %
\end{proof}

Теперь уже можно построить обещанное неразрешимое ассоциативное
        \index{Ассоциативное исчисление!неразрешимое}%
        \index{Неразрешимое ассоциативное исчисление}%
        \index{Исчисление!неразрешимое}%
исчисление.

Возьмём перечислимое неразрешимое множество~$K$. Возь\-мём
машину~Тьюринга, которая на входах из~$K$ останавливается и даёт
пустое слово, а на входах не из~$K$ не останавливается
(полухарактеристическая функция перечислимого множества,
        \index{Перечислимое неразрешимое множество}%
        \index{Множество!перечислимое неразрешимое}%
напомним, вычислима, и потому вычислима на машине~Тьюринга по
тезису~Тьюринга).

Построим ассоциативное исчисление, моделирующее эту машину в
только что описанном смысле. Для него нет алгоритма, который по
паре слов~$X$ и~$Y$ выясняет, можно ли преобразовать~$X$ в~$Y$.
В самом деле, если бы такой алгоритм был, то можно было бы
применить его к словам~$\verb|[|X\verb|]|$ и~$\Lambda$ (пустое
слово) и узнать, лежит ли слово~$X$ в множестве~$K$ или не
лежит.

\section{Двусторонние исчисления}\label{chapt09-6}

Оказывается, что рассуждение предыдущего раздела можно немного
        \index{Ассоциативное исчисление!двустороннее}%
        \index{Двустороннее ассоциативное исчисление}%
усилить. Назовём ассоциативное исчисление (\те набор правил)
\emph{двусторонним}, если оно вместе с каждым правилом~$X\hm\to Y$
содержит и симметричное правило~$Y\hm\to X$.

\begin{theorem}
        \label{post-markov-twoside}%
Существует двустороннее исчисление, для которого нет алгоритма,
выясняющего, можно ли получить одно слово из другого по правилам
этого исчисления.
        %
\end{theorem}

\begin{proof}
        %
Для доказательства мы воспользуемся той же конструкцией с небольшими
изменениями. Для начала правило~$\triangledown\verb|]|\hm\to\Lambda$
заменим на правило~$\triangledown\verb|]|\hm\to\star$ (мы вскоре
увидим, зачем это нужно). После этого для каждого правила добавим
обратное. Это новое исчисление~$I'$ также моделирует машину~Тьюринга:

\lemma{Лемма.} Двоичное слово~$Y$ является результатом работы машины на
двоичном слове~$X$ тогда и только тогда, когда
слово~\verb|[|$\:X\:$\verb|]| можно преобразовать в слово~$Y\star$ по
правилам исчисления~$I'$.

Доказательство леммы. Если не добавлять обратные правила, то~$I'$
ничем не отличается от ранее построенного исчисления (кроме
последнего шага, где остаётся звёздочка\т но это, очевидно,
несущественно). Поэтому нам надо лишь показать, что
если \verb|[|$\:X\:$\verb|]|~можно преобразовать в слово~$Y\star$ по
правилам исчисления~$I'$, то это можно сделать без применения
обратных правил, только с помощью прямых.

Доказывается это так. Назовём \лк активными\пк\ следующие
символы алфавита исчисления~$I'$: символ~$\verb|[|$ (который,
напомним, заменяется на первом же шаге), все состояния машины,
$\triangleright$, $\triangleleft$, $\triangledown$ и~$\star$.
Тогда в каждом правиле нашего исчисления слева и справа есть
ровно один активный символ. Следовательно, в любой
последовательности прямых и обратных правил,
соединяющей~\verb|[|$\:X\:$\verb|]| с~$Y\star$, все слова содержат
по одному активному символу.

Теперь такое наблюдение: к слову, в котором один активный
символ, применимо не более одного прямого правила. (Это легко
проверить, посмотрев все правила; причина здесь в том, что
правила моделируют работу детерминированной машины~Тьюринга, в
        \index{Машина!Тьюринга}%
        \index{Тьюринга машина}%
которой следующая конфигурация определена однозначно.) Поэтому можно
удалить все обратные правила из последовательности
преобразований~\verb|[|$\:X\:$\verb|]| в~$Y\star$.

В самом деле, рассмотрим последнее вхождение об\-рат\-но\-го
правила в последовательность преобразований. Оно не может быть
самым последним в последовательности, так как обратное правило
не порождает символ~$\star$. Значит, за ним следует применение
какого\д то прямого правила. Но одно прямое правило, которое
можно применить, уже есть\т это то, к которому было обратно наше
обратное правило. В силу единственности другого прямого правила
быть не может. Поэтому применение обратного, а за ним прямого
правила можно взаимно сократить и получить более короткую
последовательность, в которой снова найти последнее обратное
правило \итд
        %
Лемма доказана.

Из неё сразу же следует существование неразрешимых
двусторонних ассоциативных исчислений, которое и составляло
утверждение основной теоремы этого раздела.
        %
\end{proof}

\section{Полугруппы, образующие и соотношения}\label{chapt09-7}
        \index{Образующие полугруппы}%
        \index{Соотношения в полугруппе}%
        \index{Полугруппа}%

Сейчас мы объясним, как только что доказанное утверждение
о двусторонних ассоциативных исчислениях переводится на
алгебраический язык. (Ничего нового по существу при этом
не утверждается, это просто перевод.) Напомним некоторые
сведения из алгебры.

\emph{Полугруппой} называется произвольное непустое
        \index{Полугруппа}%
мно\-жест\-во~$G$ с ассоциативной операцией, записываемой как умножение,
причём существует единичный элемент~$1$, для
которого~$1\hm\times x \hm=x\hm\times 1\hm=x$ для всех~$x\hm\in G$.
(Полугруппы без единичного элемента нам не потребуются.) Пусть
$G$\т некоторая полугруппа. Говорят, что множество~$A\hm\subset
G$ является \emph{множеством образующих} для полугруппы~$G$,
        \index{Образующие полугруппы}%
если всякий элемент полугруппы может быть получен как
произведение образующих (возможно, пустое\т такое произведение
считается равным~$1$). Полугруппа называется \emph{конечно
порождённой}, если она имеет конечное множество образующих.
        \index{Конечно порождённая полугруппа}%

Пусть $A\hm=\{a_1,\dots,a_n\}$\т алфавит. Тогда множество всех
        \index{Алфавит}%
        \index{Слово}%
слов в алфавите~$A$ образует полугруппу. Умножение в ней\т это
        \index{Конкатенация}%
\emph{конкатенация} слов, то есть приписывание одного к другому.
Единичный элемент\т пустое слово. Очевидно, $a_1,\dots,a_n$~являются
        \index{Пустое слово}%
образующими этой полугруппы. (Точнее следовало бы
говорить об од\-но\-бук\-вен\-ных словах как образующих.) Эта полугруппа
называется \emph{свободной полугруппой} с
        \index{Свободная полугруппа}%
образующими~$a_1,\dots,a_n$. Будем обозначать
её~$\calF(a_1,\dots,a_n)$.

Пусть $G$\т произвольная полугруппа, и $g_1,\dots,g_n$\т
любые её элементы. Тогда существует единственный гомоморфизм~$h$
полугруппы~$\calF(a_1,\dots,a_n)$ в полугруппу~$G$, для
        \index{Гомоморфизм}%
которого~$h(a_i)\hm=g_i$. (\emph{Гомоморфизмом} полугрупп называют
отображение, при котором образ произведения равен произведению
образов и единица переходит в единицу.) Он переводит слово из
символов~$a_i$ в произведение соответствующих элементов~$g_i$; образом
пустого слова является единичный элемент. Очевидно, образ этого
гомоморфизма совпадает со всей полугруппой~$G$ тогда и только
тогда, когда элементы~$g_1,\dots,g_n$ являются образующими
группы~$G$.

\emph{Соотношениями} мы будем
называть равенства вида~$X\hm=Y$, где $X$ и~$Y$\т
        \index{Соотношения в полугруппе}%
элементы свободной полугруппы~$\calF(a_1,\dots,a_n)$, то
есть слова в алфавите~$A$.
Говорят, что соотношение~$X\hm=Y$ выполнено в полугруппе~$G$ с
выделенными элементами~$g_1,\dots,g_n$, если образы слов~$X$ и~$Y$
при описанном гомоморфизме, то есть произведения
соответствующих элементов~$g_i$, равны. Пусть имеется некоторый набор
соотношений~$X_1\hm=Y_1,\dots,X_k\hm=Y_k$. Будем рассматривать
различные полугруппы~$G$ с выделенными~$n$ элементами, в которых
выполнены все эти соотношения, и в которых выделенные элементы
являются образующими. (Например, полугруппа из единственного
единичного элемента также входит в их число.) Среди таких
полугрупп, как мы сейчас увидим, есть \лк максимальная\пк, в
которой выполнено меньше всего соотношений.

Введём на словах алфавита~$A$ отношение эквивалентности, считая,
что~$P\hm\equiv Q$, если $P$~можно преобразовать в~$Q$ в
        \index{Ассоциативное исчисление!двустороннее}%
        \index{Двустороннее ассоциативное исчисление}%
двустороннем ассоциативном исчислении с правилами
$X_1\hm\leftrightarrow Y_1,\dots,X_k\hm\leftrightarrow Y_k$. (Другими
словами, в любом слове разрешается заменить его подслово~$X_i$
на подслово~$Y_i$ и наоборот.) Очевидно, это отношение
действительно будет
отношением эквивалентности. Заметим, что если~$P\equiv Q$,
то~$PR\hm\equiv QR$ и~$RP\hm\equiv RQ$ для произвольного слова~$R$ (в
цепочке преобразований можно дописать ко всем словам~$R$ слева
или справа). Рассмотрим классы эквивалентности этого
отношения. На них можно определить операцию произведения, считая
произведением двух классов, содержащих слова~$P$ и~$Q$, класс,
содержащий их конкатенацию~$PQ$. Отмеченное свойство отношения
эквивалентности гарантирует корректность этого определения
(класс\д произведение не зависит от выбора представителей в
сомножителях). Тем самым мы получаем полугруппу~$G$, в которой
единичным элементом будет класс пустого слова, а классы~$g_i\hm=[a_i]$
эквивалентности
од\-но\-бук\-вен\-ных слов будут образующими. Её обозначают
        $$
\calF(a_1,\dots,a_n)/(X_1=Y_1,\dots,X_k=Y_k)
        $$
и называют \emph{полугруппой с
образующими~$a_1,\dots,a_k$ и
соотношениями~$X_1\hm=Y_1,\dots,X_k\hm=Y_k$}.
        \index{Образующие полугруппы}%
        \index{Соотношения в полугруппе}%
        \index{Полугруппа}%
Ясно, что в полугруппе~$G$
выполнены исходные соотношения~$X_i\hm=Y_i$. Легко понять также, что
в ней нет никаких других соотношений, кроме следствий исходных:

\begin{theorem}
        \label{semigroup-finitely-presented}
Если соотношение~$X=Y$ выполнено в полугруппе
        $$
\calF(a_1,\dots,a_n)/(X_1=Y_1,\dots,X_k=Y_k),
        $$
то оно выполнено в любой полугруппе~$G$ с выделенными
элементами~$g_1,\dots,g_n$, в которой выполнены
все соотношения~$X_i\hm=Y_i$.
        %
\end{theorem}

\begin{proof}
        %
В самом деле, словам~$X$ и~$Y$ соответствуют их классы
эквивалентности по описанному отношению, так что из~$X$
можно получить~$Y$ по правилам двустороннего ассоциативного
исчисления. Но все эти правила не меняют значение элемента
в любой полугруппе, в которой выполнены соотношения~$X_i\hm=Y_i$,
и потому в любой такой полугруппе словам~$X$ и~$Y$ будет
соответствовать один и тот же элемент.
        %
\end{proof}

\begin{problem}
        %
Рассмотрим полугруппу с двумя образующими~$a_1$ и~$a_2$ и
соотношениями~$a_1a_2\hm=\Lambda$,~$a_2a_1\hm=\Lambda$. Что это
за полугруппа?
        %
\end{problem}

\begin{problem}
        %
Рассмотрим полугруппу с двумя образующими~$a_1$ и~$a_2$ и
соотношением~$a_1a_2\hm=a_2a_1$. Что это за полугруппа?
        %
\end{problem}

\begin{problem}
        %
Рассмотрим полугруппу с двумя образующими~$a_1$ и~$a_2$ и
соотношениями $a_1a_1\hm=\Lambda$, $a_2a_2\hm=\Lambda$,~$a_1a_2\hm=a_2a_1$.
Что это за полугруппа?
        %
\end{problem}

\begin{problem}
        %
Рассмотрим полугруппу с двумя образующими~$a_1$ и~$a_2$ и
соотношениями $a_1a_1\hm=\Lambda$,
$a_2a_2a_2 \hm=\Lambda$,~$a_1a_2\hm=a_2a_2a_1$.
Что это за полугруппа?
        %
\end{problem}

Теперь мы можем сформулировать утверждение о существовании
неразрешимых двусторонних ас\-со\-ци\-а\-тив\-ных исчислений в терминах
полугрупп.

\begin{theorem}
        \label{post-markov-twoside-2}%
Существует полугруппа, с конечным числом образующих
и конечным числом соотношений, в которой задача проверки
равенства двух слов, составленных из образующих,
алгоритмически неразрешима (нет алгоритма, который по
двум словам такого вида узнавал, равны они в этой полугруппе
или не равны).
        %
\end{theorem}

\begin{proof}
        %
Согласно определению,
равенство двух слов, составленных из образующих, означает
возможность преобразовать одно из них в другое по правилам
двустороннего исчисления, так что эта теорема представляет
собой переформулировку
теоремы~\ref{post-markov-twoside}~(с.~\pageref{post-markov-twoside})
        %
\end{proof}

\begin{historyremark}
        %
Эта теорема была доказана в 1947~году независимо Постом
\glossary{Пост@\Пост}%
\glossary{Марков@\Марков}%
и Андреем Андреевичем Марковым (младшим); вскоре
\glossary{Новиков@\Новиков}
после этого Пётр Сергеевич Новиков усилил её, построив пример
группы (а не только полугруппы!) с конечным числом образующих и
соотношений, для которой проблема равенства двух слов из
образующих неразрешима.
        %
\end{historyremark}
