| Ackermann Function |
Article Index for Ackermann |
Website Links For Ackermann |
Information AboutAckermann Function |
| CATEGORIES ABOUT ACKERMANN FUNCTION | |
| arithmetic | |
| large numbers | |
| special functions | |
| theory of computation | |
| recursion theory | |
|
HISTORY Ackermann proved that ''A'' is a recursive function, a function a computer with unbounded memory can calculate, but it is not a Primitive Recursive Function , a class of functions including almost all familiar functions such as addition and Factorial . In ''On the Infinite'', David Hilbert hypothesized that the Ackermann function was not primitively recursive, but it was Ackermann, Hilbert’s personal secretary and former student, who actually proved the hypothesis in his paper ''On Hilbert’s Construction of the Real Numbers''. ''On the Infinite'' was Hilbert’s most important paper on the foundations of mathematics, serving as the heart of Hilbert's Program to secure the foundation of transfinite numbers by basing them on finite methods.3 von Heijenoort. From Frege To Gödel , 1967. A similar function of only two variables was later defined by Rózsa Péter and Raphael Robinson ; its definition is given below. The numbers, except in the first few rows, are three less than powers of two. For the exact relation between the two functions, see below.4 DEFINITION AND PROPERTIES The Ackermann function is defined Recursively for non-negative integers ''m'' and ''n'' as follows (this presentation is due to Rózsa Péter ): It may not be immediately obvious that the evaluation of these functions always terminates. The recursion is bounded because in each recursive application either ''m'' decreases, or ''m'' remains the same and ''n'' decreases. Each time that ''n'' reaches zero, ''m'' decreases, so ''m'' eventually reaches zero as well. (Expressed more technically, in each case the pair (''m'', ''n'') decreases in the Lexicographic Order , which preserves the Well-order ing of the non-negative integers.) However, when ''m'' decreases there is no upper bound on how much ''n'' can increase — and it will often increase greatly. The Ackermann function can also be expressed nonrecursively using Conway Chained Arrow notation: A hence :2 → ''n'' → ''m'' = ''A''(''m''+2,''n''-3) + 3 for ''n''>2 (''n''=1 and ''n''=2 would correspond with ''A''(''m'',−2) = −1 and ''A''(''m'',−1) = 1, which could logically be added), the Hyper Operator s: A and the indexed version of Knuth's Up-arrow Notation : ::''A''(''m'', ''n'') = The part of the definition ''A''(''m'', 0) = A(''m''-1, 1) corresponds to . For small values of ''m'' like 1, 2, or 3, the Ackermann function grows relatively slowly with respect to ''n'' (at most Exponentially ). For ''m'' ≥ 4, however, it grows much more quickly; even ''A''(4, 2) is about 2×1019728, and the decimal expansion of ''A''(4, 3) is very large by any typical measure. If we define the function ''f'' (''n'') = ''A''(''n'', ''n''), which increases both ''m'' and ''n'' at the same time, we have a function of one variable that dwarfs every primitive recursive function, including very fast-growing functions such as the Exponential Function , the factorial function, multi- and Superfactorial functions, and even functions defined using Knuth's up-arrow notation (except when the indexed up-arrow is used). This extreme growth can be exploited to show that ''f'', which is obviously computable on a machine with infinite memory such as a Turing Machine and so is a Computable Function , grows faster than any primitive recursive function and is therefore not primitive recursive. Though the Ackermann function is often used to debunk the hypothesis that all useful or simple functions are primitive recursive, one should not confuse the ''primitive recursive'' functions with those definable by ''primitive recursion'' (it is this latter class that is of interest to programming language theorists because programs written using only primitive recursion are guaranteed to terminate). In a category with exponentials, using the isomorphism , the Ackermann function may be defined via primitive recursion over higher-order functionals as follows: where ''Succ'' is the usual successor function and ''Iter'' is defined by primitive recursion as well: Another interesting class of functions are the Busy Beaver functions grow faster than any recursive function, and indeed it can be shown that if they could be evaluated in general, we could solve the Halting Problem so evaluation using an algorithm is impossible. One interesting aspect of the Ackermann function is that the only arithmetic operations it ever uses are addition and subtraction of 1. Its properties come solely from the power of unlimited Recursion . This also implies that its running time is at least proportional to its output, and so is also extremely huge. In actuality, for most cases the running time is far larger than the output; see below. TABLE OF VALUES Computing the Ackermann function can be restated in terms of an infinite table. We place the natural numbers along the top row. To determine a number in the table, take the number immediately to the left, then look up the required number in the previous row, at the position given by the number just taken. If there is no number to its left, simply look at column 1 in the previous row. Here is a small upper-left portion of the table:
|
|
|
|
|