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

Теорема 61. Пусть М — машина Тьюринга, алфавит которой включает 0 и 1. Тогда можно построить ассоциа­тивное исчисление / с таким свойством: двоичное слово У является результатом работы машины на двоичном сло­ве X тогда и только тогда, когда слово 1X2 по правилам исчисления / можно преобразовать в слово У.

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

77. Покажите, что если без дополнительных символов С и ] утверждение теоремы не будет верным. (Указание: если сло­во У можно получить из слова X по правилам исчисления, то слово РУф можно получить из слова РХС£ по правилам исчисления.)

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

Конечно, для этого надо правильно выбрать кодиро­вание. Мы будем делать это так: конфигурация кодируется словом \iPsQ2 ■ Таким образом, алфавит на­шего исчисления будет включать все буквы алфавита машины Тьюринга, включая пробел (который мы изо­бражаем как «_»), и все её состояния (мы считаем, что множество состояний не пересекается с алфавитом), а также специальные символы [ и ]. Заметим, что ко­дирование не однозначно за счёт того, что слово Р может начинаться с пробела, а слово <5 им кончаться.

Например, если a, b и с — буквы алфавита, as — со­стояние, то слово [absc] соответствует состоянию s, ленте ...abc... и головке напротив с; слова [_absc] и [absc_] соответствуют той же конфигурации. Дру­гие примеры кодирования конфигураций: слово [sabс] соответствует состоянию s, ленте ...abc... и голов­ке напротив а, слово [abcs] — ленте . . . abc... с го­ловкой справа от с, а слово [s] соответствует пустой ленте.

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

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

asx —5- s'ах'

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

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

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

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

[гл. 9]

если в таблице есть инструк­ция ...

правило

читая х в состоянии в, пе­рейти в состояние в1, напе­чатать х' и сдвинуться на­лево

\_8Х —5- _х'

читая пробел в состоянии в, перейти в состояние в', напе­чатать х' и остаться на ме­сте

в] -Л в'х']

читая пробел в состоянии в, перейти в состояние в', напе­чатать х' и сдвинуться нале­во

см] —5- в1 ах'1 Ы ->• 18'_х'1

читая пробел в состоянии в, перейти в состояние в', на­печатать х' и сдвинуться на­право

в] -Л х'в']

Особые случаи, рассмотренные в этой таблице — это слу­чай пробела под головкой и пустого слова <5, а также сдвига налево при пустом слове Р.

Применение этих правил шаг за шагом моделирует процесс вычисления машины Тьюринга. Но надо ещё «подготовить вход» и «очистить выход». После завер­шения работы машина оказывается в некотором за­ключительном состоянии в, и код конфигурации имеет вид [Рв<5]. А нам надо получить слово, являющееся ре­зультатом работы машины. То есть, по нашим правилам определения результата, надо удалить Р и открывающу­юся скобку, а также в <5 выделить максимальное начало из нулей и единиц, и всё последующее удалить. Вот как это делается. Введём дополнительный символ <а, прави­ла в —5- <а для каждого заключительного состояния в, правила а <з —У <з для всех букв а и правило [<а —5- >. Тогда символ <а появится на месте заключительного состояния, съест всё слева от себя, а в конце встретит скобку и превратится в новый символ >. Для этого символа мы используем правила 1>0 —5- 0>, >1 —5- 1> и >а —5- У а

 (последнее правило — для всех а из алфавита машины, кроме 0 и 1, а также для а = ]). Символ > пропускает результат налево от себя и превращается в символ V. А этот символ уничтожает всё справа от себя и затем самоуничтожается в паре с закрывающейся скобкой; пра­вила таковы: У а —У V для всех символов а из алфавита машины, а также У] —5- А (А обозначает пустое сло­во).

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

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

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

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

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