Ackermann function: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Dmitrii Kouznetsov
(copypast the preamble from wikipedia.)
 
imported>Dmitrii Kouznetsov
(<references/>)
Line 1: Line 1:
{{subpages}}
In [[computability theory]], the '''Ackermann function''' or '''Ackermann-Péter function''' is a simple example of a [[computable function]] that is not [[Primitive recursive function|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.
In [[computability theory]], the '''Ackermann function''' or '''Ackermann-Péter function''' is a simple example of a [[computable function]] that is not [[Primitive recursive function|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.


Line 12: Line 13:


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>.
==References==
<references/>

Revision as of 07:22, 8 November 2008

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.

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

References