Алгоритмически неразрешимые проблемы

Алгоритмически неразрешимые проблемы

Л е к ц и я 16

В данном разделе устанавливается алгоритмическая неразрешимость ряда проблем, относящихся к теории алгоритмов.

Будем рассматривать так называемые массовые проблемы. Массовая проблема представляет собой бесконечную серию индивидуальных задач. Например, индивидуальной задачей является такая: обладает ли заданным свойством Q конкретная частично рекурсивная функция. Совокупность всех таких задач (для всех частично рекурсивных функций) образует массовую проблему распознавания свойства Q. Мы ограничимся такими массовыми проблемами, в которых все индивидуальные задачи имеют двузначный ответ («ДА» или «НЕТ»).

Массовая проблема П является алгоритмически разрешимой, если соответствующая характеристическая функция f, которая определяется соотношением:

является вычислимой.

Решая конкретную массовую проблему, следует считаться с возможностью, что она может оказаться алгоритмически неразрешимой, поэтому необходимо иметь представление о технике доказательства неразрешимости. Основной метод, применяемый в доказательствах алгоритмической неразрешимости, базируется на следующем рассуждении. Пусть имеем две массовые проблемы П₁ и П₂. Пусть имеется алгоритм А, который по всякой индивидуальной задаче строит индивидуальную задачу такую, что выполнено: имеет ответ «ДА» тогда и только тогда, когда имеет ответ «ДА». В этом случае говорят, что проблема П ₁ сводится к проблеме П₂. Если проблема П₁ неразрешима, то проблема П₂ также неразрешима. Действительно, пусть это не так, и проблема П₂ разрешима. Тогда можно построить разрешающий алгоритм для проблемы П₁. Берем произвольную индивидуальную задачу . Имея алгоритм А, строим индивидуальную задачу . Теперь применяем к задаче существующий по предположению разрешающий алгоритм для проблемы П₂. Если задача имеет ответ «ДА», то для задачи полагаем ответ «НЕТ». Поскольку, по условию, проблема П₁ неразрешима, то получим противоречие. Значит, проблема П₂ неразрешима. Данное рассуждение называется методом сводимости, и его применение возможно, если уже имеется запас проблем, алгоритмическая неразрешимость которых уже установлена. Приведем теперь некоторые из таких проблем.

Рассмотрим так называемую проблему самоприменимости машин Тьюринга. Она заключается в следующем. Рассматриваются машины Тьюринга, внешние алфавиты которых содержат символы 0,1 (наряду с другими). Для каждой машины Тьюринга Т построим Код (Т), который является (0,1)-словом, и запустим машину Т в начальной конфигурации q ₁ Код (Т). Если машина Т останавливается (т.е. попадает в заключительное состояние) через конечное число шагов, то она называется самоприменимой, в противном случае — несамоприменимой. Заметим, что имеются как самоприменимые, так и несамоприменимые машины Тьюринга. Например, несамоприменимой будет машина Т ₁, у которой все команды имеют вид q_ia_j à q_ia_jE (в правых частях команд нет заключительного состояния), самоприменимой будет машина Т ₁, у которой все команды имеют вид q_ia_j à q ₀ a_jE (в правых частях всех команд имеется заключительное состояние). Проблема самоприменимости состоит в том, чтобы по любой машине Тьюринга Т определить, является ли она самоприменимой или нет. Условимся, что машина Тьюринга М решает проблему самоприменимости, если для любой машины Т начальную конфигурацию q ₁ Код (Т) она переводит в q ₀1, если машина Т самоприменима, и в q ₀0, если машина Т несамоприменима.

Теорема 16.1. Не существует машины Тьюринга М, решающей проблему самоприменимости, т.е. проблема самоприменимости алгоритмически неразрешима.

Доказательство. Предположим противное, т.е. пусть существует машина Тьюринга М, решающая проблему самоприместимости в указанном выше смысле. Построим новую машину М ₀, добавив новое состояние и объявив его заключительным, а также добавив новые команды для состояния q ₀, которое было заключительным в М:

q ₀1 à q ₀1 E;(a)

q ₀0 à 0 E. (b)

Рассмотрим теперь работу машины М ₀. Пусть Т — произвольная машина. Если Т — самоприменима, то начальная конфигурация q ₁ Код (Т) перейдет с помощью команд машины М _O через конечное число шагов в конфигурацию q ₀1, далее применяется команда (a), и машина М ₀ никогда не остановится. Если Т — несамоприменима, то начальная конфигурация q ₁ Код (Т) перейдет с помощью команд машины М через конечное число шагов в конфигурацию q ₀0, далее применяется команда (b), и машина М ₀ остановится. Значит, машина М ₀ применима к кодам самоприменимых машин Т и не применима к кодам самоприменимых машин Т. Теперь рассмотрим Код (М ₀) и применим машину М ₀ к начальной конфигурации q ₁ Код (М ₀). Сама машина М ₀ является либо самоприменимой, либо несамоприменимой. Если М ₀ самоприменима, то по доказанному, она никогда не остановится, начав с q ₁ Код (М ₀), и потому она несамоприменима. Если М ₀ несамоприменима, то по доказанному, она останавливается через конечное число шагов, начав с q ₁ Код (М ₀), и потому она самоприменима. Получили противоречие, которое является следствием допущения существования машины М ₀, решающей проблему самоприменимости, что и требовалось доказать.

Приведем еще один пример неразрешимой проблемы.

Проблемой останова называют проблему, заключающуюся в том, чтобы по любой машине Тьюринга Т и слову Р в ее внешнем алфавите узнать, применима ли Т к начальной конфигурации q ₁ Р.

Проблема останова алгоритмически неразрешима, так как если бы она была разрешимой, то, взяв в качестве Р слово Код (Т), мы получили бы разрешимость проблемы самоприменимости.

Приведем теперь неразрешимые проблемы, связанные с проверкой свойств частично рекурсивных функций. Пусть U (n, x) — универсальная функция для одноместных частично рекурсивных функций и соответствующая ей нумерация функций

f ₀(x), f ₁(x), …, f_n (x), …, (16.1)

где f_n (x) = U (n, x).

Теорема 16.2. Проблема «функция f_n всюду определена», n Î N ₀ алгоритмически неразрешима.

Доказательство. Определим характеристическую функцию данной проблемы

.

Определим новую функцию Ф (x), где

.

Заметим, что функция Ф(x) всюду определена. Кроме того,

.

Нам нужно доказать невычислимость функции g. Ясно, что из вычислимости функции g следует вычислимость функции Ф. Предположим, что функция Ф вычислима. Тогда существует число n такое, что Ф(x) = U (n, x) = f_n (x). Поскольку Ф(x) — всюду определена, то должно быть g (n) = 1. Значит, имеем Ф(n) = f_n (n) и Ф(n) = f_n (n) + 1. Поскольку при x = n функция Ф(x) определена, то получаем противоречие. Следовательно, Ф(x) — невычислима, откуда следует, что функция g (x) — невычислима, что и требовалось доказать.

Обозначим через W_n область определения функции f_n (x) в последовательности (16.1).

Теорема 16.3. Проблема «n Î W_n», n Î N ₀ алгоритмически неразрешима.

Доказательство. Рассмотрим характеристическую функцию проблемы:

и построим новую функцию g (x), где

Ясно, что из вычислимости функции f следует вычислимость функции g. Кроме того, справедливо соотношение для любых x Î N ₀: g (x) определена Û f_x (x) не определена.

Предположим теперь, что функция g вычислима. Тогда существует число m, такое, что g = f_m. Тогда имеем m Î W_m Û g (m) определено Û f_m (m) не определено Û m Ï W_m. Получили противоречие, и поэтому g — невычислима и, следовательно, f — невычислима, что и требовалось доказать.

Следствие 16.4. («Проблема применимости») Проблема «f_x (y) определена», x, y Î N ₀ — неразрешима.

Доказательство. Если бы данная проблема была разрешима, то и проблема «n Î W_n» была бы разрешима, что и требовалось доказать.

Рассмотрим теперь алгоритмический прием, позволяющий эффективно работать с номерами частично рекурсивных функций. Пусть f (x, y) — вычислимая функция. Фиксируем x = a и положим g_a (y) = f (a, y). Функция g_a (y) — одноместная и вычислимая. Значит, существует номер e такой, что g_a (y) = f_e (y) в последовательности (2). Покажем, что данный номер e находится эффективно.

Теорема 16.5. Для всякой вычислимой функции f (x, y) существует общерекурсивная функция s (x) такая, что f (x, y) = f_{s ( x )}(y).

Доказательство. Пусть F — программа МПД, вычисляющая f (x, y). Фиксируем x = a, и рассмотрим программу МПД Q_a, где

Легко убедиться, что данная программа Q_a вычисляет f (a, y). Пусть s (a) — номер программы Q_a. Согласно построению f (a, y) = f_{s ( a )}(y). При этом, поскольку F фиксирована, то s (a) — эффективно вычислима, что и требовалось доказать.

Теперь, в силу вычислимости f (x, y) существует n такое, что f (x, y) = U ⁽²⁾(n, x, y), где U ⁽²⁾ — универсальная функция для двухместных частично рекурсивных функций. Тогда в предыдущей конструкции при x = a имеем s = s (n, a) и выполнено f_{s ( n , a )}(y) = = U (s (n, a), y), где U — универсальная для одноместных частично рекурсивных функций. Таким образом, используя тезис Черча и приведенную выше конструкцию, установлена теорема.

Теорема 16.6 (нумерационная). Существует общерекурсивная функция s (n, x) такая, что выполнено

U ⁽²⁾(n, x, y) = U (s (n, x), y).

Данная теорема справедлива и в более общей ситуации, которую отметим без доказательства.

Теорема 16.7. Для любых m, n ³ 1 существует общерекурсивная функция , такая, что выполнено

,

где k Î N ₀, , .

Данное утверждение называют s - m - n -теоремой.

Теорема 16.8. Проблема «f_x = », x Î N ₀ — неразрешима. (Здесь означает функцию, тождественно равную нулю.)

Доказательство. Рассмотрим следующую функцию:

Легко видеть, что функция f (x, y) вычислима, поскольку универсальная функция U (n, x) вычислима. По теореме 16.5 существует общерекурсивная функция s (x) такая, что f (x, y) = f_{s ( x )}(y) = = U (s (x), y). Имеем по определению x Î W_x Û f_{s ( x )}(y) = . Если бы проблема f_z (y) = , z Î N ₀ была разрешима, то тогда проблема «x Î W_x» была бы разрешимой, что противоречило бы теореме 16.3, что и требовалось доказать.

Следствие16.9. Проблема «f_x = f_y», x, y Î N ₀ — неразрешима.

Теорема 16.10 (Клини). Для любой частично рекурсивной функции h (x) существует число а такое, что f_{h ( a )}(x) = f_a (x).

Доказательство. Пусть задана частично рекурсивная функция h (x). Рассмотрим вспомогательную функцию f (y, x) = U (h (s (y, y)), x), где s — функция из тождества (10), существующая по нумерационной теореме 16.6. Поскольку функция f (y, x) — частично рекурсивная, то существует число n, такое, что f (y, x) = U (h (s (y, y)), x) = = U ²(n, y, x). По нумерационной теореме 16.6 имеем f (y, x) = = U (s (n, y), x) или U (h (s (y, y)), x) = U (s (n, y), x). Теперь положим y = n, и поскольку функция s общерекурсивна, то s (n, n) определено. Тогда получаем U (h (s (n, n)), x) = U (s (n, n), x). Обозначая s (n, n) = a, имеем U (h (a), x) = U (a, x) или f_{h ( a )}(x) = f_a (x), что и требовалось доказать.

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

Произвольное множество А Í N ₀ называется рекурсивным, если соответствующая характеристическая функция , где

вычислима. Ясно, что рекурсивное множество А характеризуется тем, что проблема «x Î A» разрешима. Пусть F — множество одноместных частично рекурсивных функций, отличных от пустого множества и от множества всех одноместных частично рекурсивных функций (т.е. F — нетривиальное множество). Обозначим через N_F — множество всех номеров функций из F.

Теорема 16.11. (Райс) Множество N_F нерекурсивно.

Доказательство. Предположим, что множество N_F рекурсивно. Тогда его дополнение также рекурсивно, так как . По условию оба множества N_F и непустые. Выберем некоторые a Î N_F и b Î и определим функцию

Функция g (x) общерекурсивна, так как выполнено равенство g (x) = a + b . По теореме 16.10 для функции g (x) существует число а такое, что f_{g ( a )}(x) = f_a (x). Тогда должно быть либо a Î N_F, либо a Î . Если a Î N_F, то, по определению, f_a Î F, и так как f_{g ( a )} = f_a, то f_{g ( a )} Î F. Однако из a Î N_F следует g (a) = = b Î , т.е. g (a) Î , и тогда f_{g ( a )} Ï F. Получено противоречие.

Если a Î , то, по определению, f_a Ï F и тогда в силу f_{g ( a )} = f_a имеем f_{g ( a )} Ï F. Однако из a Î имеем g (a) = a Î N_F, т.е. g (a) Î N_F и значит f_{g ( a )} Î F. Снова получено противоречие.

Итак, число а не содержится ни в одном из множеств N_F и , чего быть не может, так как N ₀ = N_F È . Противоречие является следствием предположения о рекурсивности множества N_F, что и требовалось доказать.

Пусть Q — некоторое нетривиальной свойство одноместных частично рекурсивных функций, т.е. имеются функции как обладающие свойством Q, так и не обладающие свойством Q.

Теорема 16.12. Проблема «f обладает свойством Q», f Î E ¹ неразрешима.

Доказательство. Пусть проблема «f обладает свойством Q», f Î E ¹ разрешима, т.е. существует МПД, которая для любой f Î E ¹ начальную конфигурацию (n, 0, …), где n — номер функции f, через конечное число шагов переводит в заключительную конфигурацию (1, *, …), если f обладает свойством Q, и в заключительную конфигурацию (0, *, …), если f не обладает свойством Q. Тогда для множества номеров функций из E ¹, обладающих свойством Q, можно указать разрешающую процедуру для проблемы n Î соотношением n Î Û МПД дает результат 1.

Данное соотношение показывает, что множество рекурсивно, что противоречит теореме 16.11, что и требовалось доказать.

Теорема 16.11 имеет многочисленные применения в теоретическом программировании и позволяет доказывать неразрешимость многих задач, связанных с вычислением на машинах. Большое число алгоритмически неразрешимых проблем имеется в книге: Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. М., 1972.

Приведем одно важное понятие теории алгоритмов, связанное с вычислимостью. Выше была установлена невычислимость характеристической функции предиката «x Î W_x». В то же время частичная характеристическая функция, определенная соотношением

является вычислимой. Это следует из тезиса Черча. Поэтому говорят, что проблема «x Î W_x» полувычислима.

Многие проблемы, будучи неразрешимыми, являются полувычислимыми.

Определение 16.13. Предикат М () на натуральных числах (здесь ) называется полувычислимым, если частичная характеристическая функция f, определенная соотношением

вычислима.

Замечание 16.14. В литературе также используются равносильные термины: частичная разрешимость, рекурсивная перечислимость.

Примеры:

1. Любой разрешимый предикат полувычислим.

2. Для любой вычислимой функции g () проблема « Î D (g)» является полувычислимой, так как вычислима функция (здесь ).

3. Проблема «x Ï W_x» не является полувычислимой. Действительно, если f — соответствующая частичная характеристическая функция, то . Значит, D (f) отличается от области определения любой одноместной вычислимой функции. Поэтому f не может быть вычислимой.

Теорема 16.15. Предикат М () полувычислим тогда и только тогда, когда существует вычислимая функция g () такая, что

М () = и Û Î D (g).

Доказательство. Если М () полувычислим и f — соответствующая частичная характеристическая функция, то по определению М () = и Û Î D (g). Обратное следует из примера 2.

Определение 16.16. Множество А из N ₀ называется рекурсивно перечислимым, если частичная характеристическая функция f, где

вычислима. Это равносильно тому, что предикат «x Î A» полувычислим.

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

Дата добавления: 2014-12-29; Просмотров: 986; Нарушение авторских прав?; Мы поможем в написании вашей работы!