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

Оператором примитивной рекурсии R называются подстановки, удовлетворяющие системе уравнений:

f(x1,...,xn)= g(x1,...,xn),

f(x1,...,xn,y+1)= h(x1,...,xn,y,f(x1,...,xn,y)),

которая называется схемой примитивной рекурсии.

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

Примерами примитивно-рекурсивных функций являются:

1. ;

2. ; 0 в противном случае;

3.

Ограниченный оператор минимизации – применяется к предикатам:

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

Еще один ПР-оператор – оператор одновременной рекурсии . C его помощью строится рекурсивное описание сразу нескольких функций от (n-1)-ой переменной, причем значение каждой функции в точке y+1 зависит от значения всех функций в точке y:

Из простейших функций - константы 0, функции следования и функций тождества с помощью операторов суперпозиции и примитивной рекурсии может быть получено огромное разнообразие функций, включающих основные функции арифметики, алгебры и анализа (с поправкой на целочисленность).

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

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

По определению -оператор применяется к предикатам. Поскольку в теории рекурсивных функций истинность предиката всегда связана со справедливостью некоторого равенства, то -оператору можно придать стандартную форму:

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

Пример. Найти функцию, получаемую из с помощью операций примитивной рекурсии.

Решение:

Запишем операторы примитивной рекурсии для функции двух переменных :

Из рекурсивных соотношений получим значения функции на каждом шаге (при ), где у – номер шага.

Итак, выражение для рекурсивной функции - .

Пример. Найти функции, получаемые из данной функции с помощью минимизации по каждой переменной.

Решение:

Минимизируем функцию по переменной , решим уравнение:

.

При получим , что возможно для неотрицательных чисел только при , тогда оператор минимизации по первой переменной определен следующим образом:

0 при ,

не определен в остальных случаях.

Минимизируем функцию по переменной , решим уравнение:

.

При получим , что возможно для неотрицательных чисел только при , тогда оператор минимизации по первой переменной определен следующим образом:

0 при ,

не определен в остальных случаях.

Минимизируем функцию по переменной , решим уравнение:

.

При получим , что возможно для неотрицательных чисел только при , тогда оператор минимизации по первой переменной определен следующим образом:

при ,

не определен в остальных случаях.

Тезис Черча: всякая функция, вычислимая некоторым алгоритмом, частично-рекурсивна. Это утверждение – аналог тезиса Тьюринга: всякий алгоритм может быть реализован машиной Тьюринга, для рекурсивных функций. Из сопоставления этих двух тезисов вытекает следующее утверждение (тезис Черча-Тьюринга): функция вычислима машиной Тьюринга тогда и только тогда, когда она частично-рекурсивна.

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

Множество всех алгоритмов счетно, что означает наличие взаимно-однозначного соответствия между алгоритмами и числами натурального ряда, т.е. функции типа:

: Al N.

Такая функция называется нумерацией алгоритмов, а ее значение (А) – номером алгоритма А при нумерации . Из взаимной однозначности отображения следует, что существует обратная функция -1(n)=Аn, восстанавливающая по номеру n описание алгоритма Аn. Существование нумераций позволяет работать с алгоритмами как с числами.

Все примитивно-рекурсивные функции могут быть реализованы на машине тьюринга

Пример. Реализуем функцию константу 0:

.

Упражнения

1. Составить программу МТ для следующих функций: ; ; ; ;

2.Найти функцию , получаемую из , с помощью операции примитивной рекурсии: , .