8.5. Алгоритмическая разрешимость

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

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

При этом для всякой задачи может иметь место один из следующих двух случаев:

1. Алгоритм решения задачи существует.

2. Разрешающего алгоритма нет.

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

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

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

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

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

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

8.5.1. Разрешимые множества

Пусть A  некоторое подмножество множества N^k. Характеристической функцией множества A называется функция (x₁, ... , x_k), определяемая соотношением:

(x₁, ... , x_k) = .

ОПРЕДЕЛЕНИЕ

Множество A называется разрешимым множеством, если его характеристическая функция является вычислимой.

Очевидно, что разрешимость множества A означает существование алгоритма, который для произвольного элемента aN^k за конечное число шагов работы дает ответ на вопрос о принадлежности a множеству A.

Пример. Множество {n|n  четное число} является рекурсивным множеством, поскольку имеет рекурсивную характеристическую функцию f(x) = (mod(x, 2)).

Здесь mod(x, 2) функция остатка от деления x на 2.

Упражнение. Пусть A и B разрешимые подмножества множества N^k. Показать, что множества A  B, A  B и N^k \ A также являются разрешимыми.

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

Увеличим числовые представления всех возможных решений задачи на 1. Это позволяет выделить 0 из множества решений задачи в качестве специального значения.

Произвольной задаче T поставим в соответствие множество

D_T = {(a, b)  ((b  0)  (решение задачи T для начальных данных a равно b))  ((b = 0)  (решение задачи T для начальных данных a не существует))}.

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

Покажем, что для задачи T существует алгоритм получения решения при любых начальных данных тогда и только тогда, когда D_T  N² является разрешимым множеством.

1. Пусть для T имеется разрешающий алгоритм . Тогда для проверки принадлежности пары (a, b) множеству D_T достаточно применить  к начальному данному a и сравнить полученное решение c со значением b-1.

2. Пусть D_T  N². Тогда нахождение решения T для начального данного a состоит в проверке того, что (a, 0)  D_T. Если проверяемое условие имеет место, то решение задачи T существует и может быть найдено последовательной проверкой выполнения условия (a, i)  D_T для i = 1, 2, . . . , выполняемой до тех пор пока не будет найдена пара (a, b)  D_T , озгачающая, что решение T на начальных данных a равно b1.

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