Ackermann function

From Citizendium
Revision as of 21:28, 4 January 2011 by imported>John Stephenson (→‎Definiton: typo)
Jump to navigation Jump to search
This article is developing and not approved.
Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
This editable Main Article is under development and subject to a disclaimer.

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

  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