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

ÔÍ-12ÔÍ-12ÌÃÒÓМосковский государственный технический университетимени Н.Э. БауманаÌÃÒÓФакультет «Фундаментальные науки»Кафедра «Математическое моделирование»ÌÃÒÓÀ.Í. ÊàíàòíèêîâÈ ÒÅÎÐÈß ÀËÃÎÐÈÒÌÎÂÊîíñïåêò ëåêöèéÔÍ-12Москва2010ÌÃÒÓÔÍ-12ÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12Äëÿ ñòóäåíòîâ êàôåäðû ÈÓ9ÌÃÒÓÌÃÒÓÌÀÒÅÌÀÒÈ×ÅÑÊÀß ËÎÃÈÊÀÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓМы можем дать индуктивное определение примитивно рекурсивной функции.1. Простейшие функции примитивно рекурсивные.n2. Если функции f m , g1n , g2n , . . .

, gmпримитивно рекурсивные, то их суперпозиция — примитивно рекурсивная функция.112ÔÍ-12hn+1 (x1 , x2 , . . . , xn , 0) = f n (x1 , x2 , . . . , xn ),hn+1 (x1 , x2 , . . . , xn , y + 1) = g n+2 (x1 , x2 , . . . , xn , y, hn+1 (x1 , x2 , . . . , xn , y)).ÌÃÒÓВыделим простейшие функции натурального аргумента:1) инкремент f (x) = x+ = x + 1;2) константа нуль 0(x) = 0;n3) проективная функция Im(x1 , x2 , . . . , xn ) = xm , 1 6 m 6 n.Теперь определим простейшие операции над функциями:n1◦ суперпозиция f m (g1n (x1 , x2 , . . .

, xn ), . . . , gm(x1 , x2 , . . . , xn )) (здесь верхний индекс в обозначении функции указывает на ее арность);2◦ примитивная рекурсия, которая из функций f n и g n+2 строит новую функцию hn+1 == R(f n , g n+2 ) в соответствии с равенствами:ÔÍ-1211.1. Примитивно рекурсивные функцииÌÃÒÓÔÍ-12ÌÃÒÓРекурсивные функции — некоторый класс функций одного или нескольких натуральныхаргументов, которые можно получить из некоторого исходного набора функций с помощьюопределенных операций.

Понятие рекурсивная функция“ — удобное математическое описание”класса вычислимых (в том или ином смысле) функций, поскольку дается в привычных в математике терминах операций. В то же время процедура построения рекурсивной функции спомощью последовательности операций сродни построению формулы в том или ином формальном исчислении. Это родство выражают словом конструктивный“. Конструктивный объект”отличается как раз тем, что известно, как он получен в результате конечной процедуры применения простейших операций. Поэтому с точки зрения формализации понятия алгоритм“”рекурсивные функции ничуть не хуже абстрактных машин или нормальных алгорифмов.Хотя нормальные алгорифмы и машины Тьюринга строились в произвольном алфавите, спринципиальной точки зрения выбор алфавита не является существенным, а любой алгоритмможно трансформировать в алгоритм с двухбуквенным алфавитом (это строго проверено врамках нормальных алгорифмов). Это и понятно: множество слов в данном алфавите счетно, так что все слова можно перенумеровать, а любую словарную функцию рассматривать какфункцию натурального аргумента, которая связывает не сами слова, а их номера.

Это былопонятно давно, и с самого начала теория алгоритмов строилась на базе двухбуквенного алфавита. В частности, в рамках рекурсивных функций рассматриваются не произвольные словарныефункции, а словарные функции в двухбуквенном алфавите, которые легко интерпретируютсякак функции натурального аргумента.Различают рекурсивные функции, определенные для любых комбинаций значений аргументов, (т.е. область определения есть Nn ), и частично рекурсивные функции, областьопределения которых составляет лишь часть множества Nn .Начнем с множества исходных (простейших) рекурсивных функций.ÔÍ-12ÔÍ-1211. РЕКУРСИВНЫЕ ФУНКЦИИÌÃÒÓÌÃÒÓÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓÌÃÒÓÌÃÒÓ1133. Если функции f n и g n+2 примитивно рекурсивные, то функция R(f n , g n+2 ) примитивнорекурсивная.Отметим, что примитивно рекурсивных функций счетное множество.

Действительно, простейших функций счетное множество (за счет проективных функций разной арности). С помощью одной операции из простейших мы получаем опять счетное множество. Следовательно,функций, получаемых двумя операциями счетное множество. В результате имеем счетное семейство счетных множеств, которое, как известно, счетно.В то же время всех функций натурального аргумента континуум. Множество Nk при любомk является счетным. Множество всех отображений Nk в множество {0, 1} есть булеан счетногомножества, т.е.

континуум. А множество всех функций k аргументов можно представить какмножество подмножеств в Nk+1 (графиков функций). Значит, не более чем континуум.Из этих соображений вытекает, что подавляющее большинство функций натурального аргумента не является примитивно рекурсивным. Однако конкретный пример функции, не являющейся примитивно рекурсивной, привести не просто. Здесь та же ситуация, что и с функциямидействительного переменного: весь ассортимент функций, которыми мы реально пользуемся —очень малая часть всего многообразия функций.Замечание 11.1.

Проективные функции позволяют из данной примитивно рекурсивнойфункции получать новые функции простой перестановкой или дублированием аргументов.Действительно, если f (x1 , x2 ) примитивно рекурсивна, то примитивно рекурсивными будутf (x2 , x1 ), f (x, x), f (x, 0), посколькуПо этой же причине если функция f (x1 , x2 , .

. . , xn ) является примитивно рекурсивной, то ифункция g(x1 , x2 , . . . , xn , xn+1 ) = f (x1 , x2 , . . . , xn ), полученная добавлением фиктивного аргумента, тоже примитивно рекурсивна:ÌÃÒÓf (x2 , x1 ) = f (I22 (x1 , x2 ), I12 (x1 , x2 )),f (x, x) = f (I12 (x, x2 ), I12 (x, x2 )),f (x, 0) = f (I12 (x, x2 ), 0(I12 (x, x2 ))).ÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-1211. Рекурсивные функциигде ysr обозначает одну из переменных x1 , x2 , .

. . , xn . Как сказано, подстановка может бытьсведена к суперпозиции с помощью соответствующих проективных функций.Пример 11.1. Все постоянные функции примитивно рекурсивные. Действительно, функция 0(x) = 0 простейшая, функция f (x) = 1 есть суперпозия 0(x)+ , а значит, простейшая.Далее применяя суперпозицию уже построенной функции f (x) = k с функцией-инкрементом,получаем f (x) = k + 1.

Постоянные функции от нескольких переменных можно рассматриватькак функции, полученные из постоянных функций одного переменного добавлением фиктивныхаргументов. Отметим, что установленное свойство позволяет формально интерпретироватьпостоянные функции одного переменного как функции, полученные из нульарных“ функций”добавлением фиктивного аргумента.ÔÍ-12Замечание 11.2. Формально с помощью примитивной рекурсии мы можем получить лишьфункцию, имеющую не менее двух аргументов (поскольку функция f имеет хотя бы один аргумент и, значит, n > 1).

Однако использование постоянных функций позволяет построитьследующую рекурсию:h1 (0) = k,h1 (y + ) = g 2 (y, h1 (y)).ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓkm mhm (x1 , x2 , . . . , xn ) = f m (g1k1 (y11 , . . . , yk11 ), . . . , gm(y1 , . . . , ykmm )),ÌÃÒÓÔÍ-12Эти правила можно обобщить, введя следующее понятие. Говорим, что функция hm полученаkmиз функций f m , g1k1 , .

. . , gmс помощью подстановки, еслиÔÍ-12ÔÍ-12g(x1 , x2 , . . . , xn , xn+1 ) = f (I1n+1 (x1 , . . . , xn+1 ), I2n+1 (x1 , . . . , xn+1 ), . . . , Inn+1 (x1 , . . . , xn+1 )).ÌÃÒÓПосле этого получаем нужную функцию: h1 (y) = h2 (y, y) (на самом деле значение h2 не зависитот первого аргумента). Приведенный пример наталкивает на мысль интерпретировать конкретные числа как нульарные функции, что позволяет ввести рассмотренный пример в рамкиопределения примитивной рекурсии.Пример 11.2. Функция s(x, y) = x + y примитивно рекурсивная. Действительно, из определения суммы в рамках формальной арифметики x + 0 = x, x + y + = (x + y)+ .

Из этих равенствзаключаем, что s(x, y) есть примитивная рекурсия:s(x, y + ) = s(x, y)+ = I33 (0, 0, s(x, y)+ ).Вторая формула представляет s(x, y + ) как суперпозицию функций g 3 (x, y, z) = z + = I33 (x, y, z + ),0, 0 и s(x, y).Пример 11.3. Функция m(x, y) = xy также примитивно рекурсивная. Вспомним из формальной арифметики, что m(x, 0) = 0, m(x, y + ) = m(x, y) + x = s(x, m(x, y)). Последняяфункция имеет два аргумента, а должно быть три. Вводим функцию s3 (x, y, z) = s(x, z). Тогдаm(x, y + ) = s3 (x, y, m(x, y)).

Остается показать, что s3 (x, y, z) является примитивно рекурсивной. Ее можно получить с помощью суперпозиции: s3 (x, y, z) = s(I13 (x, y, z), I33 (x, y, z)).ns (x1 , x2 , . . . , xn ) =xnXnnf (x1 , x2 , . . . , xn−1 , i) и m (x1 , x2 , . . . , xn ) =i=0xnYf n (x1 , x2 , . . . , xn−1 , i)i=0примитивно рекурсивны.ÌÃÒÓТеорема 11.1. Если f n (x1 , x2 , . .

. , xn ) примитивно рекурсивна, то функцииÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-12ИУ-9, МЛТА, 2009-10уч.г.Здесь k — произвольное натуральное число. Действительно, рассмотрим постоянную функциюf 1 (ξ) = k и функцию g 3 (ξ, x1 , x2 ) = g 2 (x1 , x2 ). С помощью f 1 и g 3 строим функцию двухпеременных:h2 (ξ, 0) = f 1 (ξ),h2 (ξ, y + ) = g 3 (ξ, y, h2 (ξ, y)).s(x, 0) = I12 (x, 0),ÌÃÒÓÌÃÒÓÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓ114sn (x1 , x2 , . . . , xn−1 , 0) = f n (x1 , x2 , . . . , xn−1 , 0),sn (x1 , x2 , .

. . , xn−1 , k + ) = sn (x1 , x2 , . . . , xn−1 , k) + f n (x1 , x2 , . . . , xn−1 , k + 1).Функция f n (x1 , x2 , . . . , 0) примитивно рекурсивна как суперпозиция проекций и нулевой функции. Выражение sn (x1 , x2 , . . . , xn−1 , k) + f n (x1 , x2 , . . . , xn−1 , k + 1) можно представить в видеg n+1 (x1 , . . . , xn−1 , k, s(x1 , x2 , .

. . , xn−1 , k)), гдеÔÍ-12ÔÍ-12J В данном случаеПоследняя функция, очевидно, примитивно рекурсивная.Доказательство в случае умножения аналогично. IЗамечание 11.3. Доказанную теорему можно немного обобщить, а именно: в условияхтеоремы для любого k примитивно рекурсивными являются функцииnnnf (x1 , x2 , . . . , xn−1 , i) и m (x1 , x2 , . . .

, xn ) =i=0xYn −kf n (x1 , x2 , . . . , xn−1 , i),i=0где предполагается, что сумма нулевая, а произведение равно единице, если нижний пределсуммирования больше верхнего. Возьмем, например, сумму. Очевидно, чтоs (x1 , x2 , . . . , xn ) =xnXf n (x1 , x2 , . . . , i − k).j=kÌÃÒÓnÔÍ-12ÔÍ-12s (x1 , x2 , . . . , xn ) =xXn −kÌÃÒÓÌÃÒÓg n+1 (x1 , . . . , xn−1 , k, m) = f n (x1 , x2 , .