# [plt-scheme] any knows why Ackermann function definition in sicp is different from that in wikipedia ?

On Sat, Sep 22, 2007 at 08:46:21PM -0700, orzz wrote:
I've never seen this one before:
>* (define (A x y)
*>* (cond ((= y 0) 0)
*>* ((= x 0) (* 2 y))
*>* ((= y 1) 2)
*>* (else (A (- x 1)
*>* (A x (- y 1))))))
*>*
*>* http://en.wikipedia.org/wiki/Ackermann_function
*
This is more like the one I'm familiar with:
>*
*>* A(m,n)=
*>* n+1 if m = 0
*>* A(m-1,1) if m > 0 and n = 0
*>* A(m-1,A(m,n-1)) if m > 0 and n > 0
*>*
*>* (define (A-WIKI m n)
*>* (cond ((= m 0) (+ n 1))
*>* ((= n 0) (A-WIKI (- m 1) 1))
*>* (else (A-WIKI (- m 1)
*>* (A-WIKI m (- n 1))))))
*>*
*>* all that confuse me.anyone give me a hand.thx!
*
So the wikipedia matches my recollection. And, I suspect, most
mathematicians', otherwise someone would have changed it.
The whole point of the ackermann function is that if you tabulate it,
each row iterates the previous one. This eentually gives larger
growth rates. And going down the diagonal, you get a growth rate
greater than you can get with any finite number of primitive
recursions (e.g., Fortran DO-loops).
I haven't looked in detail, but I think both of the ones you've
presented satisfy this purpose.
I'm told that Ackermann's original function wasn't any of these,
though. The one that's well-known and used nowadays is presumably a
refined version of what he originally proposed. His was, I believe,
a three-argument function. With the first argument n = 0, (or did he
start with one) it gave addition; with n = 1, it gave multiplication,
with n = 2, exponentiation, and so on.
-- hendrik
>*
*>* _________________________________________________
*>* For list-related administrative tasks:
*>* http://list.cs.brown.edu/mailman/listinfo/plt-scheme
*