Функция Аккермана — одна из самых знаменитых функций в 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. Примитивно-рекурсивные функции (ПРФ)
ПРФ являются примером «математического исчисления». Исчисление — это способ определять множества объектов через набор аксиом и правил вывода из этих аксиом. В современной математике такой подход распространён широко: его можно встретить и в теории алгоритмов, и в математической логике, и в теории групп, и в куче других мест.
Что такое примитивно-рекурсивная функция? Начнём с «аксиом». Примитивно-рекурсивными функциями являются:
- Функция, тождественно равная нулю:
- Функция прибавления единицы:
- Функция-проекция:
Назовём эти функции базисными. Теперь о «правилах вывода»:
- Подстановка. Если
— функция
аргументов, а
— функции
аргументов, то из них можно собрать функцию
аргументов
: берём
аргументов, подставляем их в каждую из
функций
, получившиеся значения используем как аргументы функции
. Типичная подстановка!
- Примитивная рекурсия. Если
— функция
аргументов, а
— функция
аргументов, то из них можно собрать функцию, определённую следующим образом:
В случае примитивной рекурсии легко угадать признаки того, что мы обыкновенно называем рекурсией. Тут есть конец рекурсии: он происходит, когда последний аргумент обращается в ноль. Есть рекурсивный вызов: для вычисления значения функции с последним аргументом, отличным от нуля, необходимо вычислить значение с уменьшенным значением последнего аргумента. Такое определение является достаточно общим, т.к. в процессе вычислений доступна и сама переменная, по которой осуществляется рекурсия.
Итак, ПРФ — это базисные функции, а также любые функции, полученные из базисных при помощи операций композиции и примитивной рекурсии.
В терминах ПРФ легко построить описания простых всем известных функций.
Например, сложение двух чисел сделаем через рекурсию по второму слагаемому. Если к числу прибавить ноль, то надо вернуть само это число. В противном случае надо к результату прибавить единицу, из второго слагаемого вычесть единицу и запустить рекурсию:
Теория алгоритмов — часть математики, а поэтому требует строгости. В данном случае оператор примитивной рекурсии требует, чтобы при нулевом втором аргументе вызывалась некоторая функция одного аргумента. Хотелось бы написать , но я не могу, т.к. просто
не является функцией. Это вынуждает меня использовать функцию
. В случае же рекурсивного вызова правила требуют, чтобы в правой части равенства стояла функция трёх конкретных аргументов:
. Из них всех мне нужен только третий аргумент, поэтому я достаю его при помощи функции
, а уже затем прибавляю единичку.
Похожим образом можно определить умножение:
Ну и давайте определим что-нибудь поинтереснее. Скажем, последовательность Фибоначчи! Напомню, что она определяется следующим образом:
В данном случае придётся помнить два предыдущих значения, а не одно; значит, придётся выкручиваться!
Введём не одну функцию, а сразу две. Первая функция, пусть это будет , будет производить искомые числа Фибоначчи. А вторая функция, пусть это будет
, будет производить числа Фибоначчи со следующим номером, то есть:
В таком случае первые несколько значений функции должны равняться 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. А насколько она в действительности велика?
Возвращаясь к практике, нам может быть интересно знать, насколько же всё-таки быстро растёт функция Аккермана, с чем её вообще можно сравнить. Выше мы уже видели, что суммы и произведения определяются некоторыми ПРФ. Через ПРФ можно определить операцию возведения в степень и даже функцию . Более того, любая функция вида
с наперёд заданным количеством возведений в степень, является примитивно-рекурсивной. Не поленюсь и докажу это. Для начала построю функцию :
Теперь использую её для определения функции :
Как видите, это делается простой подстановкой. Теперь нет сложности с тем, чтобы определить функцию :
Действуя по аналогии, можно построить функцию, в которой возводится в степень
пять раз, десять раз, сто раз, миллион раз. Функция Аккермана растёт быстрее любой из этих функций. Вот насколько быстро она растёт!