Доказать что следующие функции примитивно рекурсивны

Примитивно-рекурсивные функции. Примеры решений

На этой странице вы найдете готовые примеры заданий по проверки примитивной рекурсивности функции .

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

Полезная страница? Сохрани или расскажи друзьям

Задачи и решения о рекурсивных функциях

Задача 1. Пользуясь определением примитивно рекурсивной функции, показать что числовая функция $f(x)$ примитивно рекурсивна. $f(x)=x!$

Задача 2. Доказать примитивную рекурсивность следующей функции $f(x,y)=x\cdot y$.

Задача 3. Доказать, что заданная функция, определенная для натуральных аргументов и принимающая натуральные значения, является примитивно рекурсивной. $f(x,y)=x^y+x$.

Подробно решаем задачи по дискретной математике

Примитивно-рекурсивные функции

Введем базис простых операций:

• Константа 0
• Функция следования $x’=x+1$ (иногда обозначается $S(x)=x+1$)
• Функция проекции $I_m^n(x_1,x_2. x_n)=x_m$

Оператором суперпозиции (оператором подстановки) $S_m^n$ называется подстановка в функцию от $m$ переменных $m$ функций от $n$ одних и тех же переменных. Суперпозиция дает новую функцию от $n$ переменных.

Оператор примитивной рекурсии $R_n$ определяет $(n+1)$ – местную функцию $f$ через $n$ – местную функцию $g$ и $(n+2)$ – местную функцию $h$ так:

$$ f(x_1. x_n,0)=g(x_1. x_n),\\ f(x_1. x_n,y+1)=h(x_1. x_n, y, f(x_1. x_n,y). $$

Эта пара равенств называется схемой примитивной рекурсии и обозначается, как

Данная схема определяет функцию $f$ рекурсивно не только через другие функции, но и через значения самой $f$ в предшествующих точках. Существенным в операторе примитивной рекурсии является то, что независимо от числа переменных в $f$ рекурсия ведется только по одной переменной $y$, а остальные $n$ переменных $x_1. x_n$ на момент применения схемы рекурсии зафиксированы и играют роль параметров.

Функция называется примитивно-рекурсивной, если она может быть получена из константы 0, функции $x’$ и функции $I_m^n$ с помощью конечного числа применений операторов суперпозиции и примитивной рекурсии.

Основные примитивно-рекурсивные функции: сложение $a+b$, умножение $ab$, возведение в степень $a^b$, симметрическая разность $|a-b|$.

Примитивно рекурсивная функция

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

К числу исходных примитивно рекурсивных функций относятся функции следующих трёх видов:

• Нулевая функция O одного переменного, сопоставляющая любому натуральному числу значение 0.
• Функция следования S одного переменного, сопоставляющая любому натуральному числу x непосредственно следующее за ним натуральное число x + 1 .
• Функции I n m ^> , где 0 < m ⩽ n , от n переменных, сопоставляющие любому упорядоченному набору x 1 , . . . x n . x_> натуральных чисел число x m из этого набора.

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

• Пусть f — примитивно рекурсивная функция от m переменных, а g₁. g_m — упорядоченный набор примитивно рекурсивных функций от n переменных каждая. Тогда результатом подстановки функций g_k в функцию f называется функция h от n переменных, сопоставляющая любому упорядоченному набору x 1 , . . . x n . x_> натуральных чисел число

• Пусть f — примитивно рекурсивная функция от n переменных, а g — примитивно рекурсивная функция от n+2 переменных. Тогда результатом применения оператора примитивной рекурсии к паре функций f и g называется функция h от n+1 переменной вида

Примеры [ ]

Укажем на ряд широко известных арифметических функций, допускающих рассмотрение в качестве примитивно рекурсивных.

• Сложение двух натуральных чисел может быть рассмотрено в качестве примитивно рекурсивной функции двух переменных, получаемой в результате применения оператора примитивной рекурсии к функциям I 1 1 ^> и f, вторая из которых получается подстановкой основной функции I 3 3 ^> в основную функцию S :

• Умножение двух натуральных чисел может быть рассмотрено в качестве примитивно рекурсивной функции двух переменных, получаемой в результате применения оператора примитивной рекурсии к функциям O и f, вторая из которых получается подстановкой основных функций I 3 1 ^> и I 3 3 ^> в функцию сложения:

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

Границы понятия [ ]

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

Следует, однако, заметить, что произвольная рекурсивная функция от n переменных может быть получена из примитивно рекурсивной функции от n+1 переменной применением оператора минимизации.

Литература [ ]

• Гильберт Д, Бернайс П. Основания математики, Т. 1. — М.: Наука, 1979.
• Клини С. К. Введение в метаматематику. — М., 1957.
• Петер Р. Рекурсивные функции — ИЛ, 1954.

cs:Primitivně rekurzivní funkce he:פונקציה פרימיטיבית רקורסיבית

Примитивно рекурсивные функции

Рассмотрим примитивы, из которых будем собирать выражения:

[math]\mathbb \rightarrow \mathbb[/math] , [math]\mathrm(x) = 0[/math]

[math]\mathbb \rightarrow \mathbb[/math] , [math]\mathrm(x) = x'[/math] , где [math]x’ = x + 1[/math] .

[math]\mathrm: \mathbb^ \rightarrow \mathbb[/math] , [math]\mathrm (x_1, \ldots, x_n) = x_i[/math]

Если [math]\mathrm: \mathbb^ \rightarrow \mathbb[/math] и [math]\mathrm, \ldots, \mathrm: \mathbb^ \rightarrow \mathbb[/math] , то [math]\mathrm\langle<>\mathrm,\mathrm, \ldots, \mathrm\rangle: \mathbb^ \rightarrow \mathbb[/math] . При этом [math]\mathrm\langle<>\mathrm,\mathrm, \ldots, \mathrm\rangle (x_1, \ldots, x_m) = \mathrm(\mathrm(x_1, \ldots, x_m), \ldots \mathrm(x_1, \ldots, x_m))[/math]

Если [math]\mathrm: \mathbb^ \rightarrow \mathbb[/math] и [math]\mathrm:\mathbb^ \rightarrow \mathbb[/math] , то [math]\mathrm\langle<>\mathrm,\mathrm\rangle: \mathbb^ \rightarrow \mathbb[/math] , при этом [math]\mathrm\langle<>\mathrm,\mathrm\rangle (x_1, \ldots, x_n,y) = \left\ \mathrm(x_1, \ldots, x_n) & y = 0\\ \mathrm(x_1, \ldots, x_n,y-1,\mathrm\langle<>\mathrm,\mathrm\rangle(x_1, \ldots, x_n,y-1)) & y \gt 0 \end\right.[/math]

Если [math]\mathrm: \mathbb^ \rightarrow \mathbb[/math] , то [math]\mu \langle<>\mathrm\rangle: \mathbb^ \rightarrow \mathbb[/math] , при этом [math]\mu \langle<>\mathrm\rangle (x_1, \ldots, x_n)[/math] — такое минимальное число [math]y[/math] , что [math]\mathrm(x_1, \ldots, x_n,y) = 0[/math] . Если такого [math]y[/math] нет, результат данного примитива неопределен.

Определение:

Если некоторая функция [math]\mathbb^ \rightarrow \mathbb[/math] может быть задана с помощью данных примитивов(англ. primitive), то она называется рекурсивной (англ. recursive).

Примитивно рекурсивные функции

Определение:

Примитивно рекурсивными (англ. Primitively recursive) называют функции, которые можно получить с помощью правил [math]1[/math] — [math]5[/math] .

Заметим, что если [math] \mathrm [/math] — [math]n[/math] -местная примитивно рекурсивная функция, то она определена на всем множестве [math] \mathbb^ [/math] , так как [math] \mathrm [/math] получается путем правил преобразования из всюду определенных функций, и правила преобразования не портят всюду определенность. Говоря неформальным языком, рекурсивные функции напоминают программы, у которых при любых входных данных все циклы и рекурсий завершатся за конечное время. Если же говорить формально, то это свойство рекурсивных функций называется тотальностью.

Определение:

Тотальность (англ. Total Function) — функция, определенная для всех возможных входных данных.

Благодаря проекторам мы можем делать следующие преобразования:

• В рекурсии не обязательно вести индукцию по последнему аргументу. Следует из того что мы можем с помощью проекторов поставить требуемый аргумент на последнее место.
• В правиле подстановки можно использовать функции с разным числом аргументов. Например, подстановка [math] \mathrm(x,y) =\mathrm(\mathrm(y),\mathrm(x,x,y)) [/math] эквивалентна [math] \mathrm(x,y,z) = \mathrm(\mathrm(\mathrm(x,y)),\mathrm(\mathrm(x,y),\mathrm(x,y),\mathrm(x,y))) [/math] , но если [math] \mathrm [/math] не константная функция то все подставляемые функции должны иметь хотя бы один аргумент.

Арифметические операции на примитивно рекурсивных функциях

n-местный ноль

[math] \textbf 0 [/math] — функция нуля аргументов.

[math] \textbf 0^(y) = \mathrm(y) [/math]

[math] \textbf 0^(x_1,\ldots,x_,y) = \mathrm(y) [/math]

Теперь вместо функции [math]\mathrm(x)[/math] будем использовать константу [math]\textbf 0[/math] , обозначив ее как [math]\mathrm(x)[/math] .

Константа [math] \textbf M [/math]

[math] \textbf M^n [/math] — [math]n[/math] -местная константа, получается аналогичным к [math] \textbf 0^n [/math] образом.

Сложение

[math] \mathrm(x, y) = \mathrm\langle<>\mathrm,\mathrm\rangle(x,y)[/math] , где

[math] \mathrm(x) = x [/math]

[math] \mathrm(x, y, z) = \mathrm(z) [/math]

[math] \mathrm\langle<>\mathrm,\mathrm\rangle (x,y) = \left\ \mathrm(x) & y = 0\\ \mathrm(x, y-1,\mathrm\langle<>\mathrm,\mathrm\rangle(x, y-1)) & y \gt 0 \end\right.[/math]

[math]=\left\ x & y = 0\\ \mathrm(\mathrm \langle<>\mathrm,\mathrm\rangle(x, y-1)) & y \gt 0 \end\right.[/math]

[math]=\left\ x & y = 0\\ \mathrm(\mathrm(x, y-1)) & y \gt 0 \end\right. [/math]

Можно преобразовать в более простой вид.

[math] \mathrm(x,0) = x [/math]

[math] \mathrm(x,y) = \mathrm (\mathrm(x,y-1)) [/math]

Умножения

[math] \mathrm(x,0) = \mathrm(x) [/math]

Вычитания

Если [math] x \leqslant y [/math] , то [math] \mathrm(x,y) = 0 [/math] , иначе [math] \mathrm(x,y) = x — y [/math] .

Рассмотрим сначала вычитания единицы [math] \mathrm>(x) = x — 1 [/math]

[math] \mathrm(0) = \mathrm(0) [/math]

[math] \mathrm(x+1) = x [/math]

Теперь рассмотрим [math] \mathrm(x,y) [/math]

[math] \mathrm(x,0) = x [/math]

Операции сравнения

[math] \mathrm(x,y) = 1 [/math] если [math] x = y [/math] , иначе [math] \mathrm(x,y) = 0 [/math]

[math] \mathrm(x,y) = 1 [/math] если [math] x \leqslant y [/math] , иначе [math] \mathrm(x,y) = 0 [/math]

[math] \mathrm(x,y) = 1 [/math] если [math] x \lt y [/math] , иначе [math] \mathrm(x,y) = 0 [/math]

Сначала выразим [math] \mathrm>(x) = \mathrm(x,0) [/math]

[math] \mathrm(0) =\mathrm(0) [/math]

[math] \mathrm(y) = \mathrm(y-1,\mathrm(y-1)) [/math] , где [math] \mathrm(y-1,\mathrm(y-1)) = \mathrm(x,y-1) [/math]

Теперь все остальные функции

[math] \mathrm(x,y) = \mathrm(\mathrm(x,y),\mathrm(y,x)) [/math]

Условный оператор

[math] \mathrm(0,x,y) = y [/math]

[math] \mathrm(c,x,y) = x [/math]

Деление

[math] \mathrm(x,y) = \Bigl \lfloor \dfrac \Bigr \rfloor [/math] , если [math] y \gt 0 [/math] . Если же [math] y = 0 [/math] , то значение функции нас не интересует, и можно определить её как угодно.

Сначала определим [math] \mathrm(x,y) [/math] — функция равна максимальному числу меньшему или равному [math] x[/math] , которое нацело делится на [math] y [/math] .

Теперь само деления

[math] \mathrm(0,y) = \mathrm(y) [/math]

[math] \mathrm(x,y) = \mathrm(x,y,\mathrm(x,y)) [/math] , где [math] \mathrm(x,y,z) = \mathrm(z,\mathrm(\mathrm(x),\mathrm(\mathrm(x),y))) [/math]

Остаток от деления выражается так:

Работа со списками фиксированной длины

С помощью описанных выше арифметических операций можно выразить проверку на простоту числа и поиск [math] n [/math] -ого простого числа. Рассмотрим список из натуральны чисел [math] [x_1,\ldots,x_n] [/math] , тогда ему в соответствия можно поставить число [math] p_1^ \cdot p_2^ \cdot \ldots \cdot p_n^ [/math] , где [math]p_i[/math] — [math]i[/math] -тое простое число. Как видно из представления,создания списка, взятие [math] i [/math] — того элемента и остальные операции являются простыми арифметическими операциями, а следовательно примитивно рекурсивными. Поэтому будем считать что у примитивно рекурсивной функций аргументы и результат могут быть списками из натуральных чисел.

Теоремы

Теорема о примитивной рекурсивности вычислимых функций

Если для вычислимой функции [math] \mathrm [/math] существует примитивно рекурсивная функция [math] \mathrm [/math] , такая что для любых аргументов [math] args [/math] максимальное количество шагов, за которое будет посчитана [math] \mathrm(x) [/math] на МТ равно [math] \mathrm(args) [/math] , то [math] \mathrm [/math] примитивно рекурсивная функция.

Каждому состоянию МТ поставим в соответствие список из четырех чисел [math] [L,R,S,C] [/math] , где:

• [math] L [/math] — состояние МТ слева от головки ленты, представлено в виде числа в системы счисления с основанием равным алфавиту МТ. Младшие разряды находятся возле головки. Пробелу соответствует ноль, чтобы число было конечным.

• [math] R [/math] — состояние МТ справа от головки, представлено аналогично [math] L [/math] только возле головки МТ находятся старшие разряды.

• [math] S [/math] — номер текущего состояния.

• [math] C [/math] — символ на который указывает головка ленты.

Тогда всем переходам соответствует функция [math] \mathrm([L,R,S,C]) [/math] принимающая состояние МТ и возвращающая новое состояние. Покажем что она примитивно рекурсивная . При применении перехода в [math] C [/math] записывается новый символ,затем из-за сдвига головки в [math] L [/math] и [math] R [/math] в конец добавляется новая цифра или удаляется старая, затем в [math] C [/math] записываетcя символ после сдвига, и в конце перехода в [math] S [/math] записывается новое состояние автомата. Операции добавления в конец цифры или удаления последней цифры легко выражаются через простые арифметические операции, следовательно они примитивно рекурсивные. Все остальные операции являются простыми операциями над списками, а значит они тоже примитивно рекурсивные. Из этого следует что применения перехода — примитивно рекурсивная функция. В силу того что нужный переход можно выбрать используя конечное число функций [math] \mathrm [/math] следует что и [math] \mathrm [/math] также является примитивно рекурсивной функцией.

Функции преобразование аргументов в формат входных данных для МТ и получения ответа по состоянию МТ также выражаются через простые арифметические операции а значит они примитивно рекурсивные. Назовем их [math]\mathrm [/math] и [math] \mathrm [/math] .

Рассмотрим функцию двух аргументов [math] \mathrm([L,R,S,C],t) [/math] которая принимает состояние МТ , число шагов [math] t [/math] и возвращает состояние МТ после [math] t [/math] шагов. Покажем что [math]\mathrm[/math] — примитивно рекурсивная функция.

[math] \mathrm([L,R,S,C],t) = [L,R,S,C] [/math]

[math] \mathrm([L,R,S,C],t+1) = \mathrm([L,R,S,C],t+1,\mathrm([L,R,S,C],t)) [/math] , где [math] \mathrm([L,R,S,X],y,[L1,R1,S1,C1]) = \mathrm([L1,R1,S1,C1]) [/math]

См. также

• Лямбда-исчисление
• Частично рекурсивные функции

Источники информации

• Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. 4-е изд., испр., М.: МЦНМО, 2012
• Википедия — Рекурсивная функция
• Wikipedia — Primitive recursive function

Примитивно-рекурсивные функции и функция Аккермана

Функция Аккермана — одна из самых знаменитых функций в Computer Science. С ней связан как минимум один фундаментальный результат и как минимум один просто важный. Фундаментальный результат, говоря аккуратно и непонятно, таков: существует всюду определённая вычислимая функция, не являющаяся примитивно-рекурсивной. Важный результат заключается в том, что лес непересекающихся множеств (также известный как disjoint set union) работает очень быстро.

Мне очень нравится изучать функцию Аккермана, т.к. всё, что с ней связано, очень красиво и изящно. Вот и записанный выше фундаментальный результат понять намного проще, чем это может показаться.

Из текста ниже вы узнаете, что такое примитивно-рекурсивные функции и как выяснить, что функция Аккермана к таковым не относится. И, конечно, этот текст убедит вас в том, что это невероятно красивая конструкция и невероятно красивое рассуждение!

1. Почему это может быть интересно

Рассуждение о связи между примитивно-рекурсивными функциями и функцией Аккермана является примером решения стандартной в теории вычислимости задачи: дана некоторая модель вычислений, некоторая функция, и необходимо определить, является ли эта функция вычислимой в данной модели.

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

Функция Аккермана как будто специально создана для того, чтобы быть изящным примером решения такого рода вопросов. Скоро вы в этом убедитесь.

2. Функция Аккермана

Определение из Википедии для наших целей подходит плохо, поэтому я использую определение из книжки Верещагина и Шеня «Вычислимые функции». Эта конструкция и идейно, и технически несколько отличается от изначальной, придуманной Аккерманом, но сейчас это не так важно.

Введём последовательность функций одного аргумента. Определим их рекурсивно:

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

Кстати, все аргументы здесь натуральные либо ноль — довольно типичный расклад для теории алгоритмов, да и для дискретной математики вообще.

Такое определение набора функций проще всего записать следующим кодом:

def Foo(number, argument): if number == 0: return argument + 1 result = argument for i in range(argument + 2): result = Foo(number - 1, result) return result

Для определения значения достаточно вычислить значение Foo(i, x) .

Так определённый набор функций обладает полезными свойствами монотонности. Во-первых, по аргументу: для любых и . Ну, действительно, , а функции со следующими номерами многократно применяют к своему аргументу.

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

Отдельно стоит запомнить, что

3. Примитивно-рекурсивные функции (ПРФ)

ПРФ являются примером «математического исчисления». Исчисление — это способ определять множества объектов через набор аксиом и правил вывода из этих аксиом. В современной математике такой подход распространён широко: его можно встретить и в теории алгоритмов, и в математической логике, и в теории групп, и в куче других мест.

Что такое примитивно-рекурсивная функция? Начнём с «аксиом». Примитивно-рекурсивными функциями являются:

1. Функция, тождественно равная нулю:
2. Функция прибавления единицы:
3. Функция-проекция:

Назовём эти функции базисными. Теперь о «правилах вывода»:

• Подстановка. Если — функция аргументов, а — функции аргументов, то из них можно собрать функцию аргументов : берём аргументов, подставляем их в каждую из функций , получившиеся значения используем как аргументы функции . Типичная подстановка!

• Примитивная рекурсия. Если — функция аргументов, а — функция аргументов, то из них можно собрать функцию, определённую следующим образом:

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

Итак, ПРФ — это базисные функции, а также любые функции, полученные из базисных при помощи операций композиции и примитивной рекурсии.

В терминах ПРФ легко построить описания простых всем известных функций.

Например, сложение двух чисел сделаем через рекурсию по второму слагаемому. Если к числу прибавить ноль, то надо вернуть само это число. В противном случае надо к результату прибавить единицу, из второго слагаемого вычесть единицу и запустить рекурсию:

Теория алгоритмов — часть математики, а поэтому требует строгости. В данном случае оператор примитивной рекурсии требует, чтобы при нулевом втором аргументе вызывалась некоторая функция одного аргумента. Хотелось бы написать , но я не могу, т.к. просто не является функцией. Это вынуждает меня использовать функцию . В случае же рекурсивного вызова правила требуют, чтобы в правой части равенства стояла функция трёх конкретных аргументов: . Из них всех мне нужен только третий аргумент, поэтому я достаю его при помощи функции , а уже затем прибавляю единичку.

Похожим образом можно определить умножение:

Ну и давайте определим что-нибудь поинтереснее. Скажем, последовательность Фибоначчи! Напомню, что она определяется следующим образом:

В данном случае придётся помнить два предыдущих значения, а не одно; значит, придётся выкручиваться!

Введём не одну функцию, а сразу две. Первая функция, пусть это будет , будет производить искомые числа Фибоначчи. А вторая функция, пусть это будет , будет производить числа Фибоначчи со следующим номером, то есть:

В таком случае первые несколько значений функции должны равняться 0, 1, 1, 2, 3, 5; функции , соответственно, 1, 1, 2, 3, 5, 8. Тогда рекурсия должна выглядеть следующим образом:

Осталось только записать это строго:

Соответствующая реализация выглядит следующим образом:

def G(x): if x == 0: return 1 return G(x - 1) + F(x - 1) def F(x): if x == 0: return 0 return G(x - 1)

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

4. Функция Аккермана и ПРФ, часть первая

Оказывается, примитивно-рекурсивные функции не могут «безгранично быстро» расти. Точнее говоря: для любой примитивно-рекурсивной функции аргументов найдётся такое , что:

Доказывать такие утверждения для исчислений — одно удовольствие. Вначале докажем его для базисных функций, а затем проверим, что свойство сохраняется при применении операций.

Что же, для базисных операций всё понятно:

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

Теперь займёмся правилами вывода. Здесь используем математическую индукцию: в предположении, что утверждение верно для функций, из которых составляется результирующая, покажем, что утверждение верно и для результирующей функции.

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

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

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

Посмотрим для начала, что будет, когда аргумент рекурсии равняется нулю. Тут всё просто: можем использовать оценку для функции :

Теперь посмотрим, что будет, если последний аргумент равен единице:

Здесь сначала используется уже полученная оценка для , а также оценка для . После этого используется монотонность функции : ясно, что

Продолжая это рассуждение по индукции, получим, что

А свойства введённой последовательности функций гарантируют, что

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

5. Функция Аккермана и ПРФ, часть вторая

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

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

Теперь верно следующее утверждение: введённая функция не является примитивно-рекурсивной.

Действительно, предположим, что эта функция является примитивно-рекурсивной. Тогда по доказанному в пункте 4 существует такой номер , что для всех . Но это точно не так, например:

Таким образом, новая функция не является примитивно-рекурсивной. Этого-то мы и добивались, ура! Её и будем называть функцией Аккермана.

6. А насколько она в действительности велика?

Возвращаясь к практике, нам может быть интересно знать, насколько же всё-таки быстро растёт функция Аккермана, с чем её вообще можно сравнить. Выше мы уже видели, что суммы и произведения определяются некоторыми ПРФ. Через ПРФ можно определить операцию возведения в степень и даже функцию . Более того, любая функция вида

с наперёд заданным количеством возведений в степень, является примитивно-рекурсивной. Не поленюсь и докажу это. Для начала построю функцию :

Теперь использую её для определения функции :

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

Действуя по аналогии, можно построить функцию, в которой возводится в степень пять раз, десять раз, сто раз, миллион раз. Функция Аккермана растёт быстрее любой из этих функций. Вот насколько быстро она растёт!

• функция аккермана
• теоретические модели вычислений
• dsu
• math