2.6 Частично–рекурсивные функции и тезис Черча
В силу узости класса примитивно–рекурсивных функций для определения алго-
ритма необходимо выйти из этого класса. Мы рассмотрели оператор, применение
которого выводит из класса примитивно–рекурсивных функций, — это оператор ми-
нимизации. Будем использовать этот оператор как дополнительное конструктивное
средство при определении нового класса функций.
Определение 2.6. Частично–рекурсивной называется функция, построенная из
простейших с помощью конечного числа операторов суперпозиции, примитивной ре-
курсии и минимизации.
Определение 2.7. Всюду определенная частично–рекурсивная функция назы-
вается общерекурсивной или просто рекурсивной функцией.
В силу теоремы (2.10) примером рекурсивной, но не примитивно–рекурсивной
функции является диагональная функция Аккермана A(x).
Частично–рекурсивные функции используются для определения понятия алго-
ритма, которое вводится с помощью тезиса Черча.
Тезис Черча: всякий алгоритм может быть реализован частично–рекурсивной
функцией.
Понятие частично–рекурсивной функции — одно из главных в теории алгоритмов.
Тезис Черча — это не теорема, а утверждение, которое связывает понятие алгорит-
ма и строгое математическое понятие частично–рекурсивной функции. Тезис Черча
является достаточным для того, чтобы придать необходимую точность формулиров-
кам алгоритмических проблем и сделать принципиально возможным доказательство
их неразрешимости. Утверждение о несуществовании частично–рекурсивной функ-
ции эквивалентно факту несуществованию алгоритма решения соответствующей за-
дачи.
В силу тезиса Черча вопрос о вычислимости функции или, что то же самое, о
существовании алгоритма ее вычисления, равносилен вопросу о ее частичной ре-
курсивности. Понятие частично–рекурсивной функции — строгое математическое,
поэтому обычные математические методы и приемы позволяют непосредственно до-
казать, что решающая задачу функция не может быть рекурсивной и тем самым
доказать неразрешимость проблемы.
Точное описание класса частично–рекурсивных функций вместе с тезисом Чер-
ча дает одно из возможных решений задачи о формальном определении алгоритма.
Вместе с тем, это решение не вполне прямое, так как понятие вычислимой функ-
ции является вторичным по отношению к понятию алгоритма: значение функции в
каждой точке, соответствующей исходным данным алгоритма — это результат ра-
боты алгоритма на этих данных. Спрашивается, нельзя ли уточнить само понятие
алгоритма и уже затем при его помощи определить точно класс вычислимых функ-
ций? Это было сделано Постом и Тьюрингом. Основная мысль, заложенная в такой
формализации алгоритма, заключается в том, что алгоритмические процессы — это
процессы, которые может совершать некоторая подходяще устроенная машина. В
соответствии с этой мыслью в следующей главе мы рассмотрим описание в точ-
ных математических терминах довольно узких классов машин, но на этих машинах
оказывается возможным осуществить все алгоритмы. Алгоритмы, осуществимые на
этих формально определенных машинах, можно рассматривать как математические
точно определенные алгоритмы. В главе 3 мы покажем, что класс функций, вычис-
лимых на этих машинах, в точности совпадает с классом всех частично–рекурсивных
функций. Тем самым мы получим еще одно фундаментальное подтверждение тезиса
50