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

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

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

Пусть фиксирован алфавит А. Будем называть прави­лом произвольную запись вида Р —У <5, где Р — слова этого алфавита (мы считаем, что сама стрелка не явля­ется буквой алфавита). Будем называть ассоциативным исчислением конечный набор правил. (Порядок правил в наборе не играет роли.) Каждое правило рассматрива­ется как правило преобразования слов. Именно, мы го­ворим, что к слову X можно применить правило Р —У <5,

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

если в слове X есть участок из подряд идущих букв (под-слово), совпадающий с Р. В этом случае его разрешается заменить на <5. Таких участков может быть несколько, так что к одному и тому же слову можно применить одно и то же правило несколькими разными способами. Кроме того, в исчислении может быть несколько правил, приме­нимых к данному слову, и тогда можно применять любое из них. После этого можно снова применить то же самое или другое правило исчисления, и так далее.

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

X    /П). У,\. У,-,.... , Уи = У,

в которой каждое слово У{ получается из предыдущего слова Х{_1 по одному из правил исчисления /, то есть в / существует такое правило Р —У <5, что У{_1 = НРБ и У{ = КС^Б для некоторых слов К ж Б.

Таким образом, каждому исчислению соответству­ет некоторое множество пар слов — множество таких пар (Х,У), что X можно преобразовать в У по прави­лам этого исчисления.

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

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

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