[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