Ackermann function: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Dmitrii Kouznetsov
mNo edit summary
 
(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&ndash;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&ndash;133 | doi=10.1007/BF01459088}}</ref>.


==Definiton==
==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 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==
<references/>
{{reflist}}[[Category:Suggestion Bot Tag]]

Latest revision as of 07:01, 6 July 2024

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