03.02.2020 07:59
ashagraev 9 7400 Источник

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


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


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


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


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


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


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


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


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


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


$a_0(x) = x + 1$


$a_{i+1}(x) = a_{i}[x+2](x)$


Здесь $f[n](x) = f\Big(f(...(f(x))...)\Big)$ — в квадратных скобках записывается число $n$, и тогда ровно $n$ раз функция применяется к своему аргументу. Таким образом, значение каждой следующей функций из нашей последовательности определяется так: возьмём предыдущую функцию, $x+2$ раза применим её к числу $x$ — получится значение следующей функции на числе $x$.


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


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


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

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


Так определённый набор функций обладает полезными свойствами монотонности. Во-первых, по аргументу: $a_i(x) > x$ для любых $i$ и $x$. Ну, действительно, $a_0(x) = x + 1 > x$, а функции со следующими номерами многократно применяют $a_0$ к своему аргументу.


Во-вторых, по номеру функции: $a_{i+1}(x) \gt a_i(x)$ для любых $i$ и $x$. Раз все функции строго монотонны по аргументу, а функция со следующим номером применяет функцию с предыдущим номером к этому же аргументу более одного раза — стало быть, итоговое значение получится больше. Чуть подробнее:


$a_{i+1}(x) = a_i[x+2](x) \ge a_i[2](x) = a_i\Big(a_i(x)\Big) > a_i(x)$


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


$a_{i+1}(x) \ge a_i\Big(a_i(x)\Big)$


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


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


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


  1. Функция, тождественно равная нулю: $Null(x_1,x_2,...,x_k) = 0$
  2. Функция прибавления единицы: $S(x)=x+1$
  3. Функция-проекция: $P_k^i(x_1, x_2,...,x_k)=x_i$

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


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

$F(x_1,...,x_n)=f\Big(g_1(x_1,...,x_n),...,g_k(x_1,...,x_n)\Big)$


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

$F(x_1,...,x_k,0)=f(x_1,...,x_k)$


$F(x_1,...,x_k,y+1)=g\Big(x_1,...,x_k,y,F(x_1,...,x_k,y)\Big)$


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


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


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


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


$Sum(x,0)=P_1^1(x)$


$Sum(x,y+1)=S\Big(P_3^3(x,y,Sum(x,y))\Big)$


Теория алгоритмов — часть математики, а поэтому требует строгости. В данном случае оператор примитивной рекурсии требует, чтобы при нулевом втором аргументе вызывалась некоторая функция одного аргумента. Хотелось бы написать $Sum(x,0)=x$, но я не могу, т.к. просто $x$ не является функцией. Это вынуждает меня использовать функцию $P_1^1$. В случае же рекурсивного вызова правила требуют, чтобы в правой части равенства стояла функция трёх конкретных аргументов: $x,y,Sum(x,y)$. Из них всех мне нужен только третий аргумент, поэтому я достаю его при помощи функции $P_3^3$, а уже затем прибавляю единичку.


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


$Mult(x,0)=Null(x)$


$Mult(x,y+1)=Sum\Big(P_3^1(x,y,Mult(x,y)),P_3^3(x,y,Mult(x,y))\Big)$


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


$Fib_0 = 0$
$Fib_1 = 1$
$Fib_{n+2} = Fib_n + Fib_{n+1}$


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


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


$F(n) = Fib_n$
$G(n) = Fib_{n+1}$


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


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


$F(0)=Null()$


$G(0)=S(Null())$


$F(y+1)=P_2^1\Big(G(y),F(y)\Big)$


$G(y+1)=Sum\Big(F(y),G(y)\Big)$


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


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)

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


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


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


$f(x_1,...,x_k)<a_n(max(x_1,...,x_k))$


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


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


$Null(x_1,...,x_k)=0<max(x_1,...,x_k) + 1=a_0(max(x_1,...,x_k))$


$S(x)=x+1=a_0(x)<a_1(x)$


$P_k^i(x_1,...,x_k)=x_i\le max(x_1,...,x_k)<a_0\Big(max(x_1,...,x_k)\Big)$


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


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


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


$F(x_1,...,x_n)=f\Big(g_1(x_1,...,x_n),...,g_k(x_1,...,x_n)\Big)<$


$<a_M\Big(max(g_1(x_1,...,x_n),...,g_k(x_1,...,x_n))\Big)<$


$<a_M\Big[max\Big(a_M(max(x_1,...,x_n)),...,a_M(max(x_1,...,x_n))\Big)\Big]$


$<a_M\Big(a_M(max(x_1,...,x_n))\Big) \le a_{M+1}\Big(max(x_1,...,x_n)\Big)$


Здесь вначале использована ограниченность функции $f$, затем ограниченность каждой из функций $g_i$, после чего внешний максимум оказывается применён к набору из $k$ одинаковых чисел, а поэтому может быть исключён. В итоге оценка сводится к двукратному применению функции $a_M$ к своему аргументу, а такой результат ограничивается значением следующей фукнции $a_{M+1}$.


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


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


$F(x_1,...,x_k,0)=f(x_1,...,x_k)<a_M\Big(max(x_1,...,x_k)\Big)$


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


$F(x_1,...,x_k,1)=g\Big(x_1,...,x_k,0,F(x_1,...,x_k,0)\Big)<$


$<a_M\Big(max(x_1,...,x_k,0,a_M(max(x_1,...,x_k))\Big)<$


$<a_M\Big(a_M(max(x_1,...,x_k)\Big)=a_M[2](max(x_1,...,x_k))$


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


$a_M\Big(max(x_1,...,x_k)\Big)>max(x_1,...,x_k, 0)$


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


$F(x_1,...,x_k,y)<a_M[y+1](max(x_1,...,x_k))$


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


$a_M[y+1](max(x_1,...,x_k))<a_{M+1}\Big(max(x_1,...,x_k,y)\Big)$


Окончательно:


$F(x_1,...,x_k,y)<a_{M+1}\Big(max(x_1,...,x_k,y)\Big)$


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


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


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


$A(n)=a_n(n)$


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


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


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


$A(M+1)=a_{M+1}(M+1)>a_M(M+1)$


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


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


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


$n^{n^{...^{n^n}}}$


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


$Pow(n,0)=S(Null())$


$Pow(n,y+1)=Mult\Big(P_3^1(n,y,Pow(n,y)),P_3^3(n,y,Pow(n,y))\Big)$


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


$SPow(n)=Pow(P_1^1(n),P_1^1(n))$


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


$SSPow(n)=Pow(P_1^1(n),SPow(n))$


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