09. Проблема применимости как неразрешимая массовая проблема

Проблема применимости для нормальных алгорифмов формулируется как частная и как общая.

Начнем с частной проблемы.

Дан нормальный алгорифм В алфавите . Можно ли построить НА над алфавитом так, чтобы он был применим к любому слову , причем тогда и только тогда, когда .

Другими словами, НА должен быть разрешающим для дополнения области применимости НА относительно алфавита .

Общая проблема применимости формулируется следующим образом: можно ли построить нормальный алгорифм над алфавитом такой, что для любых нормального алгорифма в алфавите и слова выполнялось и , где буква # не принадлежит алфавиту .

Можно сказать, что если в постановке частной проблемы применимости ставится вопрос о «тесте» на применимость заданного НА, то в постановке общей проблемы речь идет уже о возможности построения универсального «теста» на применимость в некотором классе нормальных алгорифмов. Ниже будет доказана основная теорема, в доказательстве которой предлагается способ построения НА с неразрешимой частной проблемой применимости. Так что ответ на оба поставленных выше вопроса оказывается отрицательным.

Для этого рассмотрим сначала другую проблему, которая называется Проблемой самоприменимости И формулируется следующим образом: можно ли построить такой алгорифм над алфавитом , что для любого алгорифма в алфавите , где имеет место И. Заметим, что согласно теореме о переводе в алфавите может быть задан любой алгорифм типа . Следует заметить также, что при обсуждении проблемы самоприменимости мы предполагаем, что все алгорифмы, заданные в каком-то заранее заданном алфавите Заменяются их естественными распространениями на алфавит , чтобы можно было корректно их применять к собственной записи.

Таким образом, алгорифм должен аннулировать (перерабатывать в пустое слово) записи тех и только тех алгорифмов в алфавите , которые Не применимы к собственной записи. Такие алгорифмы называют Несамоприменимыми. Другими словами, НА должен быть разрешающим для языка записей несамоприменимых нормальных алгорифмов.

Простыми примерами самоприменимого и несамоприменимого НА могут служить НА правого присоединения фиксированного слова в заданном алфавите , естественно распространенный на алфавит , где и НА, служащий формальным распространением на алфавит соответственно.

Лемма 1. Невозможен нормальный алгорифм в алфавите , применимый к записи произвольного нормального алгорифма в этом алфавите тогда и только тогда, когда алгорифм Несамоприменим.

Доказательство. Пусть такой алгорифм построен. Так как и он является алгорифмом в алфавите , то может быть поставлен вопрос о его самоприменимости. Если , то поскольку должен быть применим только к записям несамоприменимых алгорифмов, имеет место . Но тогда, так как несамоприменимый алгорифм, то должно быть . Полученное противоречие доказывает, что алгорифм не может быть построен.

Таким образом, если «тест» и «тестируемый» на самоприменимость алгорифм заданы в одном и том же алфавите, то проблема самоприменимости неразрешима, так как нельзя построить для языка записей несамоприменимых алгорифмов даже полуразрешающий НА (см. теорему 5).

Можно подумать, что, позволив «тесту» (НА ) работать в каком угодно расширении алфавита , проблему можно решить. Но это не так.

Теорема 8. Невозможен алгорифм над алфавитом , применимый к записям тех и только тех алгорифмов в алфавите , которые несамоприменимы.

Доказательство. Пусть построен алгорифм над алфавитом так, что для всякого алгорифма в алфавите имеет место . По теореме о переводе тогда может быть построен алгорифм в алфавите так, что для любого слова имеет место условное равенство .

Пусть теперь алгорифм определен как естественное распространение алгорифма на алфавит . Тогда оказывается, что этот алгорифм в алфавите таков, что для любого алгорифма в алфавите имеет место , что невозможно в силу доказанной леммы.

Суть изложенного доказательства состоит в том, что алгорифм-«тест» и алгорифм, «тестируемый» на самоприменимость, приведены к одному и тому же алфавиту, и мы попадаем в условия леммы 1.

Таким образом, проблема самоприменимости для нормальных алгорифмов, заданных в произвольном наперед заданном алфавите неразрешима.

Здесь методически целесообразно разъяснить учащимся, что алгоритмическая неразрешимость какой-либо проблемы не означает, что на вопрос, который эта проблема ставит, не может быть дан ответ ни в каком конкретном случае. Вполне можно привести пример конкретного нормального алгорифма, для которого может быть доказана его самоприменимость (или несамоприменимость). Но доказательство не есть алгоритм. Неразрешимость проблемы состоит именно в невозможности построить Алгоритм, который Для любого ее частного случая дает ответ на вопрос, сформулированный в проблеме. Именно так следует понимать Массовость любой алгоритмически неразрешимой проблемы.

Опираясь на факт неразрешимости проблемы самоприменимости, можно доказать возможность построения нормального алгорифма с неразрешимой частной проблемой применимости, откуда будет следовать, что и общая проблема подавно неразрешима.

Теорема 9. Можно построить нормальный алгорифм в алфавите так, что невозможен нормальный алгорифм над алфавитом , удовлетворяющий условиюДля любого слова .

Доказательство. Пусть . По теореме об универсальном алгорифме построим алгорифм над алфавитом так, что для любого алгорифма в алфавите и любого слова имеет место .

Теперь построим алгорифм над алфавитом так, что для любого слова . (Это можно сделать в виде композиции алгорифма, перерабатывающего всякое слово в слово и алгорифма , то есть , см. схему(8)). Следующее место в доказательстве является наиболее тонким.

Мы имеем НА Над алфавитом , но последний есть расширение алфавита и, следовательно, по теореме о переводе, может быть заменен вполне эквивалентным ему относительно алфавита алгорифмом в двухбуквенном расширении алфавита , то есть В алфавите , и для любого слова будем иметь: . Утверждается, что это и есть искомый и указанный в условии теоремы алгорифм с неразрешимой частной проблемой применимости, то есть .

Действительно, пусть построен алгорифм над алфавитом так, что . Тогда для любого алгорифма в алфавите будем иметь

,

То есть НА оказывается полуразрешающим для проблемы самоприменимости для нормальных алгорифмов в алфавите , что невозможно в силу теоремы 8.

Итак, проблема применимости для нормальных алгорифмов является неразрешимой.

Теорема 10. Существует перечислимое множество, не являющееся разрешимым.

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

Комментируя этот результат, можно заметить, что нормальный алгорифм с неразрешимой частной проблемой применимости строится как универсальный. Но на вход универсального алгорифма подается «объектный» алгорифм, запись которого может быть сколь угодно сложной. Сложность этого конструктивного объекта не ограничена сверху, возникает как бы случайная (0,1)-последовательность [10]. Естественно поэтому, что проблема применимости оказывается в этом случае неразрешимой. Но формальное доказательство основано на противоречии, обнаруживаемом в доказательстве леммы 1.

< Предыдущая		Следующая >