Рекурсивные функции

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

Оператор суперпозиции

Примеры

Оператор примитивной рекурсии

Оператор примитивной рекурсии

Функция называется примитивно – рекурсивной, если она является элементарной или может быть получена из элементарных функций с помощью конечного числа применений операторов тождества, суперпозиции и примитивной рекурсии.
Если некоторые функции являются примитивно-рекурсивными, то в результате применения к ним операторов суперпозиции или примитивной рекурсии можно получить новые примитивно-рекурсивные функции.
Существует три возможности доказательства того, что функция является примитивно-рекурсивной:
а) показать, что заданная функция является простейшей;
б) показать, что заданная функция построена с помощью оператора суперпозиции;
в) показать, что заданная функция построена с помощью оператора примитивной рекурсии.
Оператор примитивной рекурсии

Функция – константа
f(x) = m s(s(s…s(Z(x))…)) m-раз
2. Сложение
f(x,y)=x+y
f(x,0)=x;
f(x,y+1)=x+(y+1)=(x+y)+1=f(x,y)+1
Доказательство:
f(x,0)=g(x)=x=I(x);
f(x,y+1) = h(x,y,z) = h(x,y,f(x,y)) = s(I33 (x,y,f(x,y)))
+2 =R(I11,[s1;I33]).
Примеры доказательства вычислимости функций

3. Умножение
f(x,y)=x*y
f(x,0)=x*0=0;
f(x,y+1)=x*(y+1)=x*y+x=f(x,y)+x
Доказательство:
f(x,0)=g(x)=0=Z(x);
f(x,y+1) = h(x,y,z) = h(x,y,f(x,y)) =x+z= I31 (x,y,f(x,y))+I33 (x,y,f(x,y))
x2 =R(Z,[+;I33,I13])
4. Симметрическая разность (абсолютная величина разности)
Одноместная функция усеченного вычитания единицы определяется рекурсивно:

Операции конечного суммирования и конечного произведения

Оператор минимизации

Использование оператора минимизации
Используя минимизацию можно получать частично –определенные функции из всюду определенных функций.
Пример 2. Пусть g(x) = [x/2]. Найдем функцию f(x), которая получается в результате применения оператора минимизации к этой всюду определенной функции. При каждом конкретном x значение f(x) равно минимальному корню уравнения [y/2] = x. Это уравнение имеет два корня: 2x и 2x+1. Поэтому f(x)=2x.

Тезис Черча
Функция называется частично-рекурсивной (вычислимой по Черчу), если она может быть получена из простейших функций с помощью конечного числа операторов суперпозиции, примитивной рекурсии и минимизации.
Если такие функции оказываются всюду определенными, то они называются общерекурсивными функциями.
Указанные операции могут быть выполнены в любой последовательности и любое конечное число раз. Таким образом, мы не просто задаем функцию, но и точно знаем, как её вычислять.
Очевидно, каждая примитивно рекурсивная функция является частично
рекурсивной, но обратное неверно.
Введем обозначения:
KПРФ – класс примитивно рекурсивных функций;
KОРФ – класс общерекурсивных функций;
KЧРФ – класс частично рекурсивных функций.
Тогда между этими классами имеется соотношения:
KПРФ ⊆ KОРФ ⊆ KЧРФ.