Ackermann function

Ackermann function
Based on	Successor function
Growth rate	\(f_{\omega}(n)\)

A page from Sushi Kokuu Hen demonstrating the Ackermann function.

The Ackermann function \(A(x,y)\) is a recursive function which was originally invented by Wilhelm Ackermann and later simplified by Rozsa Peter and then by Raphael M. Robinson. The exact definition of the Ackermann function varies slightly between authors.

View full site to see MathJax equation

Definition

Original definition

Original definition of Ackermann function is as follows.

\begin{align*} A(0,x,y)&:=x+y\\ A(n+1,x,y)&:=\underbrace{A(n,A(\cdots(A(n,x))\cdots)}_{y \text{times}} \end{align*} It can be expressed with Arrow notation, which was not devised when this function was defined, as \(A(n+2,x,y)=x\uparrow^n y\). It was defined in terms of higher-order primitive recursion (i.e., primitive recursion on functional).

Robinson's definition

Robinson's version is the most commonly-refered-to rendition of the Ackermann function and is defined as follows:

• \(A(x,y) = y + 1\) if \(x = 0\), else
• \(A(x,y) = A(x - 1,1)\) if \(y = 0\), otherwise,
• \(A(x,y) = A(x - 1,A(x,y - 1))\).

This function grows at a rate comparable to the lesser-known Sudan function.

The expansion of \(A(2,2)\) using Robinson's definition is given below as an example:

\[ \begin{array}{cclclcl} A(2,2) &=& A(1,A(2,1))\\ &=& A(1,A(1,A(2,0)))&&\\ &=& A(1,A(1,A(1,1)))\\ &=& A(1,A(1,A(0,A(1,0))))\\ &=& A(1,A(1,A(0,A(0,1))))\\ &=& A(1,A(1,A(0,2)))\\&=& A(1, A(1, 3))\\ &=& A(1, A(0, A(1, 2)))\\ &=& A(1, A(0, A(0, A(1, 1))))\\ &=& A(1, A(0, A(0, A(0, A(1, 0)))))\\ &=& A(1, A(0, A(0, A(0, A(0, 1)))))\\ &=& A(1, A(0, A(0, A(0, 2))))\\ &=& A(1, A(0, A(0, 3)))\\ &=& A(1, A(0, 4))\\ &=& A(1, 5)\\ &=& A(0, A(1, 4))\\ &=& A(0, A(0, A(1, 3)))\\ &=& A(0, A(0, A(0, A(1, 2))))\\ &=& A(0, A(0, A(0, A(0, A(1, 1)))))\\ &=& A(0, A(0, A(0, A(0, A(0, A(1, 0))))))\\ &=& A(0, A(0, A(0, A(0, A(0, A(0, 1))))))\\ &=& A(0, A(0, A(0, A(0, A(0, 2)))))\\ &=& A(0, A(0, A(0, A(0, 3))))\\ &=& A(0, A(0, A(0, 4)))\\ &=& A(0, A(0, 5))\\ &=& A(0, 6)\\ &=& 7 \end{array} \]

The Ackermann function is related to Knuth's up-arrow notation and Hyper operators in the following way:

\(A(x,y) = 2\uparrow^{x-2}(y+3)-3 = 2[x](y+3)-3\).

It is thus capable of significantly fast growth rates. For example, \(A(4,2)\) computes to the following value:

\(A(4,2) = (2 \uparrow^{2}5) -3 = 2 \uparrow\uparrow 5 -3 = 2 \uparrow 2 \uparrow 2 \uparrow 2 \uparrow 2 -3 = 2^{2^{2^{2^{2}}}}-3 \approx 2.003529930 \times 10^{19,728}\)

Friedman's definition

Harvey Friedman defined the Ackermann function \(A(x,y)\) (\(x,y > 0\)) like so:

• \(A(x,y) = 2\) (if \(y=1\))
• \(A(x,y) = 2y\) (if \(x=1\) and \(y > 1\))
• \(A(x,y) = A(x-1,A(x,y-1))\) (if \(x > 1\) and \(y > 1\))

According to this definition, \(A(x,y)\) is defined for any positive integers \(x\) and \(y\), and equal to \(2 \uparrow^{x-1} y\).

Goucher's definition

A.P. Goucher proposed the following definition of the Ackermann function in his blog post:

• \(f_1(n)=n+2\)
• \(f_{m+1}(n) = f_m^n(2)\)
• \(A(n) = f_n(n)\)

The post describes yet another variant of the this function that is related to the following problem:

Given a row of boxes, and some number of coins in each, we can pick one box and operate by one of the following rules:

• Remove one coin from this box and add two coins in the box n+1.
• Remove one coin from this box and invert the number of coins in boxes n+1 and n+2.

We can choose a strategy of picking boxes and applying rules for them. Consider the situation when all boxes except the rightmost one are empty. Now, given a row of n boxes with one coin in each of them, f(n) is the largest number of coins in the rightmost box. Computing exact values of this function can be tricky, but it is trivial to see that \(f(1) = 1\), \(f(2) = 3\) and \(f(3) = 7\). Proving that \(f(4) = 28\) is slightly harder.

For non-integers

CompactStar defined for non-negative real numbers x and y:

• \(x < 1: A(x, y) = x + y + 1\)
• \(x \geq 1, y < 1: A(x, y) = A(x - 1, y \cdot A(x - 1, 1) - y + 1)\)
• \(x \geq 1, y \geq 1: A(x, y) = A(x - 1, A(x, y - 1))\)

Under this definition:

\(A(0.5, y) = y + 1.5\)

\(A(1.5, y) = 1.5y + 2.5\)

\(A(2.5, y) = 9 \cdot 1.5^{y} - 5\)

\(A(e, \pi) \approx 42.16412690081622\)

\(A(\pi, e) \approx 3446961975442.875\)

Other trivia

Ackermann numbers are defined with the original definition of the Ackermann function.

In googology, the Ackermann function may alternatively refer to the single-argument function \(A(n) = A(n, n)\) which diagonalizes over the two-variable counterpart. \(A(n)\) is also known as the gag function.

The function \begin{eqnarray*} \lambda \colon \mathbb{N}^2 & \to & \mathbb{N} \\ (i,n) & \mapsto & \lambda_i(n) \end{eqnarray*} defined by \begin{eqnarray*} \lambda_i(n) = \min \{j \in \mathbb{N} \mid A(i,j) \geq n\}, \end{eqnarray*} which is also denoted by \(\alpha(i,n)\), is called the inverse of the Ackermann function and the inverse-Ackermann function, although it is not the inverse map of the non-bijective map \(A \colon \mathbb{N}^2 \to \mathbb{N}\) itself. Since \(A(m, n)\) grows somewhat rapidly, the inverse Ackermann function consequently grows very slowly. Interestingly, it has seen applications in time complexity theory.

Wilhelm's original function was devised to show the existence of computable functions that are not primative-recursive, as that had been an open question at the time.

Computerphile description of the Ackermann function

Computation Programs

• 巨大数：アッカーマン関数のC++実装 (C++ program for computation of Ackermann function)
• アッカーマン関数計算過程表示プログラム (javascript program for computation of Ackermann function)
• Aycabta, Ackermann, github repository, 2012. (ruby, java, and C programs for computation of Ackermann function)
• ふぃっしゅ, Ackermann github repository, 2018 (python program for computation of Ackermann function)
• koteitan, ack, github repository, 2022. (C++ program for computation of Ackermann function)
• Mitsuki1729, アッカーマン関数 scratch巨大数選手権コンテスト, scratch. (scratch program for computation of Ackermann function)

See also

Googology in Japan

Original numbers, functions, notations, and notions

By Aeton: Okojo numbers · N-growing hierarchy
By 新井 (Arai): Arai's psi function
By aster: White-aster notation · White-aster
By バシク (BashicuHyudora): Primitive sequence number · Pair sequence number · Bashicu matrix system 1/2/3/4 original idea
By ふぃっしゅ (Fish): Fish numbers (Fish number 1 · Fish number 2 · Fish number 3 · Fish number 4 · Fish number 5 · Fish number 6 · Fish number 7 · S map · SS map · s(n) map · m(n) map · m(m,n) map) · Bashicu matrix system 1/2/3/4 formalisation · TR function (I0 function)
By Gaoji: Weak Buchholz's function
By じぇいそん (Jason): Irrational arrow notation · δOCF · δφ · ε function
By 甘露東風 (Kanrokoti): KumaKuma ψ function
By koteitan: Bashicu matrix system 2.3
By mrna: 段階配列表記 · 降下段階配列表記 · 多変数段階配列表記 · SSAN · S-σ
By Naruyoko Naruyo: Y sequence formalisation · ω-Y sequence formalisation
By Nayuta Ito: N primitive · Flan numbers (Flan number 1 · Flan number 2 · Flan number 3 · Flan number 4 version 3 · Flan number 5 version 3) · Large Number Lying on the Boundary of the Rule of Touhou Large Number 4 · Googology Wiki can have an article with any gibberish if it's assigned to a number
By Okkuu: Extended Weak Buchholz's function
By p進大好きbot: Ordinal notation associated to Extended Weak Buchholz's function · Ordinal notation associated to Extended Buchholz's function · Naruyoko is the great · Large Number Garden Number
By たろう (Taro): Taro's multivariable Ackermann function
By ゆきと (Yukito): Hyper primitive sequence system · Y sequence original idea · YY sequence · Y function · ω-Y sequence original idea

Methodology

By バシク (BashicuHyudora): Bashicu matrix system as a notation template
By じぇいそん (Jason): Shifting definition
By mrna: Side nesting
By Nayuta Ito and ゆきと (Yukito): Difference sequence system

Implementation of existing works into programs

By ふぃっしゅ (Fish): Ackermann function
By koteitan: Ackermann function · Beklemishev's worms · KumaKuma ψ function
By Mitsuki1729: Ackermann function · Graham's number · Conway's Tetratri · Fish number 1 · Fish number 2 · Laver table
By みずどら: White-aster notation
By Naruyoko Naruyo: p進大好きbot's Translation map for pair sequence system and Buchholz's ordinal notation · KumaKuma ψ function · Naruyoko is the great
By 猫山にゃん太 (Nekoyama Nyanta): Flan number 4 version 3 · Fish number 5 · Laver table
By Okkuu: Fish number 1 · Fish number 2 · Fish number 3 · Fish number 5 · Fish number 6
By rpakr: p進大好きbot's ordinal notation associated to Extended Weak Buchholz's function · Standardness decision algorithm for Taranovsky's ordinal notation

Proofs, translation maps for analysis schema, and other mathematical contributions

By ふぃっしゅ (Fish): Computing last 100000 digits of mega · Approximation method for FGH using Arrow notation · Translation map for primitive sequence system and Cantor normal form
By Kihara: Proof of an estimation of TREE sequence · Proof of the incomparability of Busy Beaver function and FGH associated to Kleene's \(\mathcal{O}\)
By koteitan: Translation map for primitive sequence system and Cantor normal form
By Naruyoko Naruyo: Translation map for Extended Weak Buchholz's function and Extended Buchholz's function
By Nayuta Ito: Comparison of Steinhaus-Moser Notation and Ampersand Notation
By Okkuu: Verification of みずどら's computation program of White-aster notation
By p進大好きbot: Proof of the termination of Hyper primitive sequence system · Proof of the termination of Pair sequence number · Proof of the termination of segements of TR function in the base theory under the assumption of the \(\Sigma_1\)-soundness and the pointwise well-definedness of \(\textrm{TR}(T,n)\) for the case where \(T\) is the formalisation of the base theory

Entertainments

By 小林銅蟲 (Kobayashi Doom): Sushi Kokuu Hen
By koteitan: Dancing video of a Gijinka of Fukashigi · Dancing video of a Gijinka of 久界 · Storyteller's theotre video reading Large Number Garden Number aloud

See also: Template:Googology in Asia