13.Рекурсивные функции и их построение из простейших.

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

А). Функция константа

Б) Функция непосредственного следования

В) Тождественная функция

14.Операторы подстановки, рекурсии и минимизации. Частично рекурсивные функции.

Для построения более сложных функций из первичных используют следующие операции.

• Операция подстановки. Эта операция заключается в том, что вместо каких-то переменных функции подставляют другие функции от тех же или иных переменных.

Пример. Пусть и . Тогда подставив вместо переменной х функцию g(у), получим новую функцию:

• Операция примитивной рекурсии. Эту операцию можно представить следующим образом

Пример 1. Пусть - известная вычислимая функция, т.е. известен алгоритм вычисления этой функции для произвольного х. Определим новую функцию f(x) следующим образом:

Это и есть определение функции с помощью операции примитивной рекурсии.

Например, пусть

Это есть определение целочисленного умножения. Так

f(3,3)=f(3,2)+3=f(3,1)+3+3=3+3+3=9.

Пример 2. и

Это определение позволяет находить значение . В самом деле, рассмотрим следующий пример вычисления 3² .

f(3,1+1)=h(3,f(3,1))=h(3,3)=h(2+1,3)=h(2,3)+3=h(1+1,3)+3=h(1,3)+3+3=3+3+3=9

Определение. Функция, определяемая из простейших с помощью операций подстановки и/или примитивной рекурсии, называется примитивно рекурсивной.

Имеется еще одна операция для построения рекурсивных функций. Правда, эта операция не всегда дает результат или, как говорят, не является полностью определенной (тотальной). Эта операция называется операцией минимизации (взятия минимального корня). Ее определение таково.

• 

Эту операции можно для простоты обозначить как _y f(x,y).

Пример 3. Пусть . Тогда _y f(3,y)=2.

Определение. Функция, определяемая из простейших с помощью операций подстановки примитивной рекурсии и минимизации, называется частично рекурсивной.

15.Тезис Черча.

Тезис Черча. Класс всех частично вычислимых функций над положительными целыми числами совпадает с классом всех частично рекурсивных функций.

Иными словами, каждая арифметическая функция, для которой имеется машина Тьюринга, является одновременно и рекурсивной, и наоборот – если функция является частично-рекурсивной, то она одновременно и вычислима.

С помощью тезиса Черча можно устанавливать вычислимость новых функций, используя уже построенные вычислимые функции. Поэтому, если f_x - вычислимая функция с номером x , то h(x)= f_x (x)+1 частично-вычислимая функция.