Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 52

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 52)

Выводом 6 из и в системе подстановок называется цепочка а (= а, (= е ~= „. ~= 6, где каждое аз получается из а; ~ некоторой подстановкой; как и обычно, наличие выводимости обозначаем а)-6. Такое определение вывода отличается от определения в начале $ 6А„предоставляем читателю убедиться, что для любой формальной системы, где все правила — бинарные и унарные отношения, эти два определения совпадают, т. е. аг — (1 в первом смысле, если и только если я) — р во втором смысле. (Заметим, что правило заключения в логических исчислениях — тернарное отношение!) Зафиксируем множество аксиом системы и назовем слово 6 заключительным, если оно доказуемо в системе и к нему неприменима ни одна из подстановок, т.

е. если никакое его подслово не является левой частью никакой подстановки. Системе команд Хт машины Тьюринга Т нетрудно поставить в соответствие систему подстановок Зт над конфигурациями; фактически это было уже сделано при построении универсальной машины Тьюринга 5 5.2). Если в качестве аксиом выбрать слова д,а, то заключительными словами 250 в системе 5т будут слова дф(а, 6 — слова в алфавите лепты машины Т), Если же к 5т добавить подстановку о; Х, то в полученной системе 5 множество заключительных слов совпадает с множеством значений функции, вычисляемой машиной Т.

Это дает для систем подстановок теорему, обратную теореме 6.14. Теорема 6Л6. Для любого перечислимого множества М существует система подстаиовок, множество заключительных слов которой совпадает с М. П Ассоциативное исчисление, или система Туз,— это формальная система, определяемая алфавитом А и конечным множеством соотношений а~ йь каждое из которых понимается как пара подстановок а~- 6~ (левая подстановка) и 6;+и; (правая подстановка). Таким образом, ассоциативное исчисление всегда есть система подстановок; обратное, вообще говоря, неверно. При наличии таких' парных правил вывода, если а) — 6, то и 6~ — и; ввиду отмеченной ранее транзитивности выводимостн получаем, что в ассоциативном исчислении выводимость является отношением эквивалентности и разбивает множество всех слов в А на классы эквивалентности. Заключительные слова в ассоциативных исчислениях возможны, однако они соответствуют классам эквивалентности, состоящим из одного слова, и особого интереса не представляют.

Аналогично тому, как это делалось для систем подстановок, поставим в соответствие каждой машине Тьюринга Т (будем считать, что Т работает на правой полуленте) ассоциативное нсчисление 5(Т). Опишем это соответствие более подробно. Если Ат — алфавит лепты машины Т, го Аз=АтЯт)ь:., д,). Системе команд машины Т соответствует система соотношений в 5(Т) (слева — команды, справа — соотношения): о~ а — +6 а, й; о; аз — ~а, и,.; (6. 13) д,ат — и~до,Ь; а,д,а~» — +д„а,а, для всех а,ЕАт (6.14) (число соотношений, соответствующих одной команде с движением влево, равно ~1Ат~1). Теорема 6.16. В исчислении 5 (Т) слова оо,а,й и уо,а,,б эквивалентны, если и только если машина Т из конфигурации ад,аА) за конечное число тактов переходит в конфигурацию уо,аеб.

Однако половина теоремы («если») непосредственно следует из доказательства теоремы 6.16. Вторая половина 251 («только еслибы) может показаться несколько неожиданной: ведь в 5(Т) допускаются подстановки в обе стороны, а в Т вЂ” в одну и, следовательно, возможности 5(Т) выглядят более сильными. Тем ие менее покажем, что если существует вывод ач,аф'„— уд,а«б, то машина Т из конфигурации ад;аф переходит в конфигурацию уд,а„б. Рассмотрим этот вывод, т. е. цепочку ад;а»)» — е, » — ...'„— уд,а~б.

Каж. дое слово в этой цепочке получено из предыдущего либо левой, либо праной подстановкой. Кроме того, символ д в каждом слове — единственный. Последнее слово не может быть получено правой подстановкой, так как символ д, отсутствует в левых частях команд машины Т.

Пусть ш— последнее слово в цепочке, полученное правой подстановкой: в~=оп)„а,бь Слово е~ получено из е~ ~ правой подстановкой, т. е, применением одного из соотношений (6.13), (6.14), содержащих д,а, в левой части. Но таких соотношений столько, сколько команд Т с д„а, в левой части, т.

е. ровно одно; обозначим его Е„. Слово еьы получено из в~ левой подстановкой (по условию для ш); но единственная левая подстановка, применимая к еь — это то же соотно. шеиие Е„(точнее, его левая половина). Итак, к е~ 1 при- менеио Е,. слева направо, а к результату этого применения е~ применено то же Е„справа налево.

Так как все подстановки (6.13), (6.14) содержат д, а в любом слове цепочки д единственно, то любая подстановка а; — 6; к любому слову е может быть применена единственным образом, т. е. в е найдется не более чем одно вхождение аь Отсюда е~ ~= =емч, поэтому е~ и еьм из цепочки можно выбросить и построить вывод ад,а;6» — ...

»-е~,» — е~+з' —...уд,а«б,в котором слов, полученных правой подстановкой, на единицу меньше, чем в прежнем выводе. Применяя к новому выводу те же рассуждения, из него также можно удалить слово, полученное правой подстановкои; в конечном счете будет построен вывод ад,аф- ...-+-уд,а,б, содержащий только левые подстановки, т, е, в точности воспроизводящий последовательность конфигураций машины Т. П. Теорема 6.17 (теорема Маркова — Поста). Существует ассоциативное исчисление, в котором проблема распознавания эквивалентности слов алгоритмически неразрешима.

Возьмем какую-нибудь универсальную машину Тьюринга О, которая является правильно вычисляющей, т. е. начинает с конфигураций вида о~а и заканчивает работу кои- фигурациями вида 'д,~. Для машины У проблема остановки неразрешима (иначе ввиду универсальности (7 была бы разрешима общая проблема остановки для машин Тьюринга).,Построим ассоциативное исчисление 5(У) и присоединим к нему систему соотношений вида г)ва;+ г),; получим новое исчисление 5'(У).

В этом исчислении, так же как и в 5((7), можно имитировать вычислительный процесс (7, однако благодаря новым соотношениям все заключительные конфигурации (7 в 5'(У) эквивалентны д,. Поэтому теорема 6.16 для 5'(У) имеет следующий вид: в 5(У) слова дга и д, эквивалентны, если и только если (), начав с!)га, остановится. Ввиду неразрешимости проблемы остановки длЯ (7 пРоблема эквивалентности г)га и г), также неразрешима. П Ассоциативные исчисления имеют важную алгебраическую интерпретацию. В гл, 2 говорилось о том, что всякую полугруппу можг(о получить из свободной полугруппы (т.е, просто пз множества А* всех слов в алфавите А) введением определяющих соотношений, т.е, равенств ссг=рь Замена поделана аг в слове а равным ему подсловом ))ь т.е. переход от слова сг'стнхч к слову <х'р;а", называется эквавалентным преобразованием слова и.

Слова считаются равными (нлн эквивалентными), если онн могут быть получены друг из друга цепочкой эквивалентных преобразований. Содержательно эквивалентность слов означает, что онн задают один и тот же элемент полугруппы; иначе говоря, элементами полу- группы, заданной определяющими соотношениями, являются классы эквивалентности слов, порождаемые этими соотношениями. Формально такое описание полугруппы — это просто ассоциативное исчисление с соотношениями а,«+РН эквивалентные преобразования в полугруппе — это выводы в исчислении.

В гл. 2 была сформулпровв1ш проблема эквивалентности слов в полугруппе. Теперь становится ясным, что ответ на нее — зто просто переформулнровна теоремы 6.!7, Теорема 6.!7'. Существует полугруппа, заданная определяющими соотношениями, в котдрой проблема распознавания эквивалентности (равенства) слов алгоритмически неразрешима. Г. С. Цейтин нашел очень простое ассоциативное исчисление с неразрешимой проблемой равенства — с алфавитом из пяти букв (а, Ь, с, г(, е) и семью соотношениями; ас « — ь са; ас(« — ь аа! Ьс « — ь сЬ; ЬИ» — ь г7Ь; аЬас «-ь азате; еса « — ь ае; ег7Ь -ь Ье. Теорема 6.!7' явилась исторически первым примером доказательст.

ва алгоритмической неразрешимости проблемы, ве связанной с логикой н основаниями математика, 263 Системы продукций Поста (канонические системы). Каноническая система определяется собственным алфавитом А=(аи ..., а„,) (алфавитом констант), алфавитом Х= =(хи ..., х„) переменных, конечным множеством аксиом и конечным множеством правил вывода, имеющих вид уи ...,у~„. б и называемых продукйиячи (уо ..., уа, как обычно, называются посылками, б — следствием).

Характеристики

Список файлов книги