Машины Тьюринга

Ассоциативные исчисления

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

Напомним, что алфавитом называют конечное множество, элементы его называют символами, или буквами, а конечные последовательности букв словами.

Пусть фиксирован алфавит A. Будем называть правилом произвольную запись вида P -> Q, где P и Q слова этого алфавита (мы считаем, что сама стрелка не является буквой алфавита). Будем называть ассоциативным исчислением конечный набор правил. (Порядок правил в наборе не играет роли.) Каждое правило рассматривается как правило преобразования слов. Именно, мы говорим, что к слову X можно применить правило P -> Q, если в слове X есть участок из подряд идущих букв (подслово), совпадающий с P. В этом случае его разрешается заменить на Q. Таких участков может быть несколько, так что к одному и тому же слову можно применить одно и то же правило несколькими разными способами. Кроме того, в исчислении может быть несколько правил, применимых к данному слову, и тогда можно применять любое из них. После этого можно снова применить то же самое или другое правило исчисления, и так далее.

Повторим это определение более формально. Говорят, что слово X можно преобразовать в слово Y по правилам исчисления I, если существует конечная последовательность слов

X = Z0, Z1, Z2, ..., Zk-1, Zk = Y,

в которой каждое слово Zi получается из предыдущего слова Zi-1 по одному из правил исчисления I, то есть в I существует такое правило P -> Q, что Zi-1=RPS и Zi=RQS для некоторых слов R и S.

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

Теорема 60. Для всякого исчисления это множество перечислимо. Существует исчисление, для которого это множество неразрешимо.

Мы докажем эту теорему в следующем разделе. Первая ее часть доказывается легко: множество всех последовательностей Z0 -> Z1 -> ... -> Zk, согласованных с правилами исчисления, разрешимо и потому перечислимо. Если от каждой из них оставить только начало и конец, получится перечисление искомого множества.

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

Моделирование машин Тьюринга

Теорема 61. Пусть M машина Тьюринга, алфавит которой включает 0 и 1. Тогда можно построить ассоциативное исчисление I с таким свойством: двоичное слово Y является результатом работы машины на двоичном слове X тогда и только тогда, когда слово [ X ] по правилам исчисления I можно преобразовать в слово Y.

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

  78. Покажите, что если без дополнительных символов [ и ] утверждение теоремы не будет верным. (Указание: если слово Y можно получить из слова X по правилам исчисления, то слово PYQ можно получить из слова PXQ по правилам исчисления.)

Идея моделирования состоит в следующем. Будем кодировать конфигурацию машины Тьюринга (содержимое ленты, положение головки, состояние) в виде слова. Тогда переход от конфигурации к следующей по правилам машины Тьюринга соответствует применению правила ассоциативного исчисления.

Конечно, для этого надо правильно выбрать кодирование. Мы будем делать это так: конфигурация

кодируется словом [ P s Q ]. Таким образом, алфавит нашего исчисления будет включать все буквы алфавита машины Тьюринга, включая пробел (который мы изображаем как " _ "), и все ее состояния (мы считаем, что множество состояний не пересекается с алфавитом), а также специальные символы [ и ]. Заметим, что кодирование не однозначно за счет того, что слово P может начинаться с пробела, а слово Q им кончаться. Например, если a, b и c буквы алфавита, а s состояние, то слово [absc] соответствует состоянию s, ленте ...abc... и головке напротив c ; слова [_absc] и [absc_] соответствуют той же конфигурации. Другие примеры кодирования конфигураций: слово [sabc] соответствует состоянию s, ленте ...abc... и головке напротив a, слово [abcs] ленте ...abc... c головкой справа от c, а слово [s] соответствует пустой ленте.

Теперь надо написать правила нашего исчисления. Мы хотим, чтобы к коду любой конфигурации было применимо ровно одно правило и чтобы получающееся при его применении слово было кодом следующей конфигурации. Это можно сделать, построчно переводя таблицу переходов машины Тьюринга на язык правил. Пусть, например, в таблице есть инструкция " находясь в состоянии s и читая букву x, перейти в состояние s', напечатать букву x' и остаться на месте". Тогда мы включаем в наше исчисление правило

s x -> s'x'.

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

для всех букв $$\alpha$$ алфавита машины Тьюринга.

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

s x -> x's'.

Но надо еще позаботиться о ситуации, когда слова P или Q пусты. Для этого нужны такие правила:

Особые случаи, рассмотренные в этой таблице это случай пробела под головкой и пустого слова Q, а также сдвига налево при пустом слове P.

Применение этих правил шаг за шагом моделирует процесс вычисления машины Тьюринга. Но надо еще " подготовить вход" и " очистить выход". После завершения работы машина оказывается в некотором заключительном состоянии s, и код конфигурации имеет вид [PsQ]. А нам надо получить слово, являющееся результатом работы машины. То есть, по нашим правилам определения результата, надо удалить P и открывающуюся скобку, а также в Q выделить максимальное начало из нулей и единиц, и все последующее удалить. Вот как это делается. Введем дополнительный символ $$\triangleleft$$, правила s -> $$\triangleleft$$ для каждого заключительного состояния s, правила $$\alpha$$ $$\triangleleft\to\triangleleft$$ для всех букв $$\alpha$$ и правило $$[\triangleleft\to\triangleright$$. Тогда символ $$\triangleleft$$ появится на месте заключительного состояния, съест все слева от себя, а в конце встретит скобку и превратится в новый символ $$\triangleright$$. Для этого символа мы используем правила $$\triangleright\,0 \to 0\,\triangleright$$, $$\triangleright\,1\to 1\,\triangleright$$ и $$\triangleright\,\alpha\to \triangledown\alpha$$ (последнее правило для всех $$\alpha$$ из алфавита машины, кроме 0 и 1, а также для $$\alpha =]$$ ). Символ $$\triangleright$$ пропускает результат налево от себя и превращается в символ $$\triangledown$$. А этот символ уничтожает все справа от себя и затем самоуничтожается в паре с закрывающейся скобкой; правила таковы: $$\triangledown\alpha\hm\to\triangledown$$ для всех символов $$\alpha$$ из алфавита машины, а также $$\triangledown$$ $$]\to \Lambda$$ ( $$\Lambda$$ обозначает пустое слово).

Эти правила позволяют выделить результат работы машины из кода заключительной конфигурации. Теперь уже можно сказать, что машина на входе X дает результат Y тогда и только тогда, когда по этим правилам из слова [s0 X] можно получить слово Y. Единственное различие с формулировкой теоремы состоит в том, что там нет символа s0, но это исправить легко: добавим еще один символ [', правило [-> ['s0, и во всех остальных правилах заменим [ на ['.

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

Теперь уже можно построить обещанное неразрешимое ассоциативное исчисление.

Возьмем перечислимое неразрешимое множество K. Возьмем машину Тьюринга, которая на входах из K останавливается и дает пустое слово, а на входах не из K не останавливается (полухарактеристическая функция перечислимого множества, напомним, вычислима, и потому вычислима на машине Тьюринга по тезису Тьюринга).

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

Двусторонние исчисления

Оказывается, что рассуждение предыдущего раздела можно немного усилить. Назовем ассоциативное исчисление (е набор правил) двусторонним, если оно вместе с каждым правилом X -> Y содержит и симметричное правило Y -> X.

Теорема 62. Существует двустороннее исчисление, для которого нет алгоритма, выясняющего, можно ли получить одно слово из другого по правилам этого исчисления.

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

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

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

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

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

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

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

Полугруппы, образующие и соотношения

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

Полугруппой называется произвольное непустое множество G с ассоциативной операцией, записываемой как умножение, причем существует единичный элемент 1, для которого 1* x =x * 1=x для всех $$x \in G$$. (Полугруппы без единичного элемента нам не потребуются.) Пусть G некоторая полугруппа. Говорят, что множество $$A \subset G$$ является множеством образующих для полугруппы G, если всякий элемент полугруппы может быть получен как произведение образующих (возможно, пустое такое произведение считается равным 1 ). Полугруппа называется конечно порожденной, если она имеет конечное множество образующих.

Пусть A={a1,...,an} алфавит. Тогда множество всех слов в алфавите A образует полугруппу. Умножение в ней это конкатенация слов, то есть приписывание одного к другому. Единичный элемент пустое слово. Очевидно, a1,...,an являются образующими этой полугруппы. (Точнее следовало бы говорить об однобуквенных словах как образующих.) Эта полугруппа называется свободной полугруппой с образующими a1,...,an. Будем обозначать ее F(a1,...,an).

Пусть G произвольная полугруппа, и g1,...,gn любые ее элементы. Тогда существует единственный гомоморфизм h полугруппы F(a1,...,an) в полугруппу G, для которого h(ai)=gi. ( Гомоморфизмом полугрупп называют отображение, при котором образ произведения равен произведению образов и единица переходит в единицу.) Он переводит слово из символов ai в произведение соответствующих элементов gi ; образом пустого слова является единичный элемент. Очевидно, образ этого гомоморфизма совпадает со всей полугруппой G тогда и только тогда, когда элементы g1,...,gn являются образующими группы G.

Соотношениями мы будем называть равенства вида X=Y, где X и Y элементы свободной полугруппы F(a1,...,an), то есть слова в алфавите A. Говорят, что соотношение X=Y выполнено в полугруппе G с выделенными элементами g1,...,gn, если образы слов X и Y при описанном гомоморфизме, то есть произведения соответствующих элементов gi, равны. Пусть имеется некоторый набор соотношений X1=Y1,...,Xk=Yk. Будем рассматривать различные полугруппы G с выделенными n элементами, в которых выполнены все эти соотношения, и в которых выделенные элементы являются образующими. (Например, полугруппа из единственного единичного элемента также входит в их число.) Среди таких полугрупп, как мы сейчас увидим, есть " максимальная", в которой выполнено меньше всего соотношений.

Введем на словах алфавита A отношение эквивалентности, считая, что $$P \equiv Q$$, если P можно преобразовать в Q в двустороннем ассоциативном исчислении с правилами $$X_{1}\Leftrightarrow Y_{1},\dots ,X_{k}\Leftrightarrow Y_{k}$$. (Другими словами, в любом слове разрешается заменить его подслово Xi на подслово Yi и наоборот.) Очевидно, это отношение действительно будет отношением эквивалентности. Заметим, что если $$P \equiv Q$$, то $$PR \equiv QR$$ и $$RP \equiv RQ$$ для произвольного слова R (в цепочке преобразований можно дописать ко всем словам R слева или справа). Рассмотрим классы эквивалентности этого отношения. На них можно определить операцию произведения, считая произведением двух классов, содержащих слова P и Q, класс, содержащий их конкатенацию PQ. Отмеченное свойство отношения эквивалентности гарантирует корректность этого определения (класс-произведение не зависит от выбора представителей в сомножителях). Тем самым мы получаем полугруппу G, в которой единичным элементом будет класс пустого слова, а классы gi=[ai] эквивалентности однобуквенных слов будут образующими. Ее обозначают

F(a1,...,an)/(X1=Y1,...,Xk=Yk)

и называют полугруппой с образующими a1,...,ak и соотношениями X1=Y1,...,Xk=Yk. Ясно, что в полугруппе G выполнены исходные соотношения Xi=Yi. Легко понять также, что в ней нет никаких других соотношений, кроме следствий исходных:

Теорема 63. Если соотношение X=Y выполнено в полугруппе

F(a1,...,an)/(X1=Y1,...,Xk=Yk),

то оно выполнено в любой полугруппе G с выделенными элементами g1,...,gn, в которой выполнены все соотношения Xi=Yi.

В самом деле, словам X и Y соответствуют их классы эквивалентности по описанному отношению, так что из X можно получить Y по правилам двустороннего ассоциативного исчисления. Но все эти правила не меняют значение элемента в любой полугруппе, в которой выполнены соотношения Xi=Yi, и потому в любой такой полугруппе словам X и Y будет соответствовать один и тот же элемент.

  79. Рассмотрим полугруппу с двумя образующими a1 и a2 и соотношениями $$a_{1}a_{2}=\Lambda$$, $$a_{2}a_{1}=\Lambda$$. Что это за полугруппа?

  80. Рассмотрим полугруппу с двумя образующими a1 и a2 и соотношением a1a2=a2a1. Что это за полугруппа?

  81. Рассмотрим полугруппу с двумя образующими a1 и a2 и соотношениями $$a_{1}a_{1}=\Lambda$$, $$a_{2}a_{2}=\Lambda$$, a1a2=a2a1. Что это за полугруппа?

  82. Рассмотрим полугруппу с двумя образующими a1 и a2 и соотношениями $$a_{1}a_{1}=\Lambda$$, $$a_{2}a_{2}a_{2} =\Lambda$$, a1a2=a2a2a1. Что это за полугруппа?

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

Теорема 64. Существует полугруппа, с конечным числом образующих и конечным числом соотношений, в которой задача проверки равенства двух слов, составленных из образующих, алгоритмически неразрешима (нет алгоритма, который по двум словам такого вида узнавал, равны они в этой полугруппе или не равны).

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

Эта теорема была доказана в 1947 году независимо Постом и Андреем Андреевичем Марковым (младшим); вскоре после этого Петр Сергеевич Новиков усилил ее, построив пример группы (а не только полугруппы!) с конечным числом образующих и соотношений, для которой проблема равенства двух слов из образующих неразрешима.