Ackermann function

From Knowino
Jump to: navigation, search

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].


[edit] Definition

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

 A(m, n) =  \begin{cases}  n+1 & \mbox{if } m = 0 \\  A(m-1, 1) & \mbox{if } m > 0 \mbox{ and } n = 0 \\  A(m-1, A(m, n-1)) & \mbox{if } m > 0 \mbox{ and } n > 0.  \end{cases}

[edit] Rapid growth

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

[edit] Holomorphic extensions

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

A(0,z) = z + 1
 A(1,z) =z+2=2+(n\!+\!3)-3
 A(2,z) =2z+3=2\!\cdot\!(n\!+\!3)-3

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

 A(3,z) = \exp_2(z\!+\!3)-3=2^{z+3}-3

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

A(4,z) = tet2(z + 3) − 3

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

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

[edit] References

  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,
Information.svg Some content on this page may previously have appeared on Citizendium.
Personal tools