Ackermann Function

In computability theory, the Ackermann function or Ackermann-Péter function is a simple example of a computable function that is not primitive recursive. The set of primitive recursive functions is a subset of the set of general recursive functions. Ackermann's function is an example that shows that the former is a strict subset of the latter. ^[1].

Definition[edit]

The Ackermann function is defined recursively for non-negative integers m and n as follows::

${\displaystyle A(m,n)=\{\begin{array}{ll}n+1& \text{if }m=0\\ A(m-1,1)& \text{if }m>0\text{ and }n=0\\ A(m-1,A(m,n-1))& \text{if }m>0\text{ and }n>0.\end{array}}$

Rapid growth[edit]

Its value grows rapidly; even for small inputs, for example A(4,2) contains 19,729 decimal digits ^[2].

Holomorphic extensions[edit]

The lowest Ackermann functions allow the extension to the complex values of the second argument. In particular,

${\displaystyle A(0,z)=z+1}$

${\displaystyle A(1,z)=z+2=2+(n+3)-3}$

${\displaystyle A(2,z)=2z+3=2\cdot (n+3)-3}$

The 3th Ackermann function is related to the exponential on base 2 through

${\displaystyle A(3,z)={\exp }_2(z+3)-3=2^{z+3}-3}$

The 4th Ackermann function is related to tetration on base 2 through

${\displaystyle A(4,z)={\mathrm{t}\mathrm{e}\mathrm{t}}_2(z+3)-3}$

which allows its holomorphic extension for the complex values of the second argument. ^[3]

For ${\displaystyle n>4}$ no holomorphic extension of ${\displaystyle A(n,z)}$ to complex values of ${\displaystyle z}$ is yet reported.

References[edit]

1. ↑ Wilhelm Ackermann (1928). "Zum Hilbertschen Aufbau der reellen Zahlen". Mathematische Annalen 99: 118–133. DOI:10.1007/BF01459088. Research Blogging.
2. ↑ Decimal expansion of A(4,2)
3. ↑ D. Kouznetsov. Ackermann functions of complex argument. Preprint ILS, 2008, http://www.ils.uec.ac.jp/~dima/PAPERS/2008ackermann.pdf