Ackermann function

The Ackermann function \(A(x,y)\) is a recursive function which was originally invented by and later simplified by Rozsa Peter and then by Raphael M. Robinson. The exact definition of the Ackermann function varies slightly between authors.
== Definition ==
=== Original definition ===
Original definition of Ackermann function is as follows.Ackermann, Wilhelm (1928). "Zum Hilbertschen Aufbau der reellen Zahlen". Mathematische Annalen. 99: 118–133. 
\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).Takayuki Kihara "Ackermann function and Hilbert" (in Japanese) 数学セミナー July 2019, pp.22-27User_blog:Kyodaisuu/Reading Ackermann's paper
=== 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))\).Ackermann Function
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:THE ACKERMANN FUNCTION IN ELEMENTARY ALGEBRAIC GEOMETRY
*\(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:Goucher, Adam P. Fast-growing functions, part 1.
*\(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.Pettie, S. An Inverse-Ackermann Type Lower Bound For Online Minimum Spanning Tree Verification*. Combinatorica 26, 207–230 (2006). 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.
left|thumb|330x330px
== 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 ==
== Sources ==
de:Ackermannfunktion
ja:アッカーマン関数
zh:阿克曼函數
Category:Functions
Category:Eponymous functions