any knows why Ackermann function definition in sicp is different from that in wikipedia ?

[orzz]

in sicp:

(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
in wikipedia:

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))))))

why they are different? thx!

[Jens Axel Søgaard]

Ackermann used his functions as a simple example
of a computable, but not primitive recursive function.
Text books therefore sometimes calls functions of
this type for Ackermann's function.

See for example:

http://acm.uva.es/p/v3/371.html

for a third one.

The one in Wikipedia is (I think) the original one.
See also:

http://www.modulaware.com/mdlt08.htm

--
Jens Axel Søgaard

[Jim]

On Sep 23, 3:47 am, Jens Axel Søgaard <use...@soegaard.net> wrote:
> Ackermann used his functions as a simple example
> of a computable, but not primitive recursive function.
> Text books therefore sometimes calls functions of
> this type for Ackermann's function.
>
> See for example:
>
> http://acm.uva.es/p/v3/371.html
>
> for a third one.

That seems to me to be a non-standard use of the term. It is my
understanding that most people base their use of the term Ackermann
functions on the observation: addition is iterated successor,
multiplication is iterated addition, exponentiation is iterated
multiplication, etc. Then you can define a function of two variables
A(level,j) where perhaps level 1 is addition so A(1,j)=2j, level 2 is
multiplication so A(2,j)=j^2, etc.

But absolutely, different authors find convienent different approaches
to the details. In particular, many authors define A*(x)=A(x,x) where
A is some version of the function sketched above.

ISTR that Craig Smorynski's _Logical Number Theory_ vol 1 has a nice
discussion and addresses the issue of which is Ackermann's original
fcn.

Jim

[Jens Axel Søgaard]

Jim wrote:
> On Sep 23, 3:47 am, Jens Axel Søgaard <use...@soegaard.net> wrote:
>> Ackermann used his functions as a simple example
>> of a computable, but not primitive recursive function.
>> Text books therefore sometimes calls functions of
>> this type for Ackermann's function.
>>
>> See for example:
>>
>> http://acm.uva.es/p/v3/371.html
>>
>> for a third one.

> That seems to me to be a non-standard use of the term.

I might have overinterpreted.

> It is my
> understanding that most people base their use of the term Ackermann
> functions on the observation: addition is iterated successor,
> multiplication is iterated addition, exponentiation is iterated
> multiplication, etc. Then you can define a function of two variables
> A(level,j) where perhaps level 1 is addition so A(1,j)=2j, level 2 is
> multiplication so A(2,j)=j^2, etc.

You are probably right.

> But absolutely, different authors find convienent different approaches
> to the details. In particular, many authors define A*(x)=A(x,x) where
> A is some version of the function sketched above.
>
> ISTR that Craig Smorynski's _Logical Number Theory_ vol 1 has a nice
> discussion and addresses the issue of which is Ackermann's original
> fcn.

Rereading the Wikipedia entry, I notice this paragraph:

Ackermann originally considered a function A(m, n, p) of three
variables, the p-fold iterated exponentiation of m with n, or m → n →
p as expressed using the Conway chained arrow notation. When p = 1,
this is mn, which is m multiplied by itself n times. When p = 2, it is
the double exponentiation {{m^{m^m}}}, and with p > 2, it is a tower
of exponents {{m^m}^{{\cdot}^{{\cdot}^{{\cdot}^m}}}} with n levels, or
m raised n times to the power m also written as nm, the tetration of
m with n. We can continue to generalize this indefinitely as p becomes
larger.

Since the two-argument version is simpler, that explains why writers
modified Ackermann's version in the first place.

--
Jens Axel Søgaard