stringtranslate.com

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

В теории вычислимости функция Аккермана , названная в честь Вильгельма Аккермана , является одним из простейших [1] и самых ранних открытых примеров полностью вычислимой функции, которая не является примитивно рекурсивной . Все примитивно рекурсивные функции являются тотальными и вычислимыми, но функция Аккермана иллюстрирует, что не все полностью вычислимые функции являются примитивно рекурсивными.

После публикации [2] функции Аккермана (которая имела три неотрицательных целых аргумента) многие авторы модифицировали ее для различных целей, так что сегодня «функция Аккермана» может относиться к любому из многочисленных вариантов исходной функции. Одной из распространенных версий является двухаргументная функция Аккермана–Петера, разработанная Рожей Петер и Рафаэлем Робинсоном . Ее значение растет очень быстро; например, результатом является , целое число из 19 729 десятичных цифр. [3]

История

В конце 1920-х годов математики Габриэль Судан и Вильгельм Акерман , ученики Давида Гильберта , изучали основы вычислений. И Судану, и Акерману приписывают [4] открытие полных вычислимых функций (в некоторых источниках называемых просто «рекурсивными»), которые не являются примитивно рекурсивными . Судан опубликовал менее известную функцию Судана , а вскоре после этого и независимо, в 1928 году, Акерман опубликовал свою функцию (от греческой буквы фи ). Трехаргументная функция Акермана, , определена таким образом, что для , она воспроизводит основные операции сложения , умножения и возведения в степень как

а для p > 2 он расширяет эти базовые операции таким образом, что их можно сравнить с гипероперациями :

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

В работе «О бесконечности » [5] Дэвид Гильберт выдвинул гипотезу, что функция Аккермана не является примитивно рекурсивной, но именно Аккерман, личный секретарь Гильберта и его бывший студент, фактически доказал эту гипотезу в своей статье « О конструкции действительных чисел по Гильберту» . [2] [6]

Позднее Рожа Петер [7] и Рафаэль Робинсон [8] разработали версию функции Аккермана с двумя переменными, которая стала предпочтительнее почти всех авторов.

Обобщенная последовательность гиперопераций , например , также является версией функции Аккермана. [9]

В 1963 году Р. К. Бак основал интуитивный вариант с двумя переменными [n 1] на последовательности гиперопераций : [10] [11]

По сравнению с большинством других версий, функция Бака не имеет несущественных смещений:

Было исследовано много других версий функции Аккермана. [12] [13]

Определение

Определение: как m-арная функция

Оригинальная функция Аккермана с тремя аргументами определяется рекурсивно следующим образом для неотрицательных целых чисел и :

Из различных версий с двумя аргументами версия, разработанная Петером и Робинсоном (называемая большинством авторов «функцией Аккермана»), определена для неотрицательных целых чисел следующим образом :

Функция Аккермана также была выражена в отношении последовательности гиперопераций : [14] [15]

или, записанный в нотации Кнута со стрелкой вверх (расширенной до целочисленных индексов ):
или, что эквивалентно, в терминах функции Бака F: [10]

Определение: как итерированная 1-арная функция

Определим как n -ю итерацию :

Итерация — это процесс составления функции с самой собой определенное количество раз. Композиция функций — это ассоциативная операция, поэтому .

Рассматривая функцию Аккермана как последовательность унарных функций, можно положить .

Функция затем становится последовательностью унарных [n 2] функций, определенных из итерации :

Вычисление

Рекурсивное определение функции Аккермана можно естественным образом транспонировать в систему переписывания термов (TRS) .

TRS, основанный на 2-арной функции

Определение 2-арной функции Аккермана приводит к очевидным правилам редукции [16] [17]

Пример

Вычислить

Последовательность сокращения: [n 3]

Для вычисления можно использовать стек , который изначально содержит элементы .

Затем повторно два верхних элемента заменяются в соответствии с правилами [n 4]

Схематически, начиная с :

WHILE длина стека <> 1{ ВСТАВИТЬ 2 элемента; ВСТАВИТЬ 1 или 2 или 3 элемента, применяя правила r1, r2, r3}

Псевдокод опубликован в работе Гроссмана и Цейтмана (1988).

Например, при вводе ,

Замечания

Их собственный алгоритм, по сути своей итеративный, производит вычисления во времени и пространстве.

TRS, основанный на итерированной 1-арной функции

Определение итерированных 1-арных функций Аккермана приводит к различным правилам редукции

Так как композиция функций ассоциативна, то вместо правила r6 можно определить

Как и в предыдущем разделе, вычисление можно реализовать с помощью стека.

Первоначально стек содержит три элемента .

Затем три верхних элемента многократно заменяются в соответствии с правилами [n 4]

Схематически, начиная с :

WHILE длина стека <> 1{ ВСТАВИТЬ 3 элемента; ВЫТЯНУТЬ 1 или 3 или 5 элементов, применяя правила r4, r5, r6;}

Пример

На входе последовательные конфигурации стека

Соответствующие равенства имеют вид

При использовании правила редукции r7 вместо правила r6 замены в стеке будут следующими

Последовательные конфигурации стека будут тогда

Соответствующие равенства имеют вид

Замечания

TRS, на основе гипероператоров

Как ясно показали Сундблад (1971) или Порто и Матос (1980), функция Аккермана может быть выражена через последовательность гиперопераций :

или, после удаления константы 2 из списка параметров, в терминах функции Бака

Функция Бака [10] , которая сама по себе является вариантом функции Аккермана, может быть вычислена с помощью следующих правил редукции:

Вместо правила b6 можно определить правило

Для вычисления функции Аккермана достаточно добавить три правила редукции

Эти правила учитывают базовый случай A(0,n), выравнивание (n+3) и подстановку (-3).

Пример

Вычислить

Соответствующие равенства имеют вид

Замечания

Огромные цифры

Чтобы продемонстрировать, как вычисление результатов происходит за много шагов и в большом количестве: [n 5]

Таблица значений

Вычисление функции Аккермана можно переформулировать в терминах бесконечной таблицы. Сначала разместите натуральные числа вдоль верхней строки. Чтобы определить число в таблице, возьмите число сразу слева. Затем используйте это число, чтобы найти требуемое число в столбце, заданном этим числом, и на одну строку выше. Если слева нет числа, просто посмотрите на столбец под заголовком «1» в предыдущей строке. Вот небольшая верхняя левая часть таблицы:

Числа, представленные здесь только с помощью рекурсивного возведения в степень или стрелок Кнута, очень велики и заняли бы слишком много места, если бы их записывать простыми десятичными цифрами.

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

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

Характеристики

Общие замечания

Не примитивно рекурсивный

Функция Аккермана растет быстрее, чем любая примитивно-рекурсивная функция , и поэтому сама по себе не является примитивно-рекурсивной. Набросок доказательства таков: примитивно-рекурсивная функция, определенная с использованием до k рекурсий, должна расти медленнее, чем , (k+1)-я функция в быстрорастущей иерархии, но функция Аккермана растет по крайней мере так же быстро, как .

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

Как только это установлено, следует, что само по себе не является примитивно рекурсивным, поскольку в противном случае подстановка привела бы к противоречию

Доказательство проводится следующим образом: определяется класс всех функций, которые растут медленнее функции Аккермана

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

Использование в вычислительной сложности

Функция Аккермана появляется во временной сложности некоторых алгоритмов [19], таких как системы сложения векторов [20] и достижимость сетей Петри [21] , таким образом показывая, что они вычислительно невыполнимы для больших примеров. Обратная функция Аккермана появляется в некоторых результатах временной сложности.

Обратный

Поскольку рассмотренная выше функция f ( n ) = A ( n , n ) растет очень быстро, ее обратная функция , f −1 , растет очень медленно. Эта обратная функция Аккермана f −1 обычно обозначается как α . Фактически, α ( n ) меньше 5 для любого практического размера входных данных n , поскольку A (4, 4) имеет порядок . 

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

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

Эта функция возникает при более точном анализе алгоритмов, упомянутых выше, и дает более точную временную границу. В структуре данных непересекающихся множеств m представляет собой количество операций, а n представляет собой количество элементов; в алгоритме минимального остовного дерева m представляет собой количество ребер, а n представляет собой количество вершин. Существует несколько немного отличающихся определений α ( m , n ) ; например, log 2 n иногда заменяется на n , а функция floor иногда заменяется на ceiling .

Другие исследования могут определить обратную функцию единицы, где m установлено равным константе, так что обратная функция применяется к конкретной строке. [22]

Обратная функция Аккермана является примитивно рекурсивной. [23]

Использовать как эталон

Функция Аккермана, благодаря своему определению в терминах чрезвычайно глубокой рекурсии, может использоваться в качестве эталона способности компилятора оптимизировать рекурсию. Первое опубликованное использование функции Аккермана таким образом было в 1970 году Драгошем Вайдой [24] и, почти одновременно, в 1971 году, Ингве Сундбладом. [14]

Основополагающая работа Сундблада была продолжена Брайаном Вихманном (соавтором эталонного теста Whetstone ) в трилогии статей, написанных между 1975 и 1982 годами. [25] [26] [27]

Смотрите также

Примечания

  1. ^ с обратным порядком параметров
  2. ^ ' карри '
  3. ^ На каждом шаге подчеркнутый редекс переписывается.
  4. ^ ab здесь: стратегия «самая левая-самая внутренняя»!
  5. ^ abcd Для лучшей читаемости
    S(0) обозначается как 1,
    S(S(0)) обозначается как 2,
    S(S(S(0))) обозначается как 3
    и т. д.
  6. ^ Максимальная глубина рекурсии относится к числу уровней активации процедуры, которые существуют во время самого глубокого вызова процедуры. Корнелиус и Кирби (1975)
  7. ^ ЦИКЛ n+1 РАЗ ДЕЛИТЬ F

Ссылки

  1. ^ Монин и Хинчи 2003, с. 61.
  2. ^ ab Аккерманн 1928.
  3. ^ "Десятичное разложение A(4,2)". kosara.net . 27 августа 2000 г. Архивировано из оригинала 20 января 2010 г.
  4. ^ Калуде, Маркус и Теви 1979.
  5. Гильберт 1926, стр. 185.
  6. ^ ван Хейеноорт 1977.
  7. Питер 1935.
  8. Робинсон 1948.
  9. Ричи 1965, стр. 1028.
  10. ^ abc Бак 1963.
  11. ^ Меуссен и Зантема 1992, стр. 6.
  12. ^ Мунафо 1999a.
  13. Ричи 1965.
  14. ^ ab Sundblad 1971.
  15. Порто и Матос 1980.
  16. ^ Гроссман и Цейтман 1988.
  17. ^ Полсон 2021.
  18. Коэн 1987, стр. 56, Предложение 3.16 (см. в корректуре).
  19. ^ Брубейкер 2023.
  20. ^ Червинский и Орликовский 2022.
  21. ^ Леру 2022.
  22. ^ Петти 2002.
  23. ^ Матос 2014.
  24. ^ Вайда 1970.
  25. ^ Вихманн 1976.
  26. ^ Вихманн 1977.
  27. ^ Вихманн 1982.

Библиография

Внешние ссылки