Ackermann function

| Main Article
| Discussion
| Related Articles  [?]
| Bibliography  [?]
| External Links  [?]
| Citable Version  [?]

|
|
|
|
|
|
|
|

This editable Main Article is under development and subject to a disclaimer.

[edit intro]

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

## Contents

* 1 Definition
* 2 Rapid growth
* 3 Holomorphic extensions
* 4 References

## Definition[edit]

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

A ( m , n ) = { n + 1 if m = 0 A ( m − 1 , 1 ) if m > 0 and n = 0 A ( m − 1 , A ( m , n − 1 ) ) if m > 0 and n > 0. {\displaystyle 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}}}

## 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,

A ( 0 , z ) = z + 1 {\displaystyle A(0,z)=z+1}
A ( 1 , z ) = z + 2 = 2 + ( n + 3 ) − 3 {\displaystyle A(1,z)=z+2=2+(n\\!+\\!3)-3}
A ( 2 , z ) = 2 z + 3 = 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

A ( 3 , z ) = exp 2 ⁡ ( z + 3 ) − 3 = 2 z + 3 − 3 {\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

A ( 4 , z ) = t e t 2 ( z + 3 ) − 3 {\displaystyle A(4,z)=\mathrm {tet} _{2}(z+3)-3}

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

For  n > 4 {\displaystyle n>4} no holomorphic extension of  A ( n , z ) {\displaystyle A(n,z)} to complex values of  z {\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