АЛГОРИТМИЧЕСКАЯ РАЗРЕШИМОСТЬ

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

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

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

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

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

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

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

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

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

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

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