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

 From: orzz (123orzz at gmail.com) Date: Wed Sep 26 04:05:12 EDT 2007 Previous message: [plt-scheme] any knows why Ackermann function definition in sicp is different from that in wikipedia ? Next message: [plt-scheme] MrEd - Gui Messages sorted by: [date] [thread] [subject] [author]

``` Thankx both of you very much!

hend... at topoi.pooq.com 写道：
> 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
> with n = 2, exponentiation, and so on.
>
> -- hendrik
>
> >
> > _________________________________________________