Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
') В оригинале французский пример: regorgeais «= re/gorge/ais = reg/or/ geais. — Прим. перед. Г л. VI. Комбинаторные системы и машины Тьюринга
107
Наметим ход рассуждения, с помощью которого доказывается неразрешимость этой проблемы.
Эскиз доказательства. Пусть имеются две конкретные rt-ки в алфавите її:
(Oi.....Gn) и (H1.....Hn).
Построим нормальную систему (N), в которой ни одно выводимое из аксиомы слово не пусто. . Аксиома системы (N) — непустое слово А є її*. .. Схемы продукций системы (N) таковы:
GiP-* PH1, 1 </<«.
Исследуем процесс получения теорем в (N). Предположим, что аксиому А можно представить в виде
А = G'P',
где G' — одно из G,-; тогда появится возможность вывести из А следствие:
А = G'P' P'H',
где через H' обозначено Я,-, соответствующее G,-.
Предположим, далее, что Р'Н' представляется, в свою очередь, в виде
Р'Н' = G"P",
где через G" также обозначено одно из Gv, тогда мы получим, что
G"P" -* Р"Н" и т. д.
Таким образом, доказательство в (N) производится по следующей схеме (отношение следования обозначается вертикальной стрелкой):
(0) A= G'P'
(1) Р'Н' =G" Р"
(2) Р"Н" = G'" P'"
(k-l) р<*-і>я<*-і)=0<*>р<*> (k) PwHw = В 108
Часть /. Предварительные сведения из логики и алгебры
Из этой схемы непосредственно получаем
(0)' АН' = G'P'H' = G' G"P" (1Y АН'Н" = G' G"P"H" = G' G" G'" P'"
(k - 2)' АН'Н" ... Я<*-'> = G'G" ... Gjk-0Pjk-Vk"4 -
= G'G" ... Gjk-W
(ft - 1)' АН'Н" ... я(к"VJk> = G'G" ... Gjk-ltGjk* PjVw =
= GV ... Gjk-4GwS.
Поскольку все Яі H Gi не пусты (хотя Pi могут в принципе быть пустыми), верны следующие неравенства: длина слова длина слова G'G"\
длина слова АН'Н" > длина слова G'G"G'" и т. п. Итак, мы получили
Предложение. Если В — теорема системы (N), то существует последовательность индексов, ведущая к «псевдопостов-скому» равенству
АН'Н" ... Я<*> = G'G" ... GMB,
а также к неравенствам
длина слева АН' ... Я<->">> длина слова G' ... GU).
Обратно, если имеют место это равенство и соответствующие неравенства, то можно «восстановить» все P1- и доказательстбо теоремы В (провести нужное рассуждение предоставляется читателю в качестве упражнения).
Мы видим, таким образом, что проблема установления того, выводимо ли данное слово из аксиомы в системе (N), эквивалентна «псевдопостовской» проблеме. Чтобы перейти к проблеме Поста, необходимо освободиться от неравенств, а также от самих слов А и В.
Можно эффективно построить (см. упражнения) такую нормальную систему, производную от (N), что ее проблема тождества эквивалентна проблеме Поста, а это влечет за собой неразрешимость последней.
Проблема Поста в свою очередь будет служить отправной точкой для доказательства некоторых теорем о неразрешимости, относящихся к формальным грамматикам.
Одна возможная интерпретация проблемы Поста. Пусть sH и S—два алфавита (возможно, совпадающие).
Рассмотрим такое отображение свободной полугруппы sH* в (или на) полугруппу 93*, которое было бы совместимо с кон- Г л. VI. Комбинаторные системы и машины Тьюринга
109
катенацией (это значит, что образ произведения, т. е. конкатенации, должен совпадать с произведением образов). Подобное отображение является гомоморфизмом полугруппы; оно определяется образами однобуквенных слов.
Если даны два таких гомоморфизма ф и то можно поставить следующий вопрос: существует ли слово Мей*, имеющее одинаковые образы относительно ф и ф, т. е. такое, что
Ф (M) = IjJ (M).
Эта проблема известна как проблема диагонализации двух гомоморфизмов свободной полугруппы. Очевидно, что она эквивалентна проблеме Поста,
6.2.4. Неразрешимые проблемы: резюме
Мы построили математический объект (машину Тьюринга), с которым связана некоторая неразрешимая проблема, и с помощью теорем об эквивалентности получили ряд результатов о неразрешимости, связанных с другими объектами. Последовательность изложения может быть представлена диаграммой на стр. 110.
6.2.5. Упражнения
1. Привести конкретные примеры ситуаций, в которых проблема соответствий Поста разрешима; сделать это, либо указав последовательность индексов, дающую положительный ответ, либо доказав, что такой последовательности не существует.
2. Устранить «лишние» условия в «псевдопостовской» проблеме.
А. В свое время мы доказали, что любой системе можно сопоставить эквивалентную путем кодирования исходной системы в двухбуквенном алфавите {a, b}.
Предположим, что (W) заранее была подвергнута такому кодированию. Поставим в соответствие системе (N) «антинормальную» систему (AN), аксиома и левые (правые) части продукций которой представляют собой зеркальные образы соответственно аксиомы и левых (правых) частей продукций системы (N).
Затем дополним (AN) до системы (ЛАП), алфавит которой содержит маркер h, причем этот маркер добавляется справа к каждому слову, выводимому в (AN).
Наконец, построим нормальную систему (NC), в которой выводимы те и только те слова, которые Либо выводимы в системе (ANl) либо получаются из слов, выводимых в (ANl), циклическими перестановками:
