Функция Аккермана и её вычисление

Оригинальная функция Аккермана

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

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

function f0 (a, b) {
  return a + b
}

function f1 (a, b) {
  if (b == 0)
    return 0
  return f0(a, f1(a, b - 1))
}

function f2 (a, b) {
  if (b == 0)
    return 1
  return f1(a, f2(a, b - 1))
}

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

function f3 (a, b) {
  if (b == 0)
    return 1
  return f2(a, f3(a, b - 1))
}

Если все эти операции объединяет единый принцип, значит мы можем упростить работу с ними, перенеся индекс из названия функции в список её параметров. То есть вместо нескольких функций f0, f1, f2, ..., мы определим одну - f (n, a, b), или, еще лучше А (n, a, b). Это и будет функция Аккермана, в том виде, как её определил сам Аккерман. Поскольку сложение — это базовый случай, несводимый к другим, первая часть функции уже готова:

function A (n, a, b) {
  if (n == 0)
    return a + b
  // ???
}

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

function I (f, v, n) {
  if (n == 0)
    return v
  return f(I(f, v, n - 1))
}

Здесь f — функция от одного аргумента, v — значение аргумента, n — количество повторений.

Последний шаг — это определить значение функции Аккермана при b == 0. Для умножения оно будет равно 0, для возведения в степень 1, для всех последующих функций — значению аргумента a (так у Аккермана).

function init (a, n) {
  if (n == 1)
    return 0
  if (n == 2)
    return 1
  return a
}

Теперь у нас есть все, чтобы реализовать функцию Аккермана.

function A (a, b, n) {
  if (n == 0)
    return a + b
  return I(x => A(a, x, n - 1), init(a, n), b)
}

Здесь функция Аккермана итерируется по параметру b. Для краткости мы использовали стрелочную функцию языка JavaScript.

Нетрудно убедится, что значения A(a, b, 1) соответствуют умножению a на b, А(a, b, 2) — возведению a в степень b и так далее (с учетом выбора начального значения).

Упрощенная функция Аккермана от двух аргументов

Теперь рассмотрим упрощенный вариант непримитивно-рекурсивной функции, предложенный Розой Петер и Рафаэлем Робинсоном.

Главный принцип, положенный в основу этого варианта функции Аккермана — явное использование двойной рекурсии:

function A (m, n) {
  // ...
  return A(m - 1, A(m, n - 1))
}

Очевидно, остаётся разобраться с двумя базовыми случаями: один для m == 0, другой для n == 0. Для удобства доказательства непримитивно-рекурсивной природы этой функции, начальные случаи принимаются такими: A(0, n) = n + 1 - чтобы для каждых m, n выполнялось условие A(m, n) > n и A(m, 0) = A(m - 1, 1), чтобы для каждых m, n выполнялось условие A(m + 1, n) > A(m, n + 1). Таким образом, окончательный вариант функции Аккермана от двух аргументов выглядит так:

Мемоизация

Попробуем оптимизировать вычисление функции Аккермана с помощью мемоизации (memoization — от memory optimization). При первом вызове функции с определёнными аргументами её результат сохраняется в памяти (в данном случае, в словаре Map). При повторном вызове с теми же аргументами функция возвращает сохранённый результат, избегая повторных вычислений.

function M (f) {
  const m = new Map()
  return function(...rest) {
    const s = JSON.stringify(rest)
    if (m.has(s))
      return m.get(s)
    const v = f(...rest)
    m.set(s, v)
    return v
  }
}

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

Посмотрим, насколько нам удалось оптимизировать вычисления:

С помощью мемоизации можно добиться впечатляющего ускорения рекурсивных вычислений, однако мы по-прежнему не можем вычислить такое, например, значение как A(3, 20) из-за переполнения стека вызовов. Это явный признак, что пора переходить от рекурсии к итерации.

Итеративный подход

Воспользуемся методом итеративного вычисления функции Аккермана, предложенной Гроссманом и Зейтман. Он основывается на том наблюдении, что результаты вычисления функции Аккермана можно организовать в таблицу, где строками будут значения функции при фиксированном m, а столбцами — значения функции при фиксированном n.

1 2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9  
3 5 7 9  
5

Рассмотрим как формируется эта таблица на примере третьей строки таблицы (т. е. при m = 2): Нулевой элемент — это всегда первый элемент предыдущей (в данном случае, второй) строки, в данном случае это 3. Значит, следующий элемент — это третий элемент второй строки, в данном случае это 5. Значит, следующий элемент — пятый элемент второй строки, в данном случае это 7... и так далее.

На основании этого принципа, легко перейти к итеративному вычислению функции Аккермана:

С помощью итеративной реализации мы можем ускорить процесс вычисления, а кроме того вычислять такие значения функции, которые невозможно вычислить рекурсивным методом из-за ограничения размера стека вызовов, например, A(3, 20). Все же значение A(4, 2) будет вычисляться слишком долго даже итеративным способом.

Гипероператоры

Попробуем вычислить значение функции Аккермана с помощью гипероператоров. Известно, что A(m, n) == Hm(2, n + 3) - 3, где Hm — это гипероператор уровня m.

Хорошая новость в том, что функция, вычисляющая значения гипероператоров, у нас уже есть — это самая первая функция Аккермана, которую мы реализовали. С некоторыми поправками и оптимизациями теперь она выглядит так:

function H (a, b, n) {
  if (n == 0n)
    return b + 1n
  if (n == 1n)
    return a + b
  if (n == 2n)
    return a * b
  if (n == 3n)
    return a ** b
  return I(x => H(a, x, n - 1n), 1n, b)
}

Что изменилось:

• Нулевой оператор теперь не сложение, а "следующий за"
• Используются числовые литералы типа BigInt, поскольку результат вычисления может быть непредставим в формате 64-битного числа с плавающей точкой, который используется для числовых литералов в языке JavaScript по умолчанию
• Начальное значение для гипероператоров при n > 3 равно 1, а не a
• Случаи для n <= 3 вычисляются операторами языка JavaScript

Теперь мы можем вычислить функцию Аккермана так:

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

Свёртка

В качестве демонстрации возможностей функции свёртки, приведем реализацию функции Аккермана из статьи Грэма Хаттона "Руководство по универсальности и выразительности свёртки".

Поскольку функция свёртки работает с последовательностями, а функция Аккермана — с числами, в качестве чисел будем использовать массивы соответствующей длины, заполненные произвольными элементами. Ноль представлен пустым массивом [], единица - массивом из одного элемента [1], прибавление единицы - добавлением одного элемента к массиву: [1, ...n]. В качестве операции свертки будем использовать метод reduce встроенного объекта Array.

Вычисление производится в два этапа: сначала на основании аргумента m вычисляется функция, которая принимает аргумент n, и уже она вычисляет конечный результат, то есть массив, длина которого равна значению функции Аккермана для данных m, n.

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

function A (m) { 
  return I(
    f => n => I(x => f(x), f(1), n),
    n => n + 1, m)
}

Интересные ссылки:

• Zum Hilbertsehen Aufbau der reellen Zahlen
• Versions of Ackermann's Function
• An inherently iterative computation of Ackermann function
• A tutorial on the universality and expressiveness of fold