Talk:Ackermann function

Template:Oldpeerreview

Missing image Cscr-featured.png Featured article star

Ackermann function is a featured article, which means it has been identified as one of the best articles produced by the Wikipedia community. If you see a way this page can be updated or improved without compromising previous work, feel free to contribute.

---

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] (http://www.nist.gov/dads/HTML/ackermann.html) of this function, which seems incompatible with the veresion given here. Are they just plain wrong? -- Pakaran 03:34, 25 Nov 2003 (UTC)

Perhaps they are equivalent? Dysprosia 03:40, 25 Nov 2003 (UTC)

I don't think so, not even if you decrease the arguments in our version. In particular, their definition gives perfect powers of two, where ours gives 3 less than the powers (e.g. wiki_ack(3,3) = 61 = 2⁶-3, while theirs never takes on that value). Their version does snip off the uninteresting bottom few rows of the table, which may not be a bad idea, but it's not the "true" ackermann function. It may or not be asymptotically equal to that function with some change of arguments, I'm not sure on that point. -- Pakaran 03:58, 25 Nov 2003 (UTC)

I've seen quite a few different functions called Ackermann functions, with anything from one through three arguments; about all they have in common was that they are easy-to-define recursive functions which grow too fast to be primitive recursive. I suggest we add a paragraph on these sort of 'variants' of the Ackermann function. 4pq1injbok 23:07, 24 Sep 2004 (UTC)

---

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)

By using formulas for the A(0,n) through A(3,n), one shortcuts the recursion. If a program had to actually thread through the recursion, it would require way way too many steps.

-- Rpresser 21:07, 2004 Sep 1 (UTC)

Contents

1 Pseudocode to Python... 2 Inverse 3 Introduction 4 Intuitive meaning 5 Alternative definition 6 mn 7 Possible vandalism - please check 8 The Ackermann Recursive Function Antinomy

Pseudocode to Python...

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)

Well... I wrote it and designed the language and I don't even know Python. So go figure. I'm sure there are some other differences, if only the emboldened keywords and the ≠ symbol. Derrick Coetzee 23:52, 1 Oct 2004 (UTC)

Inverse

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.

I take issue with the first half of the sentence. It's kind of imprecise. It should at least give the order of the number at which it changes to 5. Also there needs to be some mention of a practical use - the union-find data structure. Deepak 14:35, 24 Sep 2004 (UTC)

That's not something I fully understand myself - it was based on a single paragraph in one of my college textbooks. I don't think we have an article on union-find in any event. F becomes 4 at A(4,4) which has a number of digits whose own number of digits cannot be written in the physical universe, correct me if I'm wrong. It becomes 5 at a number which is far bigger than that. The point is a real computer running union-find on an input with only one element per proton in the universe will have no problem, nor if it first expands each proton to a universe the size of our own a fair number of times. This would probably require an environmental impact statement or something :). Pakaran. 16:24, 24 Sep 2004 (UTC)

Indeed. I remember what Aho-Ulmann had to say "\alpha [the inverse] eventually reaches 4, then 5 and so on in its unimaginably slow crawl to infinity." Let's at least write your description - "number of digits whose own digits cannot be written in the physical universe" (to be pendantic, we should say in base-10). That should be suffficiently impressive. -- Deepak

A(4, 4) is A(3, A(4, 3)), or A(3, A(3, A(4, 2))) - which is to say 2 to the power of a number which is itself 2 to the power of a number which would require a good fraction of a day to read aloud. A(5, 5) is a horse of another color. The practicalities of storing an input the size of either in a PC's address space are left as an exercise. Feel free to add something along the lines we've discussed to the article. Pakaran. 17:50, 24 Sep 2004 (UTC)

Oh, and the number of digits in the number of digits in A(4, 4) can be written in the physical universe, since the number of bits in the number of bits can be (it'll be fairly close to A(4, 2)) Pakaran. 17:54, 24 Sep 2004 (UTC)

Introduction

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)

Intuitive meaning

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.

Alternative definition

At the end of the section about Inverse we can read:

In particular, some modified functions simplify the expression by eliminating the −3 and similar terms.

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:

<math>

 A(m,n)=
  \left\{
   \begin{matrix}
    n+2,\qquad\qquad\qquad\quad\,&&\mbox{if }m=1;\ \ \qquad\qquad
   \\
    2,\qquad\qquad\qquad\qquad\quad&&\mbox{if }m>1\mbox{ and }n=1;
   \\
    A(m-1, A(m, n-1))\,&&\mbox{otherwise.}\,\qquad\qquad
   \end{matrix}
  \right.
<math>

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)

mⁿ

The explanation of mⁿ as "m multiplied by itself n times" is not quite true. For example, it implies that m¹ 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. Drew Devereux 01:15, 20 Dec 2004 (UTC)

I consider this to be one of those cases where being a little wrong in a few edge cases for the purpose of simplicity is okay. But I'll try and stick in a word or two as a reminder. Deco 03:29, 5 Feb 2005 (UTC)

Possible vandalism - please check

User 213.94.207.61 made a change months ago: here (http://en.wikipedia.org/w/index.php?title=Ackermann_function&diff=prev&oldid=6120197).

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 (http://en.wikipedia.org/w/index.php?title=Special:Contributions&target=213.94.207.61))

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 Recursive Function Antinomy

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]

Hooray, a crank! Here's why you're wrong:

• The Ackermann function is a function, if you define a function (like every other mathematician) to be a set of pairs. It has a procedure for computing it which provably always halts, which is enough to prove that the function exists and is unique.
• It's not primitive recursive, and that's not "generally believed", that's a proven theorem - therefore any "counterargument" you offer is fallacious before I read it. The fact that you can expand it in terms of its own values in ways other than the recursive definition is true but irrelevent.
• Cantor's diagonal argument is also not a paradox.

Deco 08:01, 25 May 2005 (UTC)