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

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

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

<] Для доказательства мы воспользуемся той же кон­струкцией с небольшими изменениями. Для начала пра­вило У] —5-А заменим на правило У] —5- * (мы вскоре увидим, зачем это нужно). После этого для каждого пра­вила добавим обратное. Это новое исчисление /' также моделирует машину Тьюринга:

Лемма. Двоичное слово У является результатом рабо­ты машины на двоичном слове X тогда и только тогда, когда слово [ X ] можно преобразовать в слово У* по правилам исчисления

Доказательство леммы. Если не добавлять обратные правила, то /' ничем не отличается от ранее построен­ного исчисления (кроме последнего шага, где остаётся звёздочка — но это, очевидно, несущественно). Поэтому нам надо лишь показать, что если [А] можно преобразо­вать в слово У* по правилам исчисления /', то это можно сделать без применения обратных правил, только с помо­щью прямых.

Доказывается это так. Назовём «активными» следую­щие символы алфавита исчисления символ [ (который, напомним, заменяется на первом же шаге), все состояния машины, >, <з, V и *. Тогда в каждом правиле нашего ис­числения слева и справа есть ровно один активный сим­вол. Следовательно, в любой последовательности прямых и обратных правил, соединяющей [ X ] с У*, все слова содержат по одному активному символу.

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

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

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