| Ackermann Function |
Website Links For Ackermann |
Information AboutAckermann Function |
| CATEGORIES ABOUT ACKERMANN FUNCTION | |
| arithmetic | |
| large numbers | |
| special functions | |
| theory of computation | |
| recursion theory | |
|
HISTORY In the late 1920s, the mathematicians Gabriel Sudan and Wilhelm Ackermann , students of David Hilbert , were studying the foundations of computation. Sudan is credited with inventing the lesser-known Sudan Function , the first published function that is recursive but not primitive-recursive. Shortly afterwards and independently, in 1928, Ackermann published his own recursive but non-primitive recursive function. {Link without Title} Ackermann originally considered a function ''A''(''m'', ''n'', ''p'') of three variables, the ''p''-fold iterated exponentiation of ''m'' with ''n'', or ''m'' → ''n'' → ''p'' as expressed using the Conway Chained Arrow . When ''p'' = 1, this is ''m''''n'', which is ''m'' multiplied by itself ''n'' times. When ''p'' = 2, it is a tower of exponents with ''n'' levels, or ''m'' raised ''n'' times to the power ''m'' also written as ''n''''m'', the Tetration of ''m'' with ''n''. We can continue to generalize this indefinitely as ''p'' becomes larger. 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, a former student and Hilbert’s personal secretary, 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. The paper also outlines a proof of the Continuum Hypothesis and was central in influencing Kurt Gödel to study the Completeness And Consistency Of Mathematics leading to Gödel's Incompleteness Theorem . 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. DEFINITION AND PROPERTIES The Ackermann function is defined Recursively for non-negative integers ''m'' and ''n'' as follows: : 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). or the Hyper Operator s: A 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) cannot be recorded in the physical universe. 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 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 surprising 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:
An attempt to express the fourth Ackermann number, 44, using a Power Tower as above would become extremely complicated. SEE ALSO REFERENCES
EXTERNAL LINKS
|
|
|