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

Массовая проблема – бесконечный класс однотипных (индивидуальных) проблем.

Пример.

Индивидуальная проблема: Обладает ли заданным свойством Q конкретная частично-рекурсивная функция (ЧРФ).

Совокупность всех таких задач (для всех ЧРФ) образует массовую проблему распознавания свойства Q.

Будем рассматривать только задачи, дя которых имеет смысл ответ ДА или НЕТ.

Введем обозначения: п – индивидуальная проблема, П – массовая проблема, ,

f(п) – характеристическая функция.

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

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

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

Пусть существуют две массовые проблемы П1 и П2. Пусть существует алгоритм А, который по всякой индивидуальной задаче строит индивидуальную задачу , такую, что выполняется:

имеет ответ «ДА» тогда и только тогда, когда имеет ответ «ДА». В этом случае говорят, что проблема П1 сводится к проблеме П2. Если проблема П1 неразрешима, то проблема П2 также неразрешима.

Доказательство (от противного).

Пусть проблема П2 разрешима. Тогда можно построить разрешающий алгоритм для проблемы П1. Берем произвольную индивидуальную задачу . Имея алгоритм А, строим индивидуальную задачу , . Применяем к задаче п2 существующий по предположению разрешающий алгоритм для проблемы П2. Если задача п2 имеет ответ «ДА», то для задачи п1ответ должен быть «НЕТ». Т. к. по

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

уже установлена.

Рассмотрим некоторые из таких проблем.