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

. . , hn+1 (x, t1s (y))(11.2)(здесь для упрощения через x обозначена группа переменных x1 , x2 , . . . , xn ).H(x, y) =yYπ(i)h(x,i)i=0Тогдаh(x, k) = pw(k, H(x, y)),k 6 y.(11.3)Докажем, что функция H(x, y) примитивно рекурсивна. ИмеемÔÍ-12ÔÍ-12J Идея доказательства состоит в переходе от конструируемой функции hn+1 к другой в некотором роде аккумулирующей“ функции H n+1 , для которой* H(x, y) содержит в себе информацию”о всех значениях h(x, k), 0 6 k 6 y, причем любое значение h(x, k) извлекается из H(x, y) стандартной процедурой. Тогда из примитивной рекурсивности H мы сможем сделать заключениео примитивной рекурсивности h.

Речь идет о кодировании нескольких чисел в одно.Введем в рассмотрение производящую функциюÌÃÒÓÌÃÒÓТеорема 11.6. Функция, полученная возвратной рекурсией из примитивно рекурсивныхфункций, примитивно рекурсивна.ÔÍ-12На самом деле последняя формула показывает, что функция двух переменных pw(i, x) естьпримитивно рекурсивная функция (правда, надо доказать, что функция xy примитивно рекурсивна).Примитивная рекурсия возникает как реализация метода математической индукции приопределении функции. Базовый вариант метода состоит в следующем. Доказываем какое-тоутверждение, которое можно рассматривать как истинность некоторого предиката R(x). Если:а) R(0) истинно; б) из истинности R(n) следует истинность R(n+1), то предикат R(n) являетсятождественно истинным (наше утверждение верно для любого n).Однако известны различные модификации метода математической индукции, в которых дляустановления истинности R(n + 1) используется истинность нескольких предыдущих значенийпредиката: истинность R(k1 ), R(k2 ), .

. . , R(ks ), где k1 < k2 < . . . < ks 6 n.Аналогичным образом значение целочисленной функции h(x1 , x2 , . . . , xn , y +1) может определяться на основе не только значения h(x1 , x2 , . . . , xn , y), но и некоторых предыдущих значенийh(x1 , x2 , . . .

, xn−1 , ki ) с ki < y. В этом случае говорят о возвратной рекурсии. Точное определение таково. Говорят, что функция hn+1 получается возвратной рекурсией из функций f n ,g n+s+1 , t11 , . . . , t1s , где ti (y) 6 y, i = 1, s, еслиÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓ118y−1,H(x, y + 1) =Yπ(i)h(x,i) · π(y + 1)h(x,y+1) = H(x, y)π(y + 1)h(x,y+1) .i=0Поскольку h(x, y) получена возвратной рекурсией, т.е. по формуле (11.2), заключаем, чтоh(x, y + 1) = g(x, y, h(x, t1 (y)), . . .

, h(x, ts (y)) == g(x, y, pw(t1 (y), H(x, y)), . . . , pw(ts (y), H(x, y)) = G(x, y, H(x, y)),ÌÃÒÓÌÃÒÓH(x, 0) = π(0)h(x,0)G(x, y, z) = g(x, y, pw(t1 (y), z), . . . , pw(ts (y), z).В результатеH(x, y + 1) = H(x, y) π(y+1)G(x,y,H(x,y))и функция H(x, y) получена примитивной рекурсией. Следовательно, H(x, y) примитивно рекурсивна. Согласно формуле (11.3) при k = y, функция h(x, y) также примитивно рекурсивна.

IВ доказательстве мы опять через x обозначаем группу неизменных аргументов x1 , x2 , . . . , xn .ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12*ÔÍ-12ÔÍ-12гдеÌÃÒÓÌÃÒÓÌÃÒÓ119Оказывается, что класс примитивно рекурсивных функции не охватывает множество всехвычислимых функций (в частности, вычислимых по Тьюрингу или Маркову). Первое обстоятельство — примитивно рекурсивные функции всюду определены. Но есть и второе, болеесерьезное обстоятельство, связанное с ростом функций.Функция Аккермана. Рассмотрим функцию B(x, y), называемую функцией Аккермана, которая определяется индуктивно следующими формулами:B(0, y) = 2 + y,B(x, 0) = sg(x − 1), x > 1,B(x + 1, y + 1) = B(x, B(x + 1, y)),B(0, y) = 2 + y,B(1, y) = 2y,yB(2, y) = 2 ,2·2··B(3, y) = 2(y раз).Видно, что с ростом x функция B(x, y) по y растет все быстрее. В то же времяB(x, 1) = 2 + sg(x),B(x, 2) = 4,(11.4)ÌÃÒÓт.е.

при y 6 2 функция B(x, y) как функция переменного x ограничена. ОднакоB(0, 3) = 5,B(1, 3) = 6,B(2, 3) = 8,B(3, 3) = 16,ÔÍ-12Из формул видно, что для вычисления B(x + 1, y + 1) необходимо знать B(x + 1, y) (этоукладывается в операцию примитивной рекурсии) и все значения B(x, z), поскольку мы незнаем, какое конкретно z = B(x + 1, y) будет использовано. В действительности вычислениезначений функции идет в общем порядке возрастания пар x, y, но конкретный порядок перебораэтих пар устроен весьма сложно. Тем не менее эта функция вычислима.Непосредственно из формул вытекают соотношенияÌÃÒÓÔÍ-12ÔÍ-1211.3.

Частично рекурсивные функцииB(x, 0) = sg(x),ÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-1211. Рекурсивные функции...,и видно, что функция B(x, 3) растет.B(x, y) < B(x, y + 1), x ∈ N,B(x, y + 1) 6 B(x + 1, y), x ∈ N.J Сначала докажем неравенство B(x, y) > y + 2, верное при y > 2. При x = 0 оно верносогласно определению функции Аккермана. Оно также верно при любом x > 0 и при y = 2,поскольку B(x, 2) = 4. Предположим, что оно верно при данном значении x для любого y > 2и при значениях x + 1 и y > 2. ТогдаÔÍ-12ÔÍ-12Теорема 11.7. Функция B(x, y) удовлетворяет условиямНаконец, покажем, что B(x + 1, y) > B(x, y + 1) при y > 3.B(x + 1, y) = B(x, B(x + 1, y − 1)) > B(x, y − 1 + 2),поскольку B(x + 1, y − 1) > y + 1 при y > 3 и B(x, z1 ) > B(x, z2 ) при z1 > z2 .

IМожно показать, что каждая примитивно рекурсивная функция f (x1 , x2 , . . . , xn ) при некотором достаточно большом m удовлетворяют неравенствуkxk > 1.ÌÃÒÓÔÍ-12f (x1 , x2 , . . . , xn ) 6 B(m, kxk),ÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12Теперь докажем неравенство B(x, y + 1) > B(x, y).

Оно очевидно при x = 0. Оно такжеверно, согласно (11.4), при любом x и при y < 2. Пусть x > 0 и y > 2. Тогда B(x, y) > y + 2 > 2иB(x, y + 1) = B(x − 1, B(x, y)) > B(x, y) + 2 > B(x, y).ÌÃÒÓÌÃÒÓB(x + 1, y + 1) = B(x, B(x + 1, y)) > B(x + 1, y) + 2 > y + 4 > y + 2.ÌÃÒÓÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ИУ-9, МЛТА, 2009-10уч.г.где kxk = max {x1 , x2 , . . . , xn }. Для этого достаточно проверить простейшие функции (дляних m = 0) и сохранение свойства при суперпозиции и примитивной рекурсии.Указанным свойством не обладает диагональная функция Аккермана A(x) = B(x, x).Действительно, тогда должно было бы выполняться неравенство B(x, x) 6 B(m, x). Однакоэто неверно при x > m.

Значит, диагональная функция Аккермана не является примитивнорекурсивной.Функция Аккермана — пример вычислимой функции, не являющейся примитивно рекурсивной. Существование таких функций указывает на то, что класс примитивно рекурсивныхфункций должен быть расширен. Это требование разрешается введением еще одной операции.Скажем, что n-арная функция hn получена из (n + 1)-местного предиката P n+1 с помощьюоператора минимизации (µ-оператора), еслиhn (x1 , x2 , .

. . , xn ) = µyP n+1 (x1 , x2 , . . . , xn , y),где символ µ означает выбор первого номера y, при котором P (x1 , x2 , . . . , xn , y) является истинным (т.е. равен единице).Отметим, что оператор µ уже был использован, но с дополнительным ограничением, когдаy не превышал одной из переменных (в силу этого такой вариант называют операторомограниченной минимизации). Оператор ограниченной минимизации не выводит из классапримитивно рекурсивных функций (это было установлено). Оператор общей минимизации уженельзя выразить через операции композиции и примитивной рекурсии.ÔÍ-12Определение 11.1. Скажем, что целочисленная функция f частично рекурсивна, если онаудовлетворяет одному из условий:1) примитивно рекурсивная функция частично рекурсивна;2) функция, полученная с помощью оператора минимизации из частично рекурсивной функции, является частично рекурсивной.Смысл этой функции очевиден: s(x, y) = x − y, если x > y, и s(x, y) не определена, если x < y.Теорема 11.8.

Любая частично рекурсивная функция вычислима по Маркову (Тьюрингу).J Понятия вычислимости по Маркову и Тьюрингу эквивалентны. Остановимся на вычислимости по Маркову, для чего будем опираться на сочетания нормальных алгорифмов. Надодоказать, что базисные функции вычислимы по Маркову и что операции образования новыхфункций сохраняют свойство вычислимости по Маркову.Очевидно, что простейшие функции вычислимы по Маркову. Также легко установить, чтокомпозиция функций, вычислимых по Маркову, является вычислимой по Маркову: достаточносделать соединение нормальных алгорифмов в соответствии с рис. 11.1, на котором алгоритмZ0 удаляет лидирующий нуль в результате, представленном как γ-система.ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12s(x, y) = µz P (x, y, z).ÌÃÒÓÌÃÒÓПример 11.4.

Рассмотрим предикат P (x, y, z) = (x = y + z). С помощью него и оператораминимизации определим функциюÔÍ-12Частичная рекурсивная функция при некоторых значениях аргументов может быть не определена. Пусть при данных x1 , x2 , . . . , xn значение предиката P (x1 , x2 , . . .