Ackermann function: Difference between revisions
Jump to navigation
Jump to search
imported>Dmitrii Kouznetsov (copypast the preamble from wikipedia.) |
(No difference)
|
Revision as of 07:18, 8 November 2008
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.
The Ackermann function is defined recursively for non-negative integers m and n as follows::
Its value grows rapidly; even for small inputs, for example A(4,2) contains 19,729 decimal digits [1].