§10 Алгоритмически неразрешимые проблемы
1
0
)
В данном разделе устанавливается алгоритмическая неразрешимость ряда
проблем, относящихся к теории алгоритмов. Будем рассматривать так
называемые массовые проблемы. Массовая проблема представляет собой
бесконечную серию индивидуальных задач. Например, индивидуальной задачей
является такая: обладает ли заданным свойством Q конкретная частично
рекурсивная функция. Совокупность всех таких задач (для всех частично
рекурсивных функций) образует массовую проблему распознавания свойства Q.
Мы ограничимся такими массовыми проблемами, в которых все
индивидуальные задачи имеют двузначный ответ ("ДА" или "НЕТ").
Массовая проблема П является алгоритмически разрешимой, если
соответствующая характеристическая функция
, которая определяется
соотношением:
f
f
инд зада а П имеет ответ ДА
инд зада а П имеет ответ НЕТ
()
""
""
π
π
π
=
⇔÷∈
⇔÷∈
1
0
(1)
является вычислимой.
Решая конкретную массовую проблему следует считаться с возможностью,
что она может оказаться алгоритмически неразрешимой, поэтому необходимо
иметь представление о технике доказательства неразрешимости. Основной
метод, применяемый в доказательствах алгоритмической неразрешимости,
базируется на следующем рассуждении. Пусть (имеем две массовые проблемы
П
1
и П
2
. Пусть имеется алгоритм А , который по всякой индивидуальной задаче
строит индивидуальную задачу
π
, такую, что выполнено:
π
1
∈П
1 2
1
2
∈П
π
1
имеет "ДА"
⇔π
имеет "ДА" .
2
В этом случае говорят, что проблема П
1
сводится к проблеме П
2
. Если
проблема П
1
неразрешима, то проблема П
2
также неразрешима. Действительно,
пусть это не так, и проблема П
2
разрешима. Тогда можно построить
разрешающий алгоритм для проблемы П
1
. Берем произвольную индивидуальную
задачу
π
. Имея алгоритм А ,строим индивидуальную задачу
ππ
.
Теперь применяем к задаче
π
существующий по предположению разрешающий
алгоритм для проблемы П
1
∈П
21
= A()
π
1
2
2
. Если задача
π
имеет ответ "ДА", то для задачи
полагаем ответ "ДА", в противном случае, для задачи
π
полагаем ответ "НЕТ".
Поскольку, по условию, проблема П
2
1
1
неразрешима, то получим противоречие.
Значит, проблема П
2
неразрешима. Данное рассуждение называется методом
сводимости, и его применение возможно, если уже имеется запас проблем,
алгоритмическая неразрешимость которых уже установлена. Приведем теперь
некоторые из таких проблем.
2
0
)
Рассмотрим так называемую проблему самоприменимости машин
Тьюринга. Она заключается в следующем. Рассматриваются, машины Тьюринга,
внешние алфавиты которых содержат символы О, 1 (наряду с другими). Для
каждой машины Тьюринга Т построим Код (Т) который является ( 0,1) - словом,
61