Ackermann function: Difference between revisions
imported>Dmitrii Kouznetsov m (Make sections. Add Holomorphic extension and references. The wikipedia artilce still looks much better.) |
imported>Meg Taylor (update template) |
||
| (6 intermediate revisions by 3 users not shown) | |||
| Line 3: | Line 3: | ||
<ref>{{cite journal | author=Wilhelm Ackermann | journal=[[Mathematische Annalen]] | title=''Zum Hilbertschen Aufbau der reellen Zahlen'' | year=1928 | volume=99 | pages=118–133 | doi=10.1007/BF01459088}}</ref>. | <ref>{{cite journal | author=Wilhelm Ackermann | journal=[[Mathematische Annalen]] | title=''Zum Hilbertschen Aufbau der reellen Zahlen'' | year=1928 | volume=99 | pages=118–133 | doi=10.1007/BF01459088}}</ref>. | ||
== | ==Definition== | ||
The Ackermann function is defined [[recursion|recursively]] for non-negative integers ''m'' and ''n'' as follows:: | The Ackermann function is defined [[recursion|recursively]] for non-negative integers ''m'' and ''n'' as follows:: | ||
| Line 12: | Line 12: | ||
A(m-1, A(m, n-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} | \end{cases} | ||
</math> | </math> | ||
==Rapid growth== | ==Rapid growth== | ||
Its value grows rapidly; even for small inputs, for example A(''4,2'') contains 19,729 decimal digits <ref>[http://www.kosara.net/thoughts/ackermann42.html Decimal expansion of A(4,2)]</ref>. | Its value grows rapidly; even for small inputs, for example A(''4,2'') contains 19,729 decimal digits <ref>[http://www.kosara.net/thoughts/ackermann42.html Decimal expansion of A(4,2)]</ref>. | ||
==Holomorphic extensions== | ==Holomorphic extensions== | ||
| Line 21: | Line 21: | ||
:<math> A(0,z) =z+1</math> | :<math> A(0,z) =z+1</math> | ||
:<math> A(1,z) =z+2=2+(n\!+\!3)-3</math> | :<math> A(1,z) =z+2=2+(n\!+\!3)-3</math> | ||
:<math> A( | :<math> A(2,z) =2z+3=2\!\cdot\!(n\!+\!3)-3</math> | ||
The 3th Ackermann function is related to the exponential on base 2 through | The 3th Ackermann function is related to the exponential on base 2 through | ||
:<math> A(3,z) = \exp_2(z\!+\!3)-3=2^{z+3}-3</math> | :<math> A(3,z) = \exp_2(z\!+\!3)-3=2^{z+3}-3</math> | ||
| Line 31: | Line 31: | ||
D. Kouznetsov. Ackermann functions of complex argument. Preprint ILS, 2008, | D. Kouznetsov. Ackermann functions of complex argument. Preprint ILS, 2008, | ||
http://www.ils.uec.ac.jp/~dima/PAPERS/2008ackermann.pdf | http://www.ils.uec.ac.jp/~dima/PAPERS/2008ackermann.pdf | ||
</ref> | </ref> | ||
For <math>n>4</math> no holomorphic extension of <math>A(n,z)</math> to complex values of <math>z</math> is yet reported. | For <math>n>4</math> no holomorphic extension of <math>A(n,z)</math> to complex values of <math>z</math> is yet reported. | ||
==References== | ==References== | ||
{{reflist}} | |||
Latest revision as of 06:37, 13 September 2013
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
The Ackermann function is defined recursively for non-negative integers m and n as follows::
Rapid growth
Its value grows rapidly; even for small inputs, for example A(4,2) contains 19,729 decimal digits [2].
Holomorphic extensions
The lowest Ackermann functions allow the extension to the complex values of the second argument. In particular,
The 3th Ackermann function is related to the exponential on base 2 through
The 4th Ackermann function is related to tetration on base 2 through
which allows its holomorphic extension for the complex values of the second argument. [3]
For no holomorphic extension of to complex values of is yet reported.
References
- ↑ Wilhelm Ackermann (1928). "Zum Hilbertschen Aufbau der reellen Zahlen". Mathematische Annalen 99: 118–133. DOI:10.1007/BF01459088. Research Blogging.
- ↑ Decimal expansion of A(4,2)
- ↑ D. Kouznetsov. Ackermann functions of complex argument. Preprint ILS, 2008, http://www.ils.uec.ac.jp/~dima/PAPERS/2008ackermann.pdf