Неразрешимость и труднорешаемые проблемы

УДК 510.643 ББК 22.1я431

Аннотация

Общее понятие алгоритма первично и не определяемо, а может бытьь только понято через его свойства, подобно понятию множества. Через вычислительные модели (машина Тьюринга, Колмогорова, нормальные алгоритмы Маркова) оно уточняется. То же относится к понятию исчисления, которое уточняется в конкретных дедуктивных системах (логические исчисления, формальная арифметика). Между алгоритмами и исчислениями существует тесная связь Для каждого алгоритма существует исчисление, порождающее область определения этого алгоритма, более того, можно указать исчисление, порождающее те и только те пары (x,y), для которых Ψ(x) = y. С другой стороны, для каждого исчисления существует алгоритм, область определения которого совпадает с множеством, порождаемым исходным исчислением. Каждый алгоритм задает функцию на своей области применимости, ее значения равны результату алгоритма Ψ(x). Применительно к исчислению можно говорить о породимых, разрешимых и перечислимых множествах. Тезисы Черча и Поста формулируются, соответственно, для вычислимой модели алгоритма и порождающей модели исчисления. С помощью общего понятия исчисления можно глубже осмыслить многие фундаментальные понятия математической логики. В частности, знаменитую теорему Геделя о полноте, утверждающую, что все истинные формулы логики предикатов 1-го порядка могут быть порождены некоторым исчислением. Другая знаменитая теорема Геделя о неполноте утверждает, что множество всех истинных формул арифметики (а, значит, и множество всех общезначимых формул логики предикатов 2-го порядка) не может быть порождено никаким исчислением. На базе понятия исчисления можно изложить всю дескриптивную теорию алгоритмов (наличие или отсутствие алгоритма без оценки затрат на достижение этой цели). Вычислимая функция – это функция, вычислимая каким-либо алгоритмом: при применении к какому-нибудь входу вычисляющий алгоритм должен не только давать результат, совпадающий со значением функции на этом входе, если такое значение существует, но  и не давать никакого результата, если функция не определена на данном входе. Породимое множество – это множество, порождаемое какимлибо исчислением. Перечислимое множество – это либо множество значений всюду определенной вычислимой функции натурального аргумента, либо пустое множество. Обе теоремы Геделя можно сформулировать в терминах перечислимости и неперечи-слимости соответствующих множеств. Множество называется разрешимым, или распознаваемым, если оно содержится в некотором породимом множестве X и для него существует разрешающий алгоритм. Алгоритм Ψ называется разрешающим алгоритмом для подмножества A множества X, если множество допустимых входов для Ψ совпадает с X и Ψ отвечает на все вопросы типа “x∈X & x∈A”.Проблема отыскания такого алгоритма называется проблемой разрешения для множества A.