11 - Рекурсивные функции. Примитивно рекурсивные функции. Предикаты, простые числа и возвратная рекурсия. Частично рекурсивные функции (Конспект лекций), страница 5

, xn ), вычислимая по Тьюрингу. Соответствующая машина Тьюринга преобразует слово, представляющее собой запись аргументов функции в палоч”ной“ системе, в слово, представляющее собой запись результата в той же палочной“ системе.”Эту машину представляет некоторая функция частично рекурсивная g(x) одного переменного, вкоторой исходное слово X и результирующее слово Y интерпретируются как запись чисел n(X)и n(Y ) в системе исчисления с основанием m. Исходную функцию f (x1 , x2 , . . . , xn ) можно представить как композицию трех функций, первая преобразует набор чисел x1 , x2 , . . .

, xn в числоn(X), вторая — это g(x), третья преобразует число n(Y ) в результат f (x1 , x2 , . . . , xn ). В светеэтого, чтобы доказать частичную рекурсивность функции f , достаточно доказать частичнуюрекурсивность двух преобразований. Первое преобразование описывается формулойÌÃÒÓÔÍ-12ÌÃÒÓ123ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-1211. Рекурсивные функцииÌÃÒÓÌÃÒÓÌÃÒÓÔÍ-12ИУ-9, МЛТА, 2009-10уч.г.всех функций fl (x1 , .

. . , xn ) = U n+1 (l, x1 , . . . , xn ), l ∈ N. В качестве такого множества будемnnвсех общевсех частично рекурсивных функций, множество Fоррассматривать множество Fчрnрекурсивных функций и множество Fпр всех примитивно рекурсивных функций.Теорема 11.11. 1. Существует универсальная частично рекурсивная функция для множеnства Fчр.n2.

Существует общерекурсивная функция, универсальная для множества Fпр, причем ниодна такая функция не является примитивно рекурсивной.nне имеет универсальной общерекурсивной функции.3. Множество FорПервое утверждение теоремы — очевидное следствие из теоремы Клини. Два других утверждения менее очевидны. Отметим, что из второго утверждения вытекает, что существуютобщерекурсивные функции, не являющиеся примитивно рекурсивными.Универсальные частично рекурсивные функции в определенном смысле имеют максимальную область определения.

Скажем, что функция g n является доопределением функции f n , еслиее область определения включает область определения f n и на области определения f n значениядвух функций совпадают.nТеорема 11.12. Никакая универсальная частично рекурсивная функция для множества Fорне может быть доопределена до общерекурсивной.g(x1 , x2 , . . . , xn ) = U n+1 (l, x1 , x2 , . . . , x2 ) = Gn+1 (l, x1 , x2 , . . .

, x2 ).Но, учитывая определение функции g, заключаем, чтоÌÃÒÓJ Пусть U n+1 — универсальная частично рекурсивная функция и Gn+1 — ее общерекурсивноедоопределение. Рассмотрим функцию g(x1 , x2 , . . . , xn ) = Gn+1 (x1 , x1 , x2 , . . . , xn ) + 1. Это общерекурсивная функция n переменных и должна выражаться через универсальную функцию.Следовательно, при некотором lÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓ124а это невозможно.

InКонечно, множество Fоримеет универсальную частично рекурсивную функцию (таковойnявляется любая универсальная функция для множества Fчр). Согласно теореме 11.12 средиnуниверсальных функций для множества Fор нет общерекурсивных.Следствие 11.1. Существует одноместный частично рекурсивный предикат, не имеющийобщерекурсивных доопределений.J Выберем какую-нибудь универсальную общерекурсивную функцию U n+1 и положим f (x) == sg(U n+1 (x, x, .

. . , x)). Пусть эта функция имеет общерекурсивное доопределение v(x). Образуем функцию n переменных, введя фиктивные переменные: g(x1 , x2 , . . . , xn ) = v(x1 ). Этафункция, как частично рекурсивная, выразима через универсальную. Поэтому при некотором lВ частности,sg(U n+1 (l, l, . . . , l)) = U n+1 (l, l, l, . . . , l),а это равенство неверно. IÔÍ-12sg(U n+1 (x, x, . . . , x)) = v(x) = U n+1 (l, x, x2 , . . . , xn ).ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓGn+1 (l, l, . . . , l) + 1 = Gn+1 (l, l, .

. . , l),ÌÃÒÓÔÍ-12В частности,ÔÍ-12ÔÍ-12Gn+1 (x1 , x1 , x2 , . . . , xn ) + 1 = Gn+1 (l, x1 , x2 , . . . , x2 ).ÌÃÒÓОпределение 11.2. Разрешимое множество (также рекурсивное множество) —любое подмножество множества натуральных чисел, характеристическая функция которогоявляется общерекурсивной. Если характеристическая функция примитивно рекурсивна, томножество называют примитивно рекурсивным.Пример 11.5. Пустое множество, множество всех натуральных чисел примитивно рекурсивны, поскольку их характеристические функции, будучи постоянными, примитивно рекурсивны. Множество четных чисел примитивно рекурсивно: его характеристическая функцияописывается формулой f (x) = 1 −· (x mod 2).Теорема 11.13.

Если множества A и B разрешимы (примитивно рекурсивны), то и множества A ∩ B, A ∪ B, A \ B, A = N \ A разрешимы (примитивно рекурсивны).J Утверждение теоремы вытекает из следующих представлений теоретико-множественных операций через характеристические функции:χA∪B = χA + χB −· χA χB ,χA\B = χA (1 −· χB ),χA = 1 −· χA .IПример 11.6. Одноточечное множество A = {a} примитивно рекурсивно, поскольку егохарактеристическая функция χA (x) = sg(|x − a|) примитивно рекурсивна.

Конечное множествопримитивно рекурсивно как конечное объединение примитивно рекурсивных множеств.Теорема 11.14. Если общерекурсивная (примитивно рекурсивная) функция f удовлетворяет условию f (x) > x, x ∈ N, то множество ее значений разрешимо (примитивно рекурсивно).χA (x) = ∃(y 6 x)(f (y) = x).Пример 11.7. Как было показано, функция Pr(x), значением которой является простоечисло с номером x, примитивно рекурсивна.

Множество ее значений — множество всех простыхчисел — является примитивно рекурсивным, поскольку Pr(x) > x, x ∈ N.Определение 11.3. Множество A ⊂ N называется рекурсивно перечислимым, если оносовпадает с областью определения некоторой частично рекурсивной функции.ÔÍ-12Из этой формулы вытекает общерекурсивность (примитивная рекурсивность) χA в случае, когда f (y) общерекурсивна (примитивно рекурсивна). IÌÃÒÓJ Суть в механизме проверки, является ли данное число x значением функции f . При y > xимеем f (y) > y > x, так что равенство x = f (y) надо проверять только для значений y,не превышающих x.

Характеристическую функцию множества A значений функции f можнозаписать с помощью ограниченного квантора существования:ÔÍ-12χA∩B = χA χB ,ÌÃÒÓÔÍ-12ÌÃÒÓРазрешимость множества равносильна вычислимости его характеристической функции. Понятие вычислимой функции мы отождествляем с понятием частично рекурсивной функции. Дляцелей описания множеств нужны всюду определенные, т.е. общерекурсивные функции. Этообъясняет следующее определение.ÔÍ-12ÔÍ-12Под разрешимым понимают множество, для которого можно построить разрешающий алгоритм, т.е. алгоритм, который для любого объекта a определяет, принадлежит a множествуили нет. Мы рассматриваем подмножества множества натуральных чисел. Ясно, что срединих есть неразрешимые (на всех алгоритмов не хватает).Каждое подмножество A в N можно описать характеристической функцией(1, x ∈ A;χA (x) =0, x ∈/ A.ÌÃÒÓÌÃÒÓ11.5.

Разрешимые и перечислимые множестваÌÃÒÓÔÍ-12ÌÃÒÓ125ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-1211. Рекурсивные функцииÌÃÒÓТеорема 11.16. Непустое множество рекурсивно перечислимо тогда и только тогда, когдаоно является областью значений некоторой одноместной примитивно рекурсивной функции.J Доказательство в одну сторону основано на той же идее, что и предыдущая теорема, толькоквантор существования уже не будет ограниченным и вместо него лучше использовать операторминимизации. Итак, пусть A — множество значений примитивно рекурсивной функции f .Сформируем двуместный предикат f (y) = x и используем оператор минимизации:g(x) = µ(y)(f (y) = x).ÔÍ-12Теорема 11.17.

Если A и B рекурсивно перечислимы, то A ∩ B и A ∪ B рекурсивноперечислимы.ÌÃÒÓгде b — один из фиксированных элементов множества, которое по условию непусто. Очевидно,что множество значений функции g совпадает с рассматриваемым множеством. IÔÍ-12Функция g(x) частично рекурсивна, так как получена с помощью оператора минимизации изпримитивно рекурсивного предиката. Она не определена, если x не является значением функцииf , и имеет значение наименьшего числа y, для которого f (y) = x, если x является значениемфункции f .В другую сторону доказательство сложнее. Речь идет о перестройке процедуры, порождающей частично рекурсивную функцию. Согласно теореме Клини о нормальной форме, частичнорекурсивная функция одного переменного может быть получена из примитивно рекурсивногопредиката одним оператором минимизации (функция F 1 в нормальной форме не играет роли).Итак, пусть частично рекурсивная функция f (x) получена с помощью примитивно рекурсивного предиката P (x, y) согласно формуле f (x) = µy(P (x, y)).

Согласно этой формуле, числоx принадлежит области определения функции f , если для этого x при некотором y предикатP (x, y) имеет значение 1. Надо пересчитать все такие x, может быть, с повторением. Для этогодостаточно перенумеровать пары (x, y) в одну последовательность, т.е. сформировать функцию c(x, y). Этой функции соответствуют функции l(n) и r(n), вычисляющие по номеру парылевую и правую компоненты. Все три функции при подходящем выборе нумерации примитивнорекурсивны (это можно показать). Далее создаем функцию(l(n), P (l(n), r(n));g(n) =b,¬P (l(n), r(n)),ÌÃÒÓÔÍ-12ÌÃÒÓJ Согласно условию характеристическая функция χA множества A общерекурсивна.

Составимфункцию fA (x) = µy(χA (x)) + 1. Если χA (x) = 0, то значение оператора минимизации неопределено и функция fA (x) не определена. Если χA (x) = 1, то µy(χA (x)) = 0 и значениеfA (x) есть 1. Следовательно, область определения функции fA совпадает с множеством A и этомножество рекурсивно перечислимо. IÔÍ-12ÔÍ-12Теорема 11.15. Разрешимое множество рекурсивно перечислимо.ÌÃÒÓÌÃÒÓОпределение можно переформулировать и так: множество A рекурсивно перечислимо, еслисуществует частично рекурсивная функция f , удовлетворяющая условию: f (x) = 1, если x ∈ A,и f (x) не определена, если x ∈/ A. Действительно, если A есть область определения частичнорекурсивной функции g, то указанному требованию удовлетворяет функция f (x) = 1(g(x)).Нетрудно понять, что понятие рекурсивно перечислимого множества более широкое по сравнению с понятием разрешимого множества.