Математическая логика и теория алгоритмов. Стенюшкина В.А. - 60 стр.

     2 Рассмотрим функцию y+z. Составим уравнение y+z=x и будем давать
переменной z значение 0,1,... . Получим частичную функцию x-y, определен-
ную для x>y;
     Определение Частичная функция f называется частично рекурсивной, ес-
ли она может быть получена из простейших функций o, s, Imn конечным числом
операций суперпозиции, примитивной рекурсии и минимизации.
     Примечание - Класс частично рекурсивных функций шире класса прими-
тивно рекурсивных. (Хотя бы потому, что примитивно рекурсивные функции
всюду определены, а среди частично рекурсивных встречаются неопределен-
ные всюду).

                            2.1.5 Тезис Черча

      Значение понятия частично рекурсивной функции состоит в следующем.
С одной стороны, каждая частично рекурсивная функция вычислима путем
процедуры, отвечающей интуитивному представлению об алгоритмах. С дру-
гой стороны, какие бы классы алгоритмов ни строились, вычисляемые ими чи-
словые функции оказывались частично рекурсивными. Поэтому ныне общеп-
ринятой является следующая естественнонаучная гипотеза.
      ТЕЗИС ЧЕРЧА Класс алгоритмически (или машинно) вычислимых час-
тичных числовых функций совпадает с классом всех частично рекурсивных
функций.

                    2.1.6 Общерекурсивные функции

      Определение Операция Ml , определяемая соотношением
             Mf , если Mf определена всюду,
      Ml f =
             не определена, в противном случае,
называется слабой минимизацией функции f.
     Определение Функции, которые можно получить из простейших функ-
ций конечным числом операций суперпозиции, примитивной рекурсии и
слабой минимизации, называются общерекурсивными.
     Примечание - Общерекурсивные функции всюду определены.
     Теорема Все общерекурсивные функции являются всюду определенными
частично рекурсивными функциями.
     Доказательство следует из определения слабой минимизации.
     Теорема Каждая всюду определенная частично рекурсивная функция
общерекурсивна.
      Доказательство этой теоремы очень тонкое и здесь не приводится.
     Лемма 1 Каждая примитивно рекурсивная функция является общерекур-
сивной.
     Доказательство следует из определения общерекурсивной функции.
     Лемма 2 Класс общерекурсивных функций шире класса примитивно ре-
курсивных функций.