Частично рекурсивные функции.

Пусть задана функция .

Определение. Говорят, что . получено из с применением операции ограниченной минимизации, если имеет место следующее равенство: (44)

и обозначают (45)

Лемма 1.2. Операция ограниченной минимизации сохраняет свойство примитивной рекурсивности функции.

Действительно, если имеется алгоритм , вычисляющий функции , то есть и алгоритм вычисляющий функции ..

Доказательство.Пусть требуется вычислить значение функции j на произвольном наборе .

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

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

Если на (t+1) шаге вычислено значение и , то значение функции φ на наборе . считаем равным t. Если , то переходим к следующему этапу.

В случае, когда алгоритм завершает свою работу на каком-то этапе безрезультативно, или работает бесконечно, то будем считать, что значение j не определено на данном наборе, т.е. на наборе .

Определение. Частично рекурсивным описанием (ЧРО) функции f называется конечная последовательность функций , удовлетворяющих следующим условиям:

1. ;

2. i , – яв-ся либо элемент-й функцией, либо получается из предшествующей ей последовательности функций с помощью одной из операций: подстановки, примитивной рекурсии или ограниченной минимизации.

Определение. Функция f называется ЧРФ, если существует ее ЧРО.

Определение. Функция f называется общерекурсивной, если она ЧРФ и всюду определена. (В других источниках такие функции называются тотальными или просто рекурсивными.)

каждая примитивно рекурсивная функция является частично рекурсивной, но обратное неверно.

Введем обозначения:

K_ПРФ – класс примитивно рекурсивных функций;

K_ОРФ – класс общерекурсивных функций;

K_ЧРФ – класс частично рекурсивных функций.

Тогда между этими классами имеется соотношения:

K_ПРФ K_ОРФ K_ЧРФ.

Таким образом, класс ЧРФ – самый богатый из построенных классов вычислимых функций и имеет место следующее включение: K_ЧРФ К_ВФ,

где К_ВФ – класс вычислимых функций.

Тезис Черча–Клини представляет гипотезу, из которой следует обратное включение, т.е. К_ВФ K_ЧРФ.

Таким образом, класс алгоритмически вычислимых функций совпадает с классом частично рекурсивных функций.