Ackermann function is a former featured article. Please see the links under Article milestones below for its original nomination page (for older articles, check the nomination archive) and why it was removed. | ||||||||||||||||||||||
This article appeared on Wikipedia's Main Page as Today's featured article on September 24, 2004. | ||||||||||||||||||||||
|
This article is rated B-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||||||||||||||||||||||
|
This article has a mistake somewhere in the definitions. I wrote a C program based on what is here, and it simply goes in an endless loop for m = 4 (A(4,n)). It does not terminate, as the definition states. -- Gesslein 16:58, 4 October 2006 (UTC)
Here's a few values of the Ackermann function. Not so surprisingly, my program didn't get any further.
A(0,0) = 1 A(0,1) = 2 A(0,2) = 3 A(0,3) = 4 A(0,4) = 5 A(0,5) = 6 A(0,6) = 7 A(0,7) = 8 A(0,8) = 9 A(0,9) = 10
A(1,0) = 2 A(1,1) = 3 A(1,2) = 4 A(1,3) = 5 A(1,4) = 6 A(1,5) = 7 A(1,6) = 8 A(1,7) = 9 A(1,8) = 10 A(1,9) = 11
A(2,0) = 3 A(2,1) = 5 A(2,2) = 7 A(2,3) = 9 A(2,4) = 11 A(2,5) = 13 A(2,6) = 15 A(2,7) = 17 A(2,8) = 19 A(2,9) = 21
A(3,0) = 5 A(3,1) = 13 A(3,2) = 29 A(3,3) = 61 A(3,4) = 125 A(3,5) = 253 A(3,6) = 509 A(3,7) = 1021 A(3,8) = 2045 A(3,9) = 4093
A(4,0) = 13 A(4,1) = 65533 (Didn't use program for this one, but should be right.)
Κσυπ Cyp 17:07, 18 Oct 2003 (UTC)
Hi, NIST gives a different version [1] of this function, which seems incompatible with the veresion given here. Are they just plain wrong? -- Pakaran 03:34, 25 Nov 2003 (UTC)
Please see section 14 below.
One of the table entries looks messed up under IE. Can someone with more knowledge of the pampering of IE fix this? Thanks. Pakaran . 20:55, 27 Feb 2004 (UTC)
It may be noted that A(4, 2), which appears as a decimal expansion in several web pages, cannot possibly be computed by recursive application of the Ackermann function.
How, then? --
Fibonacci 21:06, 31 Jul 2004 (UTC)
Did anybody notice that except for the absence of a few ':' characters, that pseudo code is valid Python. -- 83.146.34.206 06:23, 24 Sep 2004 (UTC)
The inverse of the function f is less than 4 for any conceivable input size, so for practical algorithm analysis, it can be regarded as a constant.
Just a note: in the introduction it states, "In mathematics and computer science, the Ackermann function (also known as Ackermann-Peter function) is an important example in the theory of computation.", but doesn't say what the Ackermann function is an important example of. - Seth Mahoney 22:06, Sep 24, 2004 (UTC)
I think it is supposed to be an example of "A function of two parameters whose value grows very fast" according to [2]. Kirbytime 02:17, 24 March 2006 (UTC)
If I understood the Aaronson article (under "References") correctly, the Ackermann function extends the line of operations "addition, multiplication, exponential" to "tetration, pentation" and so forth. So you have:
A(1) = 1 + 1 A(2) = 2 * 2 A(3) = 3 ^ 3 = (3 * 3) * 3 A(4) = 4 tetrated 4 = ((4 ^ 4) ^ 4) ^ 4 A(5) = 5 pentated 5 = (((5 tetrated 5) tetrated 5) tetrated 5) tetrated 5 ...
The definition of the function in the Wikipedia article seems to be different, but the "Explicit description" section says something about "[...] iterated exponentiation, iteration of this operation and so on", so it sounds like the essence is the same in the two definitions.
I just stumbled across this article because it was featured, so I'm not a mathematician and thus don't really know what I'm talking about here! However, if the Ackermann function really has an as simple intuitive meaning as this, maybe there should be a table showing this, like the one I just wrote.
---the original definition by Ackermann was a 3 termed function A(m,n,p) where p=1=>m+n, p=2=>m*n, etc. This 1 term function is closely related, but not the same, though it is what is usually referred to as the Ackermann function
At the end of the section about Inverse we can read:
Here's an example of a modified Ackermann function which simplifies the explicit formulas for each level in the hierarchy. This function is defined for positive integers m,n both starting at 1 instead of 0:
This function meets:
A(1,n) = 1 + 1 + ... (n 1's) ... + 1 + 2 = 2+n A(2,n) = 2 + 2 + ... (n 2's) ... + 2 = 2*n A(3,n) = 2 * 2 * ... (n 2's) ... * 2 = 2^n A(4,n) = 2 ^ 2 ^ ... (n 2's) ... ^ 2 = 2 tetrated n (powers are evaluated right-to-left as usual and so should the rest of operators; I borrowed the terms "tetrated", "pentated", etc. from "Intuitive meaning" above) A(5,n) = 2 tetrated 2 tetrated 2 ... (n 2's) ... tetrated 2 = 2 pentated n A(6,n) = 2 pentated 2 pentated 2 ... (n 2's) ... pentated 2 = 2 hexated n etc.
In particular, A(m,2) = 4 for all m, which implies that A(m, 3) = A(m-1, 4) for m > 1.
I think that the hierarchy is more easily understood this way.
- PGimeno 18:37, 26 Sep 2004 (UTC)
The explanation of mn as "m multiplied by itself n times" is not quite true. For example, it implies that m1 means "m multiplied by itself once". I can't see an obvious way to fix this. Rewriting it as "1 multiplied by m n times" would be correct but maybe a bit obscure to the layman. Snottygobble 01:15, 20 Dec 2004 (UTC)
User 213.94.207.61 made a change months ago: here.
His other edits were subtle vandalisms - he changed dates a bit and these changes didn't get caught for very long time. ( all his edits)
Can someone check whether the change in Ackermann function above is or isn't valid?
Pavel Vozenilek 12:58, 26 Mar 2005 (UTC)
It's redundant, m is always greater than 0 there. I'll remove it. Thank you for pointing it out.
RJFJR 13:45, Mar 26, 2005 (UTC)
The Ackermann’s ‘function’ hardly counts as a function --- its array or table of values is merely a perverse pathological maze. Indeed, it blatantly demonstrates that the clearly ill-defined Ackermann’s function is an antinomy or self-contradiction paradox just like:
(1) Cantor’s diagonal argument [the sequence of diagonal terms is actually an inherent list-inclusion-and-imposition-of-order condition for the row-listing so that the anti-diagonal-terms expression is indubitably excluded from the row-list]; or
(2) Cantor’s bone-of-contention “set of all the elements of an infinite set which are not contained in their respective images for a presumed one-to-one correspondence between the elements of the given infinite set and the members of its power set [see Wikipedia article and discussion on Cantor’s Theorem]; or
(3) the ‘liar’ paradox [“This statement is false” — which is both true and false at the same time].
The following is a very simple counter-argument to the generally accepted claim that the Ackermann’s function is recursive but not primitive recursive:
(1) Clearly, the first row of the Ackermann’s function values table or array already enumerates the natural numbers — A(0,n) = n + 1 — or, recursively: A(0,0) = 1, A(0,n) = A(0,n-1) + 1.
(2) The Ackermann’s function has N x N as domain and N+ as range, where N is the set of all natural numbers and N+ is the set of all positive natural numbers. Therefore, for all natural numbers m > 0 and n ³ 0, A(m,n) = z + 1 = A(0,z) where z is some natural number (which can be readily obtained from a non-recursive definition of the Ackermann’s function — say, using the hyper operator). That is:
A(m,n) = A(0,z) = A(0,A(0,z-1)) = A(0,A(0,A(0,z-2))) = A(0,A(0,A(0,A(0,z-3)))) . . . = A(0,A(0,A(0,A(0, . . . ,A(0,0)))))
— which is the standard primitive recursive successor function on the natural numbers. In other words, every Ackermann’s function value is primitive recursively and not primitive recursively defined at the same time in the same respect — hence, its very definition indeed violates the principle of non-contradiction so it is untenable ab initio.
For example, the following is a primitive recursive definition of the Ackermann’s function:
A(m,n) = 1 if m = 0, n = 0
= A(0,n-1) + 1 if m = 0, n > 0
= A(0,hyper(2,m,n+3)-4) otherwise
where the hyper operator [see Wikipedia article on “Hyper operator”] for m > 0 is defined as:
hyper(a,1,b) = a + b
hyper(a,2,b) = a x b
hyper(a,3,b) = a ^ b = ab
hyper(a,4,b) = a ^^ b = ba [see Wikipedia article on “Tetration”]
. . .
hyper(a,m,b) = a ^m-2 b
(3) Therefore, to avoid the self-contradiction, one should define the first row Ackermann’s function values from an already known recursive but not primitive recursive function — say, A(0,0) = a > 1 and, for n > 0, A(0,n) = f(A(0,n-1)) — for example, a = 10100 and f(A(0,n-1)) = A(0,n-1)A(0,n-1) — but this undercuts Ackermann’s function’s posturing as the simplest recursive but not primitive recursive function.
It must be noted that all the Ackermann function (indeed, a many-to-one relation) values do not follow a recursive single sequence — that is, they cannot be enumerated such that the later values are obtained only from earlier values in the sequence.
Moreover, the abstract algebraic commutative ring of integers or field of rational or real numbers has only addition and multiplication (as well as their respective inverse) operations initially defined. Exponentiation (that is, iterated multiplication) is also well-defined over these number systems but tetration (see Wikipedia article) or non-standard iterated exponentiation (the exponentiation is done at the deepest level first — that is, right associative operation) is not well-defined (it violates the laws of exponents for these standard number systems — that is, its operation is not properly derived from addition and multiplication). The fast growth of the Ackermann’s function values beginning with the A(4,n) row is attributable to the fact that their definition involve non-standard iterated exponentiation which belongs to a different number system than where primitive recursive functions are defined.
BenCawaling@Yahoo.com [25 April 2005]
The text says:
I'm not convinced these add anything: the Haskell example is identical to the function pseudocode, except that all the verbose keywords get swallowed up by the ease of defining functions in Haskell, and the use of multimethods to shift the burden of argument testing from the code to the compiler. The Scheme example seems a direct copy of the pseudocode except that it swaps the names of the two arguments (and again minimizes the need for keywords).
This is not a Perl golf competition - do these examples really contribute to the article at all? Hv 15:47, 13 August 2005 (UTC)
"One surprising aspect of the Ackermann function is that the only arithmetic operations it ever uses are addition and subtraction of 1" If you define each term m+1 in terms of m and n, then the function is defined entirely in terms of addition... 137.205.8.2 10:25, 15 March 2007 (UTC)
The article says "...simple example of a recursive function that is not primitively recursive." It was the first such example known, wasn't it? (IIRC from class 20 years ago) Bubba73 (talk), 03:41, 8 December 2005 (UTC)
I read in the following web site: http://mathforum.org/epigone/math-history-list/smixsmeeblu
Subject: Ackermann vs. Sudan function: priority of discovery [was:Ackermann - or Budan or ?] Author: Bill Dubuque <wgd@martigny.ai.mit.edu> Organization: MIT Date: Fri, 12 Sep 1997 08:09:48 -0400
The following message is a courtesy copy of an article that has been posted as well.
mac@abacus.concordia.ca ( JOHN MCKAY ) writes: | | Can someone assess who originated the so-called "Ackermann fn" ? | It appears it may not be Ackermann.
Cristian Calude has written a number of papers on the history of the Ackermann and Sudan functions, e.g. see
Calude, Cristian; Marcus, Solomon; \cedla Tevy, Ionel The first example of a recursive function which is not primitive recursive. Historia Math. 6 (1979), no. 4, 380--384. MR 80i:03053 03D20 01A60
Chronologically, Sudan's function is the first example of a recursive but not primitive recursive function (Bull. Math. Soc. Roumaine Sci. 30 (1927), 11 - 30; Jbuch 53, 171). Ackermann's work was published slightly later (Math. Ann. 99 (1928), 118 - 133; Jbuch 54, 56). Both were students of Hilbert, and were working on a problem posed by Hilbert, and were acquainted with each other's work. Sudan's function extends to ordinals and majorizes Ackermann's function (except at a single point). As Smorynski says in his book Logical Number Theory
independently, to two of Hilbert's students, Wilhelm Ackermann and Gabriel Sudan. Although they gave essentially the same recursion, Sudan worked with functions of transfinite ordinals and Ackermann with functions of natural numbers, whence Hilbert cited Ackermann and Ackermann's is the name associated with the resulting functions.
The paper cited above also has speculations as to why Hilbert and Bernays did not mention Sudan's construction.
According to MR 82k:03061, Sudan's function is as follows
F (x, y) = x+y 0
F (x, 0) = x n+1
F (x, y+1) = F ( F (x, y), F (x, y)+y+1 ) n+1 n n+1 n+1
In the table, each line has an entry of the form f(2,(n+3)) - 3 in the n column. Whilst is is a "fudge" to get the right answer, would it be inappropriate to write the first line as 2^0 + (n+3) - 3 which evaluates to the present n+1? -- SGBailey 12:29, 29 January 2006 (UTC)
"In fact, α(n) is less than 5 for any conceivable input size n, since A(4, 4) has a number of digits that cannot itself be written in binary in the physical universe.
The Wikipedia article on Ackermann's function does not have ackermann's function as he originally defined it. The NIST's DADS website, also has an article on Ackermann's function. Unfortunately, it too does not show Ackermann's original definition, but it does have two links to the "versions" of Ackermann's function under the "more info" section. The link to Cowles and Bailey's (hereafter C&B) webpage seems to be the more informative of the two (Munafo's is just the math definitions without the history.) C&B's research looks like its been directly taken from a BBS article, so you'll have to ignore the headers. C&B's webpage shows that the current definitions on the NIST website, MathWorld, and Wikipedia are all R. Peter's 1935 version of Ackermann's function.
Ackermann's original function seems to be a lot more general than the other two variable functions that are presented on C&B's website. It is a three variable function which maps the common addition, multiplication, exponentiation, tetration, ... to a whole (including 0) number, which is the first parameter. It, of course, has the following two whole number input parameters that R. Peter's and the other two variable functions take in as its second and third parameters. This would make it use Polish notation, if the parameters were written and used from the left to right. Also, Herbert's version seems to be the most refined, and I would suggest using it to introduce the reader to Ackermann's function.
Several links in the History section take the form '#vonHeijenoort|something', taking the user to the list of external references. Is it better to link to the wikipedia article if we have one? I changed one link (Hilbert's program) before realising there were several, so thought I'd ask! --- Richard CHS Talk 12:48, 26 June 2006 (UTC)
One can extend the Ackermann function to the transfinite (for ordinals which have a distinguished fundamental sequence) as follows:
If λ is a limit ordinal with the fundamental sequence which takes k to λk, we let:
See Large countable ordinals#Fundamental sequences for the Veblen hierarchy. JRSpriggs 09:22, 20 August 2006 (UTC)
People who do not have something useful to say about this article seem obsessed to insert some comparison between large numbers and the "number of atoms in the universe" with perhaps some silly function applied. Please stop. It might be entertaining, but it is not appropriate encyclopedic information. -- Farever 23:08, 2 February 2007 (UTC)
:-(
I note that Susan Stepney's table chooses to always list A(5,1) as A(4,65533), thus the term appears four times in her table. Our current table instead uses A(5,1) three times, which I think is distracting because it breaks the pattern in that is otherwise clear in row 6. Another possiblity is using A(5, A(6, 0)) as the result for A(6, 1). Do you guys have a preference?-- 199.33.32.40 01:35, 3 February 2007 (UTC)
This is feeling like it might be a GA once again. I will poll some of the Math WikiProject guys and get some feedback. Then maybe some PR and on to GAN!-- 70.231.149.0 02:15, 4 February 2007 (UTC)
I hope it's correct now. It was false before.
I added two external links on the inverse Ackermann function (one to a page of mine, one to a PDF presentation by R. Seidel). The inverse Ackermann function should get its own wikipedia page. Gabn1 09:32, 22 February 2007 (UTC)
"(this presentation is due to Rózsa Péter):"
Is this really important? No offense to anyone, but I think Rózsa Péter should be credited only as a scientist, not a Wikipedia editor (maybe on her own page, but this one seems a bit excessive...though not quite vanity, but perhaps self-promotion...) —The preceding unsigned comment was added by 128.32.42.26 ( talk) 23:10, 27 February 2007 (UTC).
The explanation of why this function always terminates is confusing in my opinion. At least, it does not succinctly convince the reader that the function terminates. It states:
"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-ordering 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."
I don't think that the "more technical" explanation needs to be there as it interrupts the explanation. Furthermore, the "m decreases, so m eventually reaches zero" part is followed by the part stating that if m decreases there is no upper bound on how much n will increase, so it wouldn't follow that m eventually reaches zero without further inspection. I can't offer a better explanation, but I think it could be done. —The preceding unsigned comment was added by Sam Brightman ( talk • contribs) 15:58, 2 April 2007 (UTC).
I disagree with the down-grading of the Ackermann function from "mid" importance to "low" importance. It is quite important in understanding the distinction between primitive recursive functions and total recursive functions generally. See Primitive recursive function#Relationship to recursive functions, especially the last sentence which says "... a function is primitive recursive if and only if there is a natural number m such that the function can be computed by a Turing machine that always halts within A(m,n) or fewer steps, where n is the sum of the arguments of the primitive recursive function.". JRSpriggs 10:13, 10 June 2007 (UTC)
We need some citations and more information on the relationship between Ackermann's function and primitive recursive functions. David.Monniaux 03:55, 17 June 2007 (UTC)
I fixed the entry for the fourth Ackermann number some time ago, and it got reverted by someone (probably carelessly). I'm placing the incorrect text here:
An attempt to express the fourth Ackermann number, 44, using iterated exponentiation is not practical but it can be expressed using tetration in three nested layers as shown below. Explanation: in the middle layer, there is a tower of tetration whose full length is (already a large number) and the final result is the top layer of tetrated 4's whose length equals the calculation of the middle layer.
The following contains the correct expressions: notice that it actually uses tetration as claimed:
An attempt to express the fourth Ackermann number, 44, using iterated exponentiation as above would become extremely complicated. However, it can be expressed using tetration in three nested layers as shown below. Explanation: in the middle layer, there is a tower of tetration whose full length is and the final result is the top layer of tetrated 4's whose full length equals the calculation of the middle layer. Note that by way of size comparison, the simple expression already exceeds a googolplex, so the fourth Ackermann number is quite large.
Sorry I can't remember my password to log in and sign this. I'll sign it later. Ok: signed by my logged-in ID now: Kaimiddleton 21:37, 20 July 2007 (UTC)
Hello. I just removed a C++ metaprogramming example. It was designed in vain - the templates are highly ambiguous. Here is a transcript of the contents:
template<int x, int y> struct ackermann { enum { v = ackermann<x-1, ackermann<x, y-1>::v>::v } ; } ; template< int y> struct ackermann<0, y> { enum { v = y+1 } ; } ; template<int x > struct ackermann<x, 0> { enum { v = ackermann<x-1, 1>::v } ; } ; template< > struct ackermann<0, 0> { enum { v = 1 } ; } ;
The second and third are equivalent. In a compiler that ignores the name, you'd wind up with a conflict. It doesn't work with GCC (at least in my test) - PGSONIC 00:59, 17 August 2007 (UTC)
I don't see a reason to show the function implemented in a dozen computer languages. It doesn't do anything to add to the understanding of the function and is only of cursory relevance to the article. In particular "Non-Recursive Ackermann in C++" seems more like a geek-badge than encyclopedic content.
There is no point in showing a recursive function can be implemented with a stack as that is how recursion is -- Ott2 18:32, 21 September 2007 (UTC)implemented in computer languages anyway.
Interestingly although "The first implementation in a programming language was in Fortran in 1964, see H. Gordon -- Ott2 18:32, 21 September 2007 (UTC)Rice[13], Recursion and iteration, Commun. ACM, 8(2), 1965, pp. 114--115.)", no Fortran implementation is even given (let alone the first). If any computer implementation of the function was relevant to the article it would be that one and it isn't even provided!
My recommendation is to remove the section or to have only the C definition. 69.121.109.152 19:58, 24 August 2007 (UTC)
Hello - I just came by this article and noticed a statement that I don't believe is correct (underlined):
To my knowledge, iteratively repeated power towers as used in the definition of Graham's number are expressible with Ackermann functions and 5 as the first argument: First arguments 3 are in the order of powers, 4 is in the order of power towers, and 5 in the order of repeated power towers. So I would expect Graham's number to be something like A(5, n) with n something larger than 64 (but not much larger; Ackermann function is in the order of powers of 2, whereas Graham's number is defined through powers of 3). Therefore, Grahams number could not be considered an "even larger number" as stated in the article, but upper bounds can be expressed through the Ackermann function with reasonably small arguments. Comments? Thanks, Jens Koeplinger 13:28, 27 August 2007 (UTC)
It was already said that there are too many implementations. Thus I deleted those implementations that I considered obscure. So far so good. The Matlab implementation was promptly readded. But: Matlab is just some CAS, right? I don't see its outstanding importance, least that the Ackermann function needs to be explained in terms of this "language". (I would also be happy to see even less implementations but couldn't decide on a language.) -- 53.122.197.194 ( talk) 13:57, 26 November 2007 (UTC)
Correct me if I'm wrong, but couldn't that program be int ackermann(int m, int n) {
if (m == 0) return n+1; if (n == 0) return ackermann(m-1, 1); return ackermann(m-1, ackermann(m, n-1));
} ?
Considering that it's 'written' in C and that after a return statement, it wouldn't evaluate the rest? At the very least, I would remove the "m>0" parts, because presumably if m is not zero, it is greater than zero. Sorry, can't log in account right now. Gremlinman. —Preceding unsigned comment added by 24.218.46.235 ( talk) 00:05, 5 December 2007 (UTC)
There is a citation needed note on the claim that Donald Michie invented memoization. There are citations on both his page Donald Michie and the Memoization pages. I'm not sure whether to copy that reference here, or if it would be better to remove the claim here since there isn't anything Ackermann-specific about it, and if someone wants to go look at the memoization page they'll see the claim right at the top (and the citation).
Or could the call for citation be about the claim that compilers can do memoization automatically? Certainly they can (Haskell for example [4], among plenty of others). But again, it seems to me that such details belong on the Memoization page.
-- JamesPaulWhite ( talk) 06:31, 13 April 2008 (UTC)
The " Hyper() function" appears to be someone's private terminology for one of the more common variants of the Ackermann function, and the family of so-called "hyper operators" is just the related hierarchy of fast-growing functions. Here's a relevant quote from that article, which should explain why it ought to be merged with Ackermann function:
There is a lot of good information in the Hyper operator article, but it seems to be in the wrong place, using someone's private terminology. (As far as I know, there is no published source for that terminology in this context.) I happen to like variants of the operator notation used there, i.e, a(k)n, but I expect that just about anyone who has worked very much with this hierarchy of functions has probably invented something like it for themselves; but, again, I haven't seen it used in publications (presumably because it would seem too trivial to mention).
An important point is that each function (operator) in the Ackermann hierarchy, i.e. each function obtained from the Ackermann function by fixing the argument that determines the "operator level" (i.e. 0 <-> successor, 1 <-> addition, 2 <-> multiplication, etc.), *is* primitive recursive. It's the function of all three arguments (or two in the case of the two-argument version in the present article) that's recursive but not primitive recursive.
--
r.e.s. (
talk) 19:24, 26 September 2008 (UTC)
Ackermann function is not "just" an example of a recursive function that is not primitive recursive. It plays a fundamental role in computability theory because it is the proper complexity measure of several algorithms, and the complexity measure of several decidable problems. For example, McAloon shows that controlled sequences of incomparable n-dimensional vectors of natural numbers have length bounded by a version of A(n,x) (see McAloon, TCS 1984). This provides an Ackermann upper bound for many algorithms that rely on Dickson's lemma for their termination. And there exist problems with this Ackermann upper bound for which a matching lower bound can be established. An example being the equivalence of bounded Petri nets (see Mayr and Meyer, JACM 1981). PhS ( talk) 20:25, 26 September 2008 (UTC)
I moved the definition back to the lower section. It might (I'm not quite sold) be worth adding it to the lede. But it would need to go lower in the lede, not at the top. The goal of the first part of the article is to establish context and give a general description that essentially anybody can understand. So what is presently the first paragraph really should be the first paragraph. — Carl ( CBM · talk) 01:17, 29 October 2008 (UTC)
Having read the article linked to as well as all blog comments falling under that article made by xkcd, I see nowhere where he claims his "xkcd number" is the largest ever concisely defined. The article says that Adam Clarkson considered the Clarkkkkson number to be the largest ever concisely defined. Then he says his intuition is that the xkcd number is probably larger but he is not sure, and asks if any of his readers can demonstrate which is larger. Therefore I am amending the sentence. Incantar ( talk) 07:14, 11 March 2009 (UTC)
I cannot find the definition by Rózsa Péter and Raphael Robinson that is referenced in the History section. 150.252.46.189 ( talk) 22:51, 26 March 2009 (UTC)
The article states that 'one should not confuse the primitive recursive functions with those definable by primitive recursion'. As far as I understand things, the primitive recursive functions are exactly those definable by primitive recursion (i.e. without general recursion), so, unless people have valid objections, I will delete the sentence. -- Acipsen ( talk) 18:18, 28 December 2009 (UTC)
Why is this section in Ackermann function? No mention is made of the function at all. It would be better moved in toto to Knuth's up arrow page. OR to convert 1^1, 2^^2, 3^^^3 etc into Ackermann function calls some how. -- SGBailey ( talk) 21:17, 9 July 2010 (UTC)
"Recursive" is the same as "total computable", but not the same as "computable". It is not surprising that the set of primitive recursive functions is not the same as the set of computable functions, since all p.r. functions are total and there exists at least one computable function which is not total. The interesting thing about the Ackermann function is that it shows that not every total computable function is primitive recursive, so this should be explicitely mentioned. – Adrianwn ( talk) 05:16, 13 July 2010 (UTC)
[unindent] I have looked up "Recursively enumerable sets and degrees: a study of computable functions and computably generated sets" by R.I. Soare (Springer, 1987) link, in which he states:
We shall accept Church's thesis and from now on shall use the terms "partial recursive (p.r.),", "Turing computable," and "computable" interchangeably.
On the other hand, he equates the total functions with recursive resp. computable:
An algorithmic partial function which is defined on all arguments (i.e., which is total), is called "recursive" or "computable".
Am I missing something?
Please note that in the end I don't care what term is used in the article, however,
Adrianwn ( talk) 14:38, 13 July 2010 (UTC)
Since there are no objections to the terminology as used in the article now, should we use it in other articles as well? To summarize:
In my opinion, we should. – Adrianwn ( talk) 07:15, 18 July 2010 (UTC)
I am going to delete the section on extending the Ackerman functions to the complex plane. It appears to be based on a misunderstanding. As this link shows http://mathoverflow.net/questions/2944/, one can find many different entire functions that agree with say A(m,n) for a fixed m and all n. The present section seems to doubt that there is any extension at all.
Perhaps something different was meant. If so someone else can rewrite the section and restore it. But as it is, I find actively misleading. MathHisSci ( talk) 23:19, 16 December 2010 (UTC)
xkcd is awesome! — Preceding unsigned comment added by AdamDavid ( talk • contribs) 21:25, 17 April 2011 (UTC) Umm... You probably shouldn't do something like this — Preceding unsigned comment added by EZ132 ( talk • contribs) 16:45, 18 February 2020 (UTC)
The forth equation in History is WRONG. — Preceding unsigned comment added by 72.129.87.43 ( talk) 00:36, 28 July 2011 (UTC)
I've just deleted 7 programming examples. I see no reason we need them. If your programming language supports recursion and you've passed Computer Science 101, then you know how to turn this function into code. It exposes no interesting issues in computer science. The output of the function isn't even interesting in any sense; it's just a simple example of a computable function that's not primitive recursive. The only way code for this function could be interesting if it were showing how to implement a recursive function in a language that doesn't natively support that, and I don't think this is the right article for that.
If we do need a programming example, can we at least have one pseudo-code one instead of seven examples?-- Prosfilaes ( talk) 18:46, 7 May 2012 (UTC)
There appears to be some confusion about the definition of the Ackermann function using Succ and Iter. Using the iteration operator defined by
I think the right definition for the Ackermann function is the following:
and not
(note the parens).
The second definition cannot be right anyway as it would imply
looping indefinitely. Or am I confused? Anyway, I would like to see a source for these definitions. — Tobias Bergemann ( talk) 19:53, 14 July 2012 (UTC)
ack 0 n = n+1
ack (m+1) 0 = ack m 1
ack (m+1) (n+1) = ack m (ack (m+1) n)
ack 0 = succ
ack (m+1) = h where
h 0 = ack m 1
h (n+1) = ack m (ack (m+1) n)
m
-mentionings inside the body of h:ack 0 = succ
ack (m+1) = h (ack m) where
h f 0 = f 1
h f (n+1) = f (ack (m+1) n)
m
by using ack(m+1) = h (ack m)
and h (ack m) == h f
when seen from inside the local h
:ack 0 = succ
ack (m+1) = h (ack m) where
h f 0 = f 1
h f (n+1) = f (h f n)
ack n m == m+1
for all nonnegative n m. A really bad typo! ;) --
Daniel5Ko (
talk) 21:54, 16 July 2012 (UTC)In the current page: "Logician Harvey Friedman defines a version of the Ackermann function as follows:
He also defines a single-argument version A(n) = A(n, n).[6]"
I'm recommending, whether or not Friedman originally used 'A' when introducing his function, that Wikipedia change the letter for his function, to 'F' maybe. The reason is in the next para from the article,(see under next line): it's not going to be clear to a reader in a hurry which 'A' is talked about. Maybe it doesn't matter mathematically which 'A' is talked about, if the exact same argument can show both aren't prim recursive, but it's still confusing.
"A single-argument version A(k) = A(k, k) that increases both m and n at the same time 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). It can be seen that A(n) is roughly comparable to fω(n) in the fast-growing hierarchy. This extreme growth can be exploited to show that f, which is obviously computable on a machine.... " 76.218.104.120 ( talk) 08:54, 8 January 2014 (UTC)
Editor CBM has reverted automated edits made to this article that remove the article from
Category:Pages containing cite templates with deprecated parameters. I have added {{
bots|deny=Monkbot}}
to the top of the page which I think will prevent the bot from revisiting.
— Trappist the monk ( talk) 19:46, 12 January 2014 (UTC)
I removed these two equations involving the m [ ] notation, since it was unclear what it means.
In any case I think these equations are not essential, since a full definition of the 3 argument Ackermann function is given in the following Definition and Properties section. Perhaps the m notation has a standard meaning in the literature of hypercomputation, of which I am unaware, but if so I think a further explanation is needed in the present context. CharlesHBennett ( talk) 19:34, 6 July 2015 (UTC)
Yesterday, the section on Ackermann numbers was removed by user Cagrhsi ( talk · contribs), with the edit comment "The Ackermann numbers were determined to be a non-notable addition to this page during the Chihiro number controversy." I don't know what "Chihiro number controversy" refers to, and I can't really comment on the notability of the Ackermann numbers. Anyway, this edit left dangling redirects Ackermann number and Ackermann numbers. Should these be deleted now? – Tobias Bergemann ( talk) 08:06, 16 October 2015 (UTC)
Does this function have any real-world applications, or is it only interesting in theoretical math? -- Beland ( talk) 22:45, 21 October 2015 (UTC)
The comment(s) below were originally left at Talk:Ackermann function/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.
A longer lead, and more balance would improve this. The "Implementations" and "Inverse" sections in particular would benefit from some review. Geometry guy 15:22, 9 June 2007 (UTC) |
Last edited at 15:22, 9 June 2007 (UTC). Substituted at 19:44, 1 May 2016 (UTC)
Ackermann's original function is presented in the article under History, but the Ackermann-Péter function appears earlier than it, in the introduction. Would it be appropriate to move the "true" Ackermann function to the introduction and present it before leading into the simplified Ackermann-Péter function? The latter is of course better-known, but I think it may be more correct to present Ackermann's original function first. 00dani ( talk) 01:18, 30 August 2016 (UTC)
Hello fellow Wikipedians,
I have just modified 2 external links on Ackermann function. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:
{{
dead link}}
tag to
http://www.math.osu.edu/~friedman.8/pdf/AckAlgGeom102100.pdfWhen you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at {{
Sourcecheck}}
).
This message was posted before February 2018.
After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than
regular verification using the archive tool instructions below. Editors
have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the
RfC before doing mass systematic removals. This message is updated dynamically through the template {{
source check}}
(last update: 18 January 2022).
Cheers.— InternetArchiveBot ( Report bug) 12:26, 3 October 2016 (UTC)
The following "proof" of the fact that the Ackermann function is not primitive recursive was added to the article. I have removed it since it is extremely unclear and at the very least contains numerous typos. The definition of the class is not clear since x is not defined (presumably it is the maximum of the xi?). AxelBoldt ( talk) 03:20, 26 April 2017 (UTC)
Remember the properties . Let .
Now we will show that initial functions are in , and that it is closed under functions composition and primitive recursion (which are equivalent to PR). Initial functions: (constant function), (successor) and (projections).
Function composition: .
Primitive Recursion: if (hp1) and (hp2) , if , by induction on n (inductive hypotesis), (base of induction), , QED.
Therefore, PR, but for , then A and APR, QED.
Rules:
B(2, 0) = B(1, 1) = B(0, B(1, 0)) = B(0, B(0, 1)) = B(0, A(1, 1)) = B(0, A(0, A(1, 0))) = B(0, A(0, A(0, 1))) = B(0, A(0, 2)) = B(0, 3) = A(3, 1) = A(2, A(3, 0)) = A(2, A(2, 1)) ... = A(2, A(1, 3)) ... = A(2, A(0, 4)) = A(2, 5) ... = 13 B(3, 0) = B(2, 1) = B(1, B(2, 0)) ... = B(1, 13) = A(B(1, 12), 1) = A(A(B(1, 11), 1), 1) ... = A(A(A(A(A(A(A(A(A(A(A(A(B(1, 1), 1), 1), 1), 1), 1), 1), 1), 1), 1), 1), 1), 1) ... = A(A(A(A(A(A(A(A(A(A(A(A(13, 1), 1), 1), 1), 1), 1), 1), 1), 1), 1), 1), 1) = A(A(A(A(A(A(A(A(A(A(A(A(12, A(13, 0)), 1), 1), 1), 1), 1), 1), 1), 1), 1), 1), 1) = A(A(A(A(A(A(A(A(A(A(A(A(12, A(12, 1)), 1), 1), 1), 1), 1), 1), 1), 1), 1), 1), 1) B(4, 0) = B(3, 1) = B(2, B(3, 0)) = B(2, <too large>)
That's pretty salad, but not super salad. -- EZ132 ( Talk | Contributions | Uploads | log) —Preceding undated comment added 17:00, 18 February 2020 (UTC)
Gabriel Nivasch [1] gives another form of the Inverse Ackermann function. First he defines the inverse ackermann hierarchy:
References
This note links to an author's personal page (where he also sells Jesus books, not that there's anything wrong with that) containing code that very well may be, but isn't obviously, an Ack implementation. Just to be clear: of course you can calculate anything with for-loops if you simulate a program stack and recursion using dynamic memory. An example isn't required, and this one is not particularly illustrative because readers who aren't aware you can do this are going to have to accept that it works on faith. The bigger problem, however, is that this statement and link appears at the end of a proof that has nothing to do with a claim about for-loops. I think the claim and link should be removed from the proof section as it is unrelated. It may be worthwhile to add the link to a section discussing the for-loop thing, but only if more context is provided—but I am not convinced this is a good idea either because the example is not very illuminating. TricksterWolf ( talk) 21:58, 22 June 2021 (UTC)
Ackermann function is a former featured article. Please see the links under Article milestones below for its original nomination page (for older articles, check the nomination archive) and why it was removed. | ||||||||||||||||||||||
This article appeared on Wikipedia's Main Page as Today's featured article on September 24, 2004. | ||||||||||||||||||||||
|
This article is rated B-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||||||||||||||||||||||
|
This article has a mistake somewhere in the definitions. I wrote a C program based on what is here, and it simply goes in an endless loop for m = 4 (A(4,n)). It does not terminate, as the definition states. -- Gesslein 16:58, 4 October 2006 (UTC)
Here's a few values of the Ackermann function. Not so surprisingly, my program didn't get any further.
A(0,0) = 1 A(0,1) = 2 A(0,2) = 3 A(0,3) = 4 A(0,4) = 5 A(0,5) = 6 A(0,6) = 7 A(0,7) = 8 A(0,8) = 9 A(0,9) = 10
A(1,0) = 2 A(1,1) = 3 A(1,2) = 4 A(1,3) = 5 A(1,4) = 6 A(1,5) = 7 A(1,6) = 8 A(1,7) = 9 A(1,8) = 10 A(1,9) = 11
A(2,0) = 3 A(2,1) = 5 A(2,2) = 7 A(2,3) = 9 A(2,4) = 11 A(2,5) = 13 A(2,6) = 15 A(2,7) = 17 A(2,8) = 19 A(2,9) = 21
A(3,0) = 5 A(3,1) = 13 A(3,2) = 29 A(3,3) = 61 A(3,4) = 125 A(3,5) = 253 A(3,6) = 509 A(3,7) = 1021 A(3,8) = 2045 A(3,9) = 4093
A(4,0) = 13 A(4,1) = 65533 (Didn't use program for this one, but should be right.)
Κσυπ Cyp 17:07, 18 Oct 2003 (UTC)
Hi, NIST gives a different version [1] of this function, which seems incompatible with the veresion given here. Are they just plain wrong? -- Pakaran 03:34, 25 Nov 2003 (UTC)
Please see section 14 below.
One of the table entries looks messed up under IE. Can someone with more knowledge of the pampering of IE fix this? Thanks. Pakaran . 20:55, 27 Feb 2004 (UTC)
It may be noted that A(4, 2), which appears as a decimal expansion in several web pages, cannot possibly be computed by recursive application of the Ackermann function.
How, then? --
Fibonacci 21:06, 31 Jul 2004 (UTC)
Did anybody notice that except for the absence of a few ':' characters, that pseudo code is valid Python. -- 83.146.34.206 06:23, 24 Sep 2004 (UTC)
The inverse of the function f is less than 4 for any conceivable input size, so for practical algorithm analysis, it can be regarded as a constant.
Just a note: in the introduction it states, "In mathematics and computer science, the Ackermann function (also known as Ackermann-Peter function) is an important example in the theory of computation.", but doesn't say what the Ackermann function is an important example of. - Seth Mahoney 22:06, Sep 24, 2004 (UTC)
I think it is supposed to be an example of "A function of two parameters whose value grows very fast" according to [2]. Kirbytime 02:17, 24 March 2006 (UTC)
If I understood the Aaronson article (under "References") correctly, the Ackermann function extends the line of operations "addition, multiplication, exponential" to "tetration, pentation" and so forth. So you have:
A(1) = 1 + 1 A(2) = 2 * 2 A(3) = 3 ^ 3 = (3 * 3) * 3 A(4) = 4 tetrated 4 = ((4 ^ 4) ^ 4) ^ 4 A(5) = 5 pentated 5 = (((5 tetrated 5) tetrated 5) tetrated 5) tetrated 5 ...
The definition of the function in the Wikipedia article seems to be different, but the "Explicit description" section says something about "[...] iterated exponentiation, iteration of this operation and so on", so it sounds like the essence is the same in the two definitions.
I just stumbled across this article because it was featured, so I'm not a mathematician and thus don't really know what I'm talking about here! However, if the Ackermann function really has an as simple intuitive meaning as this, maybe there should be a table showing this, like the one I just wrote.
---the original definition by Ackermann was a 3 termed function A(m,n,p) where p=1=>m+n, p=2=>m*n, etc. This 1 term function is closely related, but not the same, though it is what is usually referred to as the Ackermann function
At the end of the section about Inverse we can read:
Here's an example of a modified Ackermann function which simplifies the explicit formulas for each level in the hierarchy. This function is defined for positive integers m,n both starting at 1 instead of 0:
This function meets:
A(1,n) = 1 + 1 + ... (n 1's) ... + 1 + 2 = 2+n A(2,n) = 2 + 2 + ... (n 2's) ... + 2 = 2*n A(3,n) = 2 * 2 * ... (n 2's) ... * 2 = 2^n A(4,n) = 2 ^ 2 ^ ... (n 2's) ... ^ 2 = 2 tetrated n (powers are evaluated right-to-left as usual and so should the rest of operators; I borrowed the terms "tetrated", "pentated", etc. from "Intuitive meaning" above) A(5,n) = 2 tetrated 2 tetrated 2 ... (n 2's) ... tetrated 2 = 2 pentated n A(6,n) = 2 pentated 2 pentated 2 ... (n 2's) ... pentated 2 = 2 hexated n etc.
In particular, A(m,2) = 4 for all m, which implies that A(m, 3) = A(m-1, 4) for m > 1.
I think that the hierarchy is more easily understood this way.
- PGimeno 18:37, 26 Sep 2004 (UTC)
The explanation of mn as "m multiplied by itself n times" is not quite true. For example, it implies that m1 means "m multiplied by itself once". I can't see an obvious way to fix this. Rewriting it as "1 multiplied by m n times" would be correct but maybe a bit obscure to the layman. Snottygobble 01:15, 20 Dec 2004 (UTC)
User 213.94.207.61 made a change months ago: here.
His other edits were subtle vandalisms - he changed dates a bit and these changes didn't get caught for very long time. ( all his edits)
Can someone check whether the change in Ackermann function above is or isn't valid?
Pavel Vozenilek 12:58, 26 Mar 2005 (UTC)
It's redundant, m is always greater than 0 there. I'll remove it. Thank you for pointing it out.
RJFJR 13:45, Mar 26, 2005 (UTC)
The Ackermann’s ‘function’ hardly counts as a function --- its array or table of values is merely a perverse pathological maze. Indeed, it blatantly demonstrates that the clearly ill-defined Ackermann’s function is an antinomy or self-contradiction paradox just like:
(1) Cantor’s diagonal argument [the sequence of diagonal terms is actually an inherent list-inclusion-and-imposition-of-order condition for the row-listing so that the anti-diagonal-terms expression is indubitably excluded from the row-list]; or
(2) Cantor’s bone-of-contention “set of all the elements of an infinite set which are not contained in their respective images for a presumed one-to-one correspondence between the elements of the given infinite set and the members of its power set [see Wikipedia article and discussion on Cantor’s Theorem]; or
(3) the ‘liar’ paradox [“This statement is false” — which is both true and false at the same time].
The following is a very simple counter-argument to the generally accepted claim that the Ackermann’s function is recursive but not primitive recursive:
(1) Clearly, the first row of the Ackermann’s function values table or array already enumerates the natural numbers — A(0,n) = n + 1 — or, recursively: A(0,0) = 1, A(0,n) = A(0,n-1) + 1.
(2) The Ackermann’s function has N x N as domain and N+ as range, where N is the set of all natural numbers and N+ is the set of all positive natural numbers. Therefore, for all natural numbers m > 0 and n ³ 0, A(m,n) = z + 1 = A(0,z) where z is some natural number (which can be readily obtained from a non-recursive definition of the Ackermann’s function — say, using the hyper operator). That is:
A(m,n) = A(0,z) = A(0,A(0,z-1)) = A(0,A(0,A(0,z-2))) = A(0,A(0,A(0,A(0,z-3)))) . . . = A(0,A(0,A(0,A(0, . . . ,A(0,0)))))
— which is the standard primitive recursive successor function on the natural numbers. In other words, every Ackermann’s function value is primitive recursively and not primitive recursively defined at the same time in the same respect — hence, its very definition indeed violates the principle of non-contradiction so it is untenable ab initio.
For example, the following is a primitive recursive definition of the Ackermann’s function:
A(m,n) = 1 if m = 0, n = 0
= A(0,n-1) + 1 if m = 0, n > 0
= A(0,hyper(2,m,n+3)-4) otherwise
where the hyper operator [see Wikipedia article on “Hyper operator”] for m > 0 is defined as:
hyper(a,1,b) = a + b
hyper(a,2,b) = a x b
hyper(a,3,b) = a ^ b = ab
hyper(a,4,b) = a ^^ b = ba [see Wikipedia article on “Tetration”]
. . .
hyper(a,m,b) = a ^m-2 b
(3) Therefore, to avoid the self-contradiction, one should define the first row Ackermann’s function values from an already known recursive but not primitive recursive function — say, A(0,0) = a > 1 and, for n > 0, A(0,n) = f(A(0,n-1)) — for example, a = 10100 and f(A(0,n-1)) = A(0,n-1)A(0,n-1) — but this undercuts Ackermann’s function’s posturing as the simplest recursive but not primitive recursive function.
It must be noted that all the Ackermann function (indeed, a many-to-one relation) values do not follow a recursive single sequence — that is, they cannot be enumerated such that the later values are obtained only from earlier values in the sequence.
Moreover, the abstract algebraic commutative ring of integers or field of rational or real numbers has only addition and multiplication (as well as their respective inverse) operations initially defined. Exponentiation (that is, iterated multiplication) is also well-defined over these number systems but tetration (see Wikipedia article) or non-standard iterated exponentiation (the exponentiation is done at the deepest level first — that is, right associative operation) is not well-defined (it violates the laws of exponents for these standard number systems — that is, its operation is not properly derived from addition and multiplication). The fast growth of the Ackermann’s function values beginning with the A(4,n) row is attributable to the fact that their definition involve non-standard iterated exponentiation which belongs to a different number system than where primitive recursive functions are defined.
BenCawaling@Yahoo.com [25 April 2005]
The text says:
I'm not convinced these add anything: the Haskell example is identical to the function pseudocode, except that all the verbose keywords get swallowed up by the ease of defining functions in Haskell, and the use of multimethods to shift the burden of argument testing from the code to the compiler. The Scheme example seems a direct copy of the pseudocode except that it swaps the names of the two arguments (and again minimizes the need for keywords).
This is not a Perl golf competition - do these examples really contribute to the article at all? Hv 15:47, 13 August 2005 (UTC)
"One surprising aspect of the Ackermann function is that the only arithmetic operations it ever uses are addition and subtraction of 1" If you define each term m+1 in terms of m and n, then the function is defined entirely in terms of addition... 137.205.8.2 10:25, 15 March 2007 (UTC)
The article says "...simple example of a recursive function that is not primitively recursive." It was the first such example known, wasn't it? (IIRC from class 20 years ago) Bubba73 (talk), 03:41, 8 December 2005 (UTC)
I read in the following web site: http://mathforum.org/epigone/math-history-list/smixsmeeblu
Subject: Ackermann vs. Sudan function: priority of discovery [was:Ackermann - or Budan or ?] Author: Bill Dubuque <wgd@martigny.ai.mit.edu> Organization: MIT Date: Fri, 12 Sep 1997 08:09:48 -0400
The following message is a courtesy copy of an article that has been posted as well.
mac@abacus.concordia.ca ( JOHN MCKAY ) writes: | | Can someone assess who originated the so-called "Ackermann fn" ? | It appears it may not be Ackermann.
Cristian Calude has written a number of papers on the history of the Ackermann and Sudan functions, e.g. see
Calude, Cristian; Marcus, Solomon; \cedla Tevy, Ionel The first example of a recursive function which is not primitive recursive. Historia Math. 6 (1979), no. 4, 380--384. MR 80i:03053 03D20 01A60
Chronologically, Sudan's function is the first example of a recursive but not primitive recursive function (Bull. Math. Soc. Roumaine Sci. 30 (1927), 11 - 30; Jbuch 53, 171). Ackermann's work was published slightly later (Math. Ann. 99 (1928), 118 - 133; Jbuch 54, 56). Both were students of Hilbert, and were working on a problem posed by Hilbert, and were acquainted with each other's work. Sudan's function extends to ordinals and majorizes Ackermann's function (except at a single point). As Smorynski says in his book Logical Number Theory
independently, to two of Hilbert's students, Wilhelm Ackermann and Gabriel Sudan. Although they gave essentially the same recursion, Sudan worked with functions of transfinite ordinals and Ackermann with functions of natural numbers, whence Hilbert cited Ackermann and Ackermann's is the name associated with the resulting functions.
The paper cited above also has speculations as to why Hilbert and Bernays did not mention Sudan's construction.
According to MR 82k:03061, Sudan's function is as follows
F (x, y) = x+y 0
F (x, 0) = x n+1
F (x, y+1) = F ( F (x, y), F (x, y)+y+1 ) n+1 n n+1 n+1
In the table, each line has an entry of the form f(2,(n+3)) - 3 in the n column. Whilst is is a "fudge" to get the right answer, would it be inappropriate to write the first line as 2^0 + (n+3) - 3 which evaluates to the present n+1? -- SGBailey 12:29, 29 January 2006 (UTC)
"In fact, α(n) is less than 5 for any conceivable input size n, since A(4, 4) has a number of digits that cannot itself be written in binary in the physical universe.
The Wikipedia article on Ackermann's function does not have ackermann's function as he originally defined it. The NIST's DADS website, also has an article on Ackermann's function. Unfortunately, it too does not show Ackermann's original definition, but it does have two links to the "versions" of Ackermann's function under the "more info" section. The link to Cowles and Bailey's (hereafter C&B) webpage seems to be the more informative of the two (Munafo's is just the math definitions without the history.) C&B's research looks like its been directly taken from a BBS article, so you'll have to ignore the headers. C&B's webpage shows that the current definitions on the NIST website, MathWorld, and Wikipedia are all R. Peter's 1935 version of Ackermann's function.
Ackermann's original function seems to be a lot more general than the other two variable functions that are presented on C&B's website. It is a three variable function which maps the common addition, multiplication, exponentiation, tetration, ... to a whole (including 0) number, which is the first parameter. It, of course, has the following two whole number input parameters that R. Peter's and the other two variable functions take in as its second and third parameters. This would make it use Polish notation, if the parameters were written and used from the left to right. Also, Herbert's version seems to be the most refined, and I would suggest using it to introduce the reader to Ackermann's function.
Several links in the History section take the form '#vonHeijenoort|something', taking the user to the list of external references. Is it better to link to the wikipedia article if we have one? I changed one link (Hilbert's program) before realising there were several, so thought I'd ask! --- Richard CHS Talk 12:48, 26 June 2006 (UTC)
One can extend the Ackermann function to the transfinite (for ordinals which have a distinguished fundamental sequence) as follows:
If λ is a limit ordinal with the fundamental sequence which takes k to λk, we let:
See Large countable ordinals#Fundamental sequences for the Veblen hierarchy. JRSpriggs 09:22, 20 August 2006 (UTC)
People who do not have something useful to say about this article seem obsessed to insert some comparison between large numbers and the "number of atoms in the universe" with perhaps some silly function applied. Please stop. It might be entertaining, but it is not appropriate encyclopedic information. -- Farever 23:08, 2 February 2007 (UTC)
:-(
I note that Susan Stepney's table chooses to always list A(5,1) as A(4,65533), thus the term appears four times in her table. Our current table instead uses A(5,1) three times, which I think is distracting because it breaks the pattern in that is otherwise clear in row 6. Another possiblity is using A(5, A(6, 0)) as the result for A(6, 1). Do you guys have a preference?-- 199.33.32.40 01:35, 3 February 2007 (UTC)
This is feeling like it might be a GA once again. I will poll some of the Math WikiProject guys and get some feedback. Then maybe some PR and on to GAN!-- 70.231.149.0 02:15, 4 February 2007 (UTC)
I hope it's correct now. It was false before.
I added two external links on the inverse Ackermann function (one to a page of mine, one to a PDF presentation by R. Seidel). The inverse Ackermann function should get its own wikipedia page. Gabn1 09:32, 22 February 2007 (UTC)
"(this presentation is due to Rózsa Péter):"
Is this really important? No offense to anyone, but I think Rózsa Péter should be credited only as a scientist, not a Wikipedia editor (maybe on her own page, but this one seems a bit excessive...though not quite vanity, but perhaps self-promotion...) —The preceding unsigned comment was added by 128.32.42.26 ( talk) 23:10, 27 February 2007 (UTC).
The explanation of why this function always terminates is confusing in my opinion. At least, it does not succinctly convince the reader that the function terminates. It states:
"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-ordering 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."
I don't think that the "more technical" explanation needs to be there as it interrupts the explanation. Furthermore, the "m decreases, so m eventually reaches zero" part is followed by the part stating that if m decreases there is no upper bound on how much n will increase, so it wouldn't follow that m eventually reaches zero without further inspection. I can't offer a better explanation, but I think it could be done. —The preceding unsigned comment was added by Sam Brightman ( talk • contribs) 15:58, 2 April 2007 (UTC).
I disagree with the down-grading of the Ackermann function from "mid" importance to "low" importance. It is quite important in understanding the distinction between primitive recursive functions and total recursive functions generally. See Primitive recursive function#Relationship to recursive functions, especially the last sentence which says "... a function is primitive recursive if and only if there is a natural number m such that the function can be computed by a Turing machine that always halts within A(m,n) or fewer steps, where n is the sum of the arguments of the primitive recursive function.". JRSpriggs 10:13, 10 June 2007 (UTC)
We need some citations and more information on the relationship between Ackermann's function and primitive recursive functions. David.Monniaux 03:55, 17 June 2007 (UTC)
I fixed the entry for the fourth Ackermann number some time ago, and it got reverted by someone (probably carelessly). I'm placing the incorrect text here:
An attempt to express the fourth Ackermann number, 44, using iterated exponentiation is not practical but it can be expressed using tetration in three nested layers as shown below. Explanation: in the middle layer, there is a tower of tetration whose full length is (already a large number) and the final result is the top layer of tetrated 4's whose length equals the calculation of the middle layer.
The following contains the correct expressions: notice that it actually uses tetration as claimed:
An attempt to express the fourth Ackermann number, 44, using iterated exponentiation as above would become extremely complicated. However, it can be expressed using tetration in three nested layers as shown below. Explanation: in the middle layer, there is a tower of tetration whose full length is and the final result is the top layer of tetrated 4's whose full length equals the calculation of the middle layer. Note that by way of size comparison, the simple expression already exceeds a googolplex, so the fourth Ackermann number is quite large.
Sorry I can't remember my password to log in and sign this. I'll sign it later. Ok: signed by my logged-in ID now: Kaimiddleton 21:37, 20 July 2007 (UTC)
Hello. I just removed a C++ metaprogramming example. It was designed in vain - the templates are highly ambiguous. Here is a transcript of the contents:
template<int x, int y> struct ackermann { enum { v = ackermann<x-1, ackermann<x, y-1>::v>::v } ; } ; template< int y> struct ackermann<0, y> { enum { v = y+1 } ; } ; template<int x > struct ackermann<x, 0> { enum { v = ackermann<x-1, 1>::v } ; } ; template< > struct ackermann<0, 0> { enum { v = 1 } ; } ;
The second and third are equivalent. In a compiler that ignores the name, you'd wind up with a conflict. It doesn't work with GCC (at least in my test) - PGSONIC 00:59, 17 August 2007 (UTC)
I don't see a reason to show the function implemented in a dozen computer languages. It doesn't do anything to add to the understanding of the function and is only of cursory relevance to the article. In particular "Non-Recursive Ackermann in C++" seems more like a geek-badge than encyclopedic content.
There is no point in showing a recursive function can be implemented with a stack as that is how recursion is -- Ott2 18:32, 21 September 2007 (UTC)implemented in computer languages anyway.
Interestingly although "The first implementation in a programming language was in Fortran in 1964, see H. Gordon -- Ott2 18:32, 21 September 2007 (UTC)Rice[13], Recursion and iteration, Commun. ACM, 8(2), 1965, pp. 114--115.)", no Fortran implementation is even given (let alone the first). If any computer implementation of the function was relevant to the article it would be that one and it isn't even provided!
My recommendation is to remove the section or to have only the C definition. 69.121.109.152 19:58, 24 August 2007 (UTC)
Hello - I just came by this article and noticed a statement that I don't believe is correct (underlined):
To my knowledge, iteratively repeated power towers as used in the definition of Graham's number are expressible with Ackermann functions and 5 as the first argument: First arguments 3 are in the order of powers, 4 is in the order of power towers, and 5 in the order of repeated power towers. So I would expect Graham's number to be something like A(5, n) with n something larger than 64 (but not much larger; Ackermann function is in the order of powers of 2, whereas Graham's number is defined through powers of 3). Therefore, Grahams number could not be considered an "even larger number" as stated in the article, but upper bounds can be expressed through the Ackermann function with reasonably small arguments. Comments? Thanks, Jens Koeplinger 13:28, 27 August 2007 (UTC)
It was already said that there are too many implementations. Thus I deleted those implementations that I considered obscure. So far so good. The Matlab implementation was promptly readded. But: Matlab is just some CAS, right? I don't see its outstanding importance, least that the Ackermann function needs to be explained in terms of this "language". (I would also be happy to see even less implementations but couldn't decide on a language.) -- 53.122.197.194 ( talk) 13:57, 26 November 2007 (UTC)
Correct me if I'm wrong, but couldn't that program be int ackermann(int m, int n) {
if (m == 0) return n+1; if (n == 0) return ackermann(m-1, 1); return ackermann(m-1, ackermann(m, n-1));
} ?
Considering that it's 'written' in C and that after a return statement, it wouldn't evaluate the rest? At the very least, I would remove the "m>0" parts, because presumably if m is not zero, it is greater than zero. Sorry, can't log in account right now. Gremlinman. —Preceding unsigned comment added by 24.218.46.235 ( talk) 00:05, 5 December 2007 (UTC)
There is a citation needed note on the claim that Donald Michie invented memoization. There are citations on both his page Donald Michie and the Memoization pages. I'm not sure whether to copy that reference here, or if it would be better to remove the claim here since there isn't anything Ackermann-specific about it, and if someone wants to go look at the memoization page they'll see the claim right at the top (and the citation).
Or could the call for citation be about the claim that compilers can do memoization automatically? Certainly they can (Haskell for example [4], among plenty of others). But again, it seems to me that such details belong on the Memoization page.
-- JamesPaulWhite ( talk) 06:31, 13 April 2008 (UTC)
The " Hyper() function" appears to be someone's private terminology for one of the more common variants of the Ackermann function, and the family of so-called "hyper operators" is just the related hierarchy of fast-growing functions. Here's a relevant quote from that article, which should explain why it ought to be merged with Ackermann function:
There is a lot of good information in the Hyper operator article, but it seems to be in the wrong place, using someone's private terminology. (As far as I know, there is no published source for that terminology in this context.) I happen to like variants of the operator notation used there, i.e, a(k)n, but I expect that just about anyone who has worked very much with this hierarchy of functions has probably invented something like it for themselves; but, again, I haven't seen it used in publications (presumably because it would seem too trivial to mention).
An important point is that each function (operator) in the Ackermann hierarchy, i.e. each function obtained from the Ackermann function by fixing the argument that determines the "operator level" (i.e. 0 <-> successor, 1 <-> addition, 2 <-> multiplication, etc.), *is* primitive recursive. It's the function of all three arguments (or two in the case of the two-argument version in the present article) that's recursive but not primitive recursive.
--
r.e.s. (
talk) 19:24, 26 September 2008 (UTC)
Ackermann function is not "just" an example of a recursive function that is not primitive recursive. It plays a fundamental role in computability theory because it is the proper complexity measure of several algorithms, and the complexity measure of several decidable problems. For example, McAloon shows that controlled sequences of incomparable n-dimensional vectors of natural numbers have length bounded by a version of A(n,x) (see McAloon, TCS 1984). This provides an Ackermann upper bound for many algorithms that rely on Dickson's lemma for their termination. And there exist problems with this Ackermann upper bound for which a matching lower bound can be established. An example being the equivalence of bounded Petri nets (see Mayr and Meyer, JACM 1981). PhS ( talk) 20:25, 26 September 2008 (UTC)
I moved the definition back to the lower section. It might (I'm not quite sold) be worth adding it to the lede. But it would need to go lower in the lede, not at the top. The goal of the first part of the article is to establish context and give a general description that essentially anybody can understand. So what is presently the first paragraph really should be the first paragraph. — Carl ( CBM · talk) 01:17, 29 October 2008 (UTC)
Having read the article linked to as well as all blog comments falling under that article made by xkcd, I see nowhere where he claims his "xkcd number" is the largest ever concisely defined. The article says that Adam Clarkson considered the Clarkkkkson number to be the largest ever concisely defined. Then he says his intuition is that the xkcd number is probably larger but he is not sure, and asks if any of his readers can demonstrate which is larger. Therefore I am amending the sentence. Incantar ( talk) 07:14, 11 March 2009 (UTC)
I cannot find the definition by Rózsa Péter and Raphael Robinson that is referenced in the History section. 150.252.46.189 ( talk) 22:51, 26 March 2009 (UTC)
The article states that 'one should not confuse the primitive recursive functions with those definable by primitive recursion'. As far as I understand things, the primitive recursive functions are exactly those definable by primitive recursion (i.e. without general recursion), so, unless people have valid objections, I will delete the sentence. -- Acipsen ( talk) 18:18, 28 December 2009 (UTC)
Why is this section in Ackermann function? No mention is made of the function at all. It would be better moved in toto to Knuth's up arrow page. OR to convert 1^1, 2^^2, 3^^^3 etc into Ackermann function calls some how. -- SGBailey ( talk) 21:17, 9 July 2010 (UTC)
"Recursive" is the same as "total computable", but not the same as "computable". It is not surprising that the set of primitive recursive functions is not the same as the set of computable functions, since all p.r. functions are total and there exists at least one computable function which is not total. The interesting thing about the Ackermann function is that it shows that not every total computable function is primitive recursive, so this should be explicitely mentioned. – Adrianwn ( talk) 05:16, 13 July 2010 (UTC)
[unindent] I have looked up "Recursively enumerable sets and degrees: a study of computable functions and computably generated sets" by R.I. Soare (Springer, 1987) link, in which he states:
We shall accept Church's thesis and from now on shall use the terms "partial recursive (p.r.),", "Turing computable," and "computable" interchangeably.
On the other hand, he equates the total functions with recursive resp. computable:
An algorithmic partial function which is defined on all arguments (i.e., which is total), is called "recursive" or "computable".
Am I missing something?
Please note that in the end I don't care what term is used in the article, however,
Adrianwn ( talk) 14:38, 13 July 2010 (UTC)
Since there are no objections to the terminology as used in the article now, should we use it in other articles as well? To summarize:
In my opinion, we should. – Adrianwn ( talk) 07:15, 18 July 2010 (UTC)
I am going to delete the section on extending the Ackerman functions to the complex plane. It appears to be based on a misunderstanding. As this link shows http://mathoverflow.net/questions/2944/, one can find many different entire functions that agree with say A(m,n) for a fixed m and all n. The present section seems to doubt that there is any extension at all.
Perhaps something different was meant. If so someone else can rewrite the section and restore it. But as it is, I find actively misleading. MathHisSci ( talk) 23:19, 16 December 2010 (UTC)
xkcd is awesome! — Preceding unsigned comment added by AdamDavid ( talk • contribs) 21:25, 17 April 2011 (UTC) Umm... You probably shouldn't do something like this — Preceding unsigned comment added by EZ132 ( talk • contribs) 16:45, 18 February 2020 (UTC)
The forth equation in History is WRONG. — Preceding unsigned comment added by 72.129.87.43 ( talk) 00:36, 28 July 2011 (UTC)
I've just deleted 7 programming examples. I see no reason we need them. If your programming language supports recursion and you've passed Computer Science 101, then you know how to turn this function into code. It exposes no interesting issues in computer science. The output of the function isn't even interesting in any sense; it's just a simple example of a computable function that's not primitive recursive. The only way code for this function could be interesting if it were showing how to implement a recursive function in a language that doesn't natively support that, and I don't think this is the right article for that.
If we do need a programming example, can we at least have one pseudo-code one instead of seven examples?-- Prosfilaes ( talk) 18:46, 7 May 2012 (UTC)
There appears to be some confusion about the definition of the Ackermann function using Succ and Iter. Using the iteration operator defined by
I think the right definition for the Ackermann function is the following:
and not
(note the parens).
The second definition cannot be right anyway as it would imply
looping indefinitely. Or am I confused? Anyway, I would like to see a source for these definitions. — Tobias Bergemann ( talk) 19:53, 14 July 2012 (UTC)
ack 0 n = n+1
ack (m+1) 0 = ack m 1
ack (m+1) (n+1) = ack m (ack (m+1) n)
ack 0 = succ
ack (m+1) = h where
h 0 = ack m 1
h (n+1) = ack m (ack (m+1) n)
m
-mentionings inside the body of h:ack 0 = succ
ack (m+1) = h (ack m) where
h f 0 = f 1
h f (n+1) = f (ack (m+1) n)
m
by using ack(m+1) = h (ack m)
and h (ack m) == h f
when seen from inside the local h
:ack 0 = succ
ack (m+1) = h (ack m) where
h f 0 = f 1
h f (n+1) = f (h f n)
ack n m == m+1
for all nonnegative n m. A really bad typo! ;) --
Daniel5Ko (
talk) 21:54, 16 July 2012 (UTC)In the current page: "Logician Harvey Friedman defines a version of the Ackermann function as follows:
He also defines a single-argument version A(n) = A(n, n).[6]"
I'm recommending, whether or not Friedman originally used 'A' when introducing his function, that Wikipedia change the letter for his function, to 'F' maybe. The reason is in the next para from the article,(see under next line): it's not going to be clear to a reader in a hurry which 'A' is talked about. Maybe it doesn't matter mathematically which 'A' is talked about, if the exact same argument can show both aren't prim recursive, but it's still confusing.
"A single-argument version A(k) = A(k, k) that increases both m and n at the same time 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). It can be seen that A(n) is roughly comparable to fω(n) in the fast-growing hierarchy. This extreme growth can be exploited to show that f, which is obviously computable on a machine.... " 76.218.104.120 ( talk) 08:54, 8 January 2014 (UTC)
Editor CBM has reverted automated edits made to this article that remove the article from
Category:Pages containing cite templates with deprecated parameters. I have added {{
bots|deny=Monkbot}}
to the top of the page which I think will prevent the bot from revisiting.
— Trappist the monk ( talk) 19:46, 12 January 2014 (UTC)
I removed these two equations involving the m [ ] notation, since it was unclear what it means.
In any case I think these equations are not essential, since a full definition of the 3 argument Ackermann function is given in the following Definition and Properties section. Perhaps the m notation has a standard meaning in the literature of hypercomputation, of which I am unaware, but if so I think a further explanation is needed in the present context. CharlesHBennett ( talk) 19:34, 6 July 2015 (UTC)
Yesterday, the section on Ackermann numbers was removed by user Cagrhsi ( talk · contribs), with the edit comment "The Ackermann numbers were determined to be a non-notable addition to this page during the Chihiro number controversy." I don't know what "Chihiro number controversy" refers to, and I can't really comment on the notability of the Ackermann numbers. Anyway, this edit left dangling redirects Ackermann number and Ackermann numbers. Should these be deleted now? – Tobias Bergemann ( talk) 08:06, 16 October 2015 (UTC)
Does this function have any real-world applications, or is it only interesting in theoretical math? -- Beland ( talk) 22:45, 21 October 2015 (UTC)
The comment(s) below were originally left at Talk:Ackermann function/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.
A longer lead, and more balance would improve this. The "Implementations" and "Inverse" sections in particular would benefit from some review. Geometry guy 15:22, 9 June 2007 (UTC) |
Last edited at 15:22, 9 June 2007 (UTC). Substituted at 19:44, 1 May 2016 (UTC)
Ackermann's original function is presented in the article under History, but the Ackermann-Péter function appears earlier than it, in the introduction. Would it be appropriate to move the "true" Ackermann function to the introduction and present it before leading into the simplified Ackermann-Péter function? The latter is of course better-known, but I think it may be more correct to present Ackermann's original function first. 00dani ( talk) 01:18, 30 August 2016 (UTC)
Hello fellow Wikipedians,
I have just modified 2 external links on Ackermann function. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:
{{
dead link}}
tag to
http://www.math.osu.edu/~friedman.8/pdf/AckAlgGeom102100.pdfWhen you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at {{
Sourcecheck}}
).
This message was posted before February 2018.
After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than
regular verification using the archive tool instructions below. Editors
have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the
RfC before doing mass systematic removals. This message is updated dynamically through the template {{
source check}}
(last update: 18 January 2022).
Cheers.— InternetArchiveBot ( Report bug) 12:26, 3 October 2016 (UTC)
The following "proof" of the fact that the Ackermann function is not primitive recursive was added to the article. I have removed it since it is extremely unclear and at the very least contains numerous typos. The definition of the class is not clear since x is not defined (presumably it is the maximum of the xi?). AxelBoldt ( talk) 03:20, 26 April 2017 (UTC)
Remember the properties . Let .
Now we will show that initial functions are in , and that it is closed under functions composition and primitive recursion (which are equivalent to PR). Initial functions: (constant function), (successor) and (projections).
Function composition: .
Primitive Recursion: if (hp1) and (hp2) , if , by induction on n (inductive hypotesis), (base of induction), , QED.
Therefore, PR, but for , then A and APR, QED.
Rules:
B(2, 0) = B(1, 1) = B(0, B(1, 0)) = B(0, B(0, 1)) = B(0, A(1, 1)) = B(0, A(0, A(1, 0))) = B(0, A(0, A(0, 1))) = B(0, A(0, 2)) = B(0, 3) = A(3, 1) = A(2, A(3, 0)) = A(2, A(2, 1)) ... = A(2, A(1, 3)) ... = A(2, A(0, 4)) = A(2, 5) ... = 13 B(3, 0) = B(2, 1) = B(1, B(2, 0)) ... = B(1, 13) = A(B(1, 12), 1) = A(A(B(1, 11), 1), 1) ... = A(A(A(A(A(A(A(A(A(A(A(A(B(1, 1), 1), 1), 1), 1), 1), 1), 1), 1), 1), 1), 1), 1) ... = A(A(A(A(A(A(A(A(A(A(A(A(13, 1), 1), 1), 1), 1), 1), 1), 1), 1), 1), 1), 1) = A(A(A(A(A(A(A(A(A(A(A(A(12, A(13, 0)), 1), 1), 1), 1), 1), 1), 1), 1), 1), 1), 1) = A(A(A(A(A(A(A(A(A(A(A(A(12, A(12, 1)), 1), 1), 1), 1), 1), 1), 1), 1), 1), 1), 1) B(4, 0) = B(3, 1) = B(2, B(3, 0)) = B(2, <too large>)
That's pretty salad, but not super salad. -- EZ132 ( Talk | Contributions | Uploads | log) —Preceding undated comment added 17:00, 18 February 2020 (UTC)
Gabriel Nivasch [1] gives another form of the Inverse Ackermann function. First he defines the inverse ackermann hierarchy:
References
This note links to an author's personal page (where he also sells Jesus books, not that there's anything wrong with that) containing code that very well may be, but isn't obviously, an Ack implementation. Just to be clear: of course you can calculate anything with for-loops if you simulate a program stack and recursion using dynamic memory. An example isn't required, and this one is not particularly illustrative because readers who aren't aware you can do this are going to have to accept that it works on faith. The bigger problem, however, is that this statement and link appears at the end of a proof that has nothing to do with a claim about for-loops. I think the claim and link should be removed from the proof section as it is unrelated. It may be worthwhile to add the link to a section discussing the for-loop thing, but only if more context is provided—but I am not convinced this is a good idea either because the example is not very illuminating. TricksterWolf ( talk) 21:58, 22 June 2021 (UTC)