2. Примитивно рекурсивные отношения.

Отношение называется примитивно рекурсивным (сокращенно ПРО), если примитивно рекурсивна характеристическая функ­ция

, где

Пример1. Отношения равенства x = у и делимо­сти х|у (х делит у) примитивно рекурсивны. Действительно, ха­рактеристические функции χ₌(x,у) = (|х — у|) и X_| (x,y)= (rest(y, x)) примитивно рекурсивны.

Покажем, что теоретико-множественные операции над ПРО сохраняют примитивную рекурсивность.

Пусть Р, Q — некоторые отношения. Положим , , ,

Предложение 2. Если P,Q и - прими­тивно рекурсивные отношения, то отношения , , , , примитивно рекурсивны.

Доказательство. Поскольку по условию примитив­но рекурсивны функции , , примитивно ре­курсивными являются также характеристические функции , . Теперь из соотношений и вытекает примитивная рекурсивность характеристи­ческих функций и □

Записи ( ) и ( ) называются ограниченными кванторами. Пусть Ρ — некоторое отношение. Обозначим через ( )Ρ(x₁,... ,x_n,z) (k + 1)-местное отношение { }, через ( )Ρ(x₁,... ,x_n,z) (k + 1)-местное отношение { }

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

Предложение 3. Если Ρ — примитивно рекурсивное отношение, то отношения Q₁=( )Ρ(x₁,... ,x_n,z) и Q₂= ( )Ρ(x₁,... ,x_n,z) примитивно рекурсивны.

Доказательство. Примитивная рекурсивность отно­шений Q₁ и Q₂ вытекает из следующих соотношений:

где

Пример 1. Поскольку справедливо соотношение (x+z = у), отношение примитивно рекурсивно в силу предложения 3.

2. Аналогично из вытекает примитивная рекурсивность отношения x< у.

Пусть ( ) — некоторая k-местная операция на множестве Ν, Ρ . Обозначим через k-местную операцию, значение которой на наборе x равно

Оператор, ставящий в соответствие каждой операции -к-местной операции и отношению Ρ операцию называется оператором ограниченной минимизации.

Предложение 4. Если ( ) - ПРФ, Ρ - ПРО, то - ПРФ.

Пример 3. Функция которая каждому натураль­ному числу x ставит в соответствие целую часть от квадратного корня из х, примитивно рекурсивна в силу предложения 4, поскольку .

Примеры ПРФ. Нумерации кортежей натуральных чисел. Нумера­цией множества X называется любая сюръекция ν: X —>N. Представлена "диагональная" нумерация множества Ν², устанавливающая биекцию между множествами N и Ν². Отображение с : Ν² —> Ν, ставящее в соответствие каждой паре натуральных чисел (х, у) ее "диагональный" номер с(х, у), называется канторовской нумерующей функцией.

Т.е. пары (0,0), (0,1), (1,0), (0,2), (1,1), (2,0), (0,3),

По но­меру n = с(х, у) однозначно определяются его левая координата 1(n) =x и правая координата r(n) = у.

Функции с, l и r удовлетворяют следующим тождествам:

с(1(п),r(п)) = п, 1(с(х,у)) = х, r(с(х,у)) = у.

Данные функции ПРФ.

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

Будем говорить, что функция f( ) получается из функций g( , у) и h( , у) с помощью оператора минимизации М, и обозначать f( ) = μy (g( , у) h( , у)) или f( ) ⁼ M(g( ,y),h( ,y)), если выполнено следующее условие_: f( ) определено и равно у тогда и только тогда, когда опре­делены g( , 0), h( , 0), ..., g( , у), h( , у) и справедливы соотно­шения g( , i) > h( , i), i = 0,..., у - 1, g( , у) h( , у).

Функция f : X —> N^k называется частично рекурсивной (ЧРФ), если она может быть получена из простейших ПРФ с помощью конечного числа применений операторов S, R и М. Частично рекурсивная функция называется рекурсивной (РФ), если она всюду определена.

Обозначим через М°(g, h) значение М(g, h), если функции g, h и М(g, h) всюду определены.

Функция f: X —> N^k называется общерекурсивной (ОРФ), если она может быть получена из простейших ПРФ с помощью конечного числа применений операторов S, R и М°.

Класс ЧРФ строго содержит класс РФ, поскольку, например, нигде не определенная функция f(x) = μy (s(x) < x) частично рекурсивна.

Класс РФ совпадает с классом ОРФ.

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

Вместо оператора R можно использовать арифметические операции, тогда

Предложение 1 Любая ЧРФ она может быть получена из простейших ПРФ и функций + и с помощью конечного числа применений операторов S, М.

Из определения ПРФ и ЧРФ следует, что любая ЧРФ является вычислимой, обратное носит имя Черча: любая вычислимая частичная функция частично рекурсивна.

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