4.6. Проблема соответствия Поста

Мы уже встречались с различными результатами о неразрешимости, когда строили эффективные процедуры (алгоритмы) для решения любой задачи какого-либо рассматриваемого типа. Типичным примером является проблема СКС, рассмотренная в гл. 3. Некоторые из наиболее сложных теорем этой книги являются именно результатами о разрешимости.

Результаты о разрешимости могут быть основаны на интуитивном понятии алгоритма, в то время как для доказательства неразрешимости какой-либо проблемы понятие алгоритма должно быть формализовано. Наиболее обычной из таких формализации является машина Тьюринга, см. [AHU] или [HU].

Обычным способом установления неразрешимости некоторой проблемы P является "сведение" P к проблеме P₁, неразрешимость которой уже установлена, для чего надо показать, что разрешимость P влечет разрешимость P₁. В теории языков наиболее подходящей среди таких проблем P₁ оказывается проблема соответствия Поста: для морфизмов g: ∑^*→∑^*₁ и h: ∑^*→∑^*₁ выяснить, пусто или нет множество E(g,h). Подробное обсуждение вопроса о том, почему проблема соответствия Поста неразрешима, содержится в [Sa2].

Здесь будет проведено лишь следующее краткое рассуждение на интуитивном уровне.

Сначала покажем, как любая формализация интуитивного понятия алгоритма приводит к алгоритмически неразрешимым проблемам. Рассмотрим какую-нибудь из таких формализации. Читатель, знакомый с машинами Тьюринга, нормальными алгоритмами Маркова или любой другой формализацией, может выбрать ту, которая ему больше всего нравится.

Для любого алгоритма A и любого входного слова x алгоритма A существуют две возможности: либо A останавливается на x, т. е. при применении A к x вычисление завершается, либо A не останавливается на x. В последнем случае мы скажем, что A зацикливается на x. Проблема остановки состоит в решении для произвольных пар (A, x) вопроса о том, останавливается или зацикливается A на x.

Частным случаем проблемы остановки является проблема самоприменимости, определенная следующим образом. Каждому алгоритму A можно поставить в соответствие слово w(A), например записывая одну за другой все команды A и разделяя их маркерами. Алгоритм A называется самоприменимым, если A останавливается на слове w(A). Проблема самоприменимости состоит в решении вопроса, является ли произвольный алгоритм самоприменимым¹. Очевидно, что проблема самоприменимости является подпроблемой проблемы остановки, и, следовательно, если неразрешима первая, то неразрешима и вторая.

¹ (Точнее говоря, эта проблема состоит в построении алгоритма, распознающего самоприменимость произвольных алгоритмов.- Прим. ред.)

Предположим, что существует алгоритм A₀ для решения проблемы самоприменимости. Тогда A₀ останавливается на всех входах вида w(A) и дает ответ "да" или "нет" в зависимости от того, является ли алгоритм A самоприменимым. Теперь модифицируем A₀, добавляя незавершающееся вычисление, начинающееся с ответа "да". Получившийся алгоритм A₁ зацикливается (соответственно останавливается) на входах вида w(A), где алгоритм A самоприменим (соответственно не является таковым). Тогда мы приходим к противоречию при рассмотрении входа w(A₁). Следовательно, проблема самоприменимости неразрешима, а значит, такова и проблема остановки.

Каждому примеру (A, x) проблемы остановки можно поставить в соответствие пару морфизмов (g,h), такую, что A останавливается на x тогда и только тогда, когда множество E(g,h) непусто. Для этого нужно командам A поставить в соответствие пары (g(a),h(a)) таким образом, чтобы g моделировал вычисление A "быстрее", чем h, и чтобы h "догонял" g только в конце вычисления. (Аналогичное соответствие устанавливается в доказательстве теоремы 6.9.) Надо только быть уверенным в том, что пара (g, h) не дает "паразитных решений", т. е. что E(g,h) непусто только в том случае, когда A останавливается на x. Установленное таким образом соответствие показывает неразрешимость проблемы соответствия Поста.

Неразрешимость проблемы соответствия Поста означает отсутствие алгоритма, дающего ответ для произвольной пары (g,h). Конечно, существуют отдельные пары (g,h), для которых легко установить, что E(g,h) пусто. С другой стороны, проблема соответствия Поста остается неразрешимой, даже если g и h являются кодами; см. [Le].