Функция Аккермана
Функция Аккермана — всюду определённая вычислимая функция, которая не является примитивно рекурсивной. Она принимает два неотрицательных целых числа в качестве параметров и возвращает натуральное число, обозначается . Эта функция растёт очень быстро, например, число настолько велико, что количество цифр в порядке этого числа многократно превосходит количество атомов в наблюдаемой части Вселенной. В теоретической информатике она применяется для демонстрации пределов возможностей компьютеров и методов оптимизации. Также существует целое семейство родственных ей функций, имеющих схожую скорость роста и схожее определение.
История[править | править код]
В 1926 году Дэвид Гильберт предположил, что каждая вычислимая функция примитивно-рекурсивна. Проще говоря, каждую вычислимую функцию можно построить из базового набора при помощи нескольких очень простых правил, причём продолжительность вычисления может быть оценена заранее. Функции, для которых это неверно, очень редки.
В том же 1926 году Аккерман построил функцию, опровергающую эту гипотезу, и опубликовал свой контрпример в 1928 году. Впоследствии эта функция получила название гипероператора. Он может быть оценен компьютером за конечное время, но не является примитивно-рекурсивным.
В 1935 году Рожа Петер упростила построение Аккермана, получив столь же быстрорастущую функцию. Именно она и стала называться функцией Аккермана.
Идея построения[править | править код]
Рассмотрим последовательность . В этой последовательности каждый следующий оператор определяется так, что предыдущий оператор применяется раз к числу . Например, результат применения второго оператора к числам и равен , где число входит в выражение раз. Аналогично значение третьего оператора равно . Аккерманн предложил рассмотреть функцию возвращающую результат применения -го оператора последовательности к числам и .
- Пример : Применив все операторы последовательности к числам и , получаем следующие результаты: 6, 8, 16, 65536, (с 65536 двойками),... Пятый член последовательности настолько велик, что количество цифр в его десятичной записи намного больше числа атомов во Вселенной.
Таким образом, построенная Аккерманом функция удовлетворяет следующим уравнениям:
Начиная с четвертой строки, функцию становится затруднительно описать с помощью обычных операторов.
Определение и варианты[править | править код]
Функция Аккермана обычно определяется рекурсивно, т.е. явно задаётся для некоторых начальных значений, после чего описывается алгоритм получения дальнейших значений функции из уже рассчитанных.
Определение Аккермана[править | править код]
Изначально Аккерман определил функцию довольно громоздко, но вскоре дал следующее эквивалентное определение:
Здесь -- еще одна функция, задающая начальные значения :
- Примеры :
- При вычислении можно применить первую строку определения и получить .
- При вычислении мы применяем вторую строку и получаем .
- Если ни второй, ни третий аргумент не равен 0, используем третью строку определения. Например, . Подставив из предыдущего примера, получим . Продолжая рекурсивно вычислять значения функции получим
При оценке скорости роста функции Аккермана обычно изучают функцию.
Определение Петер[править | править код]
В 1935 году Рожа Петер предложила более простое построение, в котором функция имеет только два параметра, а вспомогательная функция не используется: [1]
Говоря о скорости роста функции Аккермана, тоже имеют в виду скорость роста функции .
Рекурсия всегда заканчивается. Это следует из того, что при рекурсивном вызове или уменьшается значение , или значение сохраняется, но уменьшается значение . Это означает, что каждый раз пара уменьшается с точки зрения лексикографического порядка, значит, значение в итоге достигнет нуля: для одного значения существует конечное число возможных значений (так как первый вызов с данным был произведён с каким-то определённым значением , а в дальнейшем, если значение сохраняется, значение может только уменьшаться), а количество возможных значений , в свою очередь, тоже конечно. Однако, при уменьшении значение, на которое увеличивается , неограниченно и обычно очень велико.
Применение в теоретической информатике[править | править код]
Аккерман привёл эту функцию в качестве примера функции, которая не является примитивно-рекурсивной, но является вычислимой.
Некоторое время предполагалось, что все вычислимые функции примитивно-рекурсивны, т. е. вычислимость любой функции можно доказать, построив алгоритм, или опровергнуть, убедившись, что она не является примитивно-рекурсивной. Однако функция Аккермана, будучи вычислимой, но не примитивно-рекурсивной (доказательство этого приведено ниже), опровергла это предположение.
Если ввести ещё одно правило построения, так называемую частичную рекурсию, то класс получающихся таким способом функций расширится и будет, в частности, содержать функцию Аккермана. Предполагается, что этот класс частично рекурсивных функций равен классу вычислимых функций (тезис Чёрча).
Доказательство[править | править код]
Чтобы доказать, что функция Аккермана вычислима, но не является примитивно-рекурсивной, мы докажем, что каждая примитивно рекурсивная функция (далее- ПРФ) растёт медленнее функции Аккермана[2].
Набросок доказательства утверждения, что функция Аккермана не является примитивно-рекурсивной:
- Сначала определим для каждой ПРФ функцию
- Эта функция возвращает наибольшее значение, которое можно получить при помощи функции , не используя аргументов выше .
- Затем с помощью индукции по структуре ПРФ показывается, что для любой ПРФ существует натуральное число , такое, что при всех .
- Если бы функция Аккермана была ПРФ, то функция сама оказалась бы примитивно рекурсивной, и для некоторого мы бы получили, что при всех Однако функция Аккермана монотонна по обоим аргументам. Противоречие.
Приложения[править | править код]
Существует очень мало приложений для функции Аккермана. Помимо невероятной глубины рекурсии, из-за которой она часто применяется в тестах производительности рекурсивных вызовов в языках программирования, функция Аккермана используется для оценки времени выполнения взвешенного объединения и сжатия пути в системе непересекающихся множеств.
Ориентир для рекурсивных вызовов[править | править код]
При тестировании новых языков программирования, компиляторов и компьютеров важное место занимает проверка их производительности.
В качестве эталона для проверки рекурсивных вызовов процедур часто используется функция Аккермана, так как непосредственное вычисление этой функции состоит почти только из них. В определении Петер непосредственно заданы только значения . Все остальные значения вычисляются с помощью многократных глубоко вложенных вызовов, что легко может привести к переполнению стека, указывающему на то, что системе не хватает памяти. Таким образом, функция Аккермана является простым и безопасным методом провоцирования переполнения стека, например, для проверки того, обрабатывается ли этот случай ошибки и, если да, то как это делается. Преимущество функции Аккермана в том, что она невосприимчива к оптимизации компилятора, а статический анализ исходного кода практически не способен обнаружить (возможное) переполнение стека.
Эта идея восходит к Ингве Сундбладу, который в 1971 году начал использовать функцию для сравнения различных языков программирования. При вычислении происходит около вложенных вызовов.
Компания Sundblad проверила, среди прочего, максимальное значение , при котором вычисление не вызывает переполнения. В то время максимально возможное значение было равно 1. Сейчас в языке Java 1.4.2 со стандартными настройками памяти максимальное допустимое значение .
В ходе расчета множество одинаковых вызовов обсчитываются несколько раз. Умный компилятор может воспользоваться этим и кэшировать результаты, чтобы не вычислять одно и то же значение много раз. Уже в 1971 году таким способом было достигнуто число . Другим способом оптимизации является вычисление напрямую без рекурсивного раскрытия в . Прямой расчёт требует линейного времени по . Расчёт требует квадратичного времени, потому что при этом происходят вложенных вызовов для разных . Расчёт занимает времени.
Оценки времени выполнения, содержащие обратную функцию Аккермана[править | править код]
Поскольку функция растёт очень быстро, её обратная функция растет очень медленно. Поскольку для всех практически встречающихся значений значение меньше 5, при практическом анализе алгоритмов его можно считать постоянным.
Реализация[править | править код]
В псевдокоде функция Аккермана реализуется по определению:
функция ack(n, m) если n = 0 вернуть m + 1 иначе, если m = 0 вернуть ack (n - 1, 1) еще вернуть ack(n - 1, ack (n, m - 1))
Следующая частично итерационная реализация несколько более эффективна:
функция ack(n, m) пока n ≠ 0 если m = 0 m:= 1 иначе m:= ack(n, m - 1) n:= n - 1 вернуть m + 1
Ещё более эффективные реализации используют динамическое программирование.
Grossman & Zeitman опубликовали алгоритм вычисления функции Аккермана без использования кэша, занимающий время и использующий памяти[3].
В функциональном языке программирования Haskell, реализация напрямую отражает определение:
ack 0 n = n+1
ack n 0 = ack (n-1) 1
ack n m = ack (n-1) (ack n (m-1))
На Прологе реализация выглядит так:
ackermann(0,X,Y) :- X >= 0,!, Y = X + 1. ackermann(X,0,Z):- X > 0,!, X1 = X - 1, ackermann(X1,1,Z). ackermann(X,Y,Z):- X > 0, Y > 0, X1 = X-1, Y1 = Y-1, ackermann(X,Y1,W), ackermann(X1,W,Z).
Чисто итеративная реализация возможна даже в лямбда-исчислении:
ack ≡ λn. n (λf.λm.mf (f 1 )) succ
Таблица значений [править | править код]
- Подробнее о hyper см. гипероператор.
(всего блоков ) |
Хотя в этой таблице возникают невообразимо большие числа, впоследствии были описаны рекуррентные построения, порождающие ещё бо́льшие числа, такие как число Грэма.
m\n | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|
0 | 1 бит | 2 бита | 2 бита | 3 бита | 4 бита | 16 бит |
1 | 2 бита | 2 бита | 3 бита | 4 бита | 16 бит | |
2 | 2 бита | 3 бита | 3 бита | 5 бит | 8 КБ | |
3 | 2 бита | 3 бита | 4 бита | 6 бит | более йоттабайт | |
4 | 3 бита | 3 бита | 4 бита | 7 бит | ||
5 | 3 бита | 3 бита | 4 бита | 8 бит | ||
6 | 3 бита | 3 бита | 4 бита | 9 бит | ||
7 | 3 бита | 3 бита | 5 бит | 10 бит | ||
8-й | 4 бита | 4 бита | 5 бит | 11 бит | ||
9 | 4 бита | 4 бита | 5 бит | 12 бит | ||
10 | 4 бита | 4 бита | 5 бит | 13 бит | ||
100 | 7 бит | 7 бит | 8 бит | 103 бита | ||
1000 | 10 бит | 10 бит | 11 бит | 125 375 байт | ||
10'000 | 14 бит | 14 бит | 15 бит | 1221 КБ | ||
100'000 | 17 бит | 17 бит | 18 бит | 12 207 КБ | ||
1 000 000 | 20 бит | 20 бит | 21 бит | 122 071 КБ | ||
10 000 000 | 24 бит | 24 бит | 25 бит | 1192 МБ | ||
100 000 000 | 27 бит | 27 бит | 28 бит | 11 921 МБ | ||
2 32 −1 | 33 бита | 33 бита | 34 бит | 119,21 МБ | ||
2 64 −1 | 65 бит | 65 бит | 66 бит | 1164 ГБ |
Подробное описание[править | править код]
Используя таблицу значений, можно вывести схему вычисления значений функции, которую легче понять, чем формальное рекурсивное определение. Легко заметить, что значения в первой строке — это просто список всех натуральных чисел: . Все последующие строки просто содержат инструкции для поиска значения в этой строке. При легко показать, что
Теперь рассмотрим более сложный случай вычисления функции , значение которой настолько велико, что записать его в десятичном виде невозможно.
Вычислить напрямую подобные значения совершенно невозможно. Даже очень простые на вид выражения Аккермана практически не поддаются вычислению. Каждая строка в предыдущем примере — это отдельное применение одной из трёх частей определения функции Аккермана.
Ещё одним аспектом функции Аккермана является то, что единственное вычисление, которое действительно появляется помимо рекурсивных вызовов, — это вычисление
Литература[править | править код]
- Dexter C. Kozen: The Design and Analysis of Algorithms. Springer, Berlin 1992, ISBN 3-540-97687-6.
- Uwe Schöning: Theoretische Informatik – kurzgefasst. Spektrum Akademischer Verlag, Heidelberg 2001, ISBN 3-8274-1099-1.
- Yngve Sundblad: The Ackermann Function. A Theoretical, Computational, and Formula Manipulative Study. In: BIT – numerical mathematics. Springer, Dordrecht 11.1971, S. 107–119, ISSN 0006-3835.
Внешние ссылки[править | править код]
- Пояснительное видео для функции Аккермана (на английском языке)
Примечания[править | править код]
- ↑ Péter Rózsa: Konstruktion nichtrekursiver Funktionen. In: Mathematische Annalen, 111, 1935, S. 42–60
- ↑ Für Details zum Beweis sehe man z. B. im Buch von Uwe Schöning nach (siehe Literatur).
- ↑ Grossman, Jerrold W. (1988-05). “An inherently iterative computation of ackermann's function”. Theoretical Computer Science. 57 (2—3): 327—330. DOI:10.1016/0304-3975(88)90046-1. Проверьте дату в
|date=
(справка на английском)
Ссылки[править | править код]
- Weisstein, Eric W. Ackermann Function (англ.) на сайте Wolfram MathWorld.
Эта статья выставлена на рецензию. Пожалуйста, выскажите своё мнение о ней на подстранице рецензии. |