Ackermann function and hyper operations

[andydude]

I wanted to say something about the first part, "1 Introduction". In this part of the paper, you equate the original Ackermann function with a[n]b, which (stictly speaking) is not true. Robert Munafo has discussed this on his website (http://www.mrob.com/pub/math/largenum.html), and I have also verified this for myself by reading the original paper Ackermann wrote. Ackermann's tetration is a function \( f(n, m) = \phi(n, m, 3) = {}^{(m+1)}n \) which is an offset from tetration. Because it is an offset of tetration, \( \phi(n, m, 4) \) is not pentation at all. It wasn't until Reuben Goodstein that the "offset" disappeared. I think we should take this into account when discussing the original Ackermann function, because its evolution is way more complicated than any introduction can really summarize.

[bo198214]

@Andrew: Good! Thats a very attentive observation.


While verifying myself I found that the deviation (up to a difference of 1 in the rank) from our operator sequence comes from forming an unnecessary odd initial condition. I dont know why he does, perhaps it is more suitable for his proof of non-primitive recursiveness.

In his article
Ackermann, W. (1928 ). Zum Hilbertschen Aufbau der reellen Zahlen. Math. Ann., 99, 118–133.

Ackermann defines:
\( \varphi(a,b,0)=a+b \)
\( \varphi(a,b,n+1)=\varrho_c(\varphi(a,c,n),\alpha(a,n),b) \).

Where \( \varrho_c(f( c),a,n)=f^{[n]}(a) \) in our notation (\( c \) is a free variable here to determine the argument of the function to be applied).

So everything would be good if the initial value was \( \alpha(a,n)=1 \) for \( n\ge 1 \). Then would \( \varphi(a,b,n)=a [n+1] b \). But instead Ackermann defines:

\( \alpha(a,n) = \iota(n,1)\cdot \iota(n,0) \cdot a + \lambda(n,1) \) where \( \iota(a,b)=1-\delta_{a,b} \) and \( \lambda(a,b)=\delta_{a,b} \) in today notation with the Kronecker-\( \delta \).
This definition is hence equivalent to:
\( \alpha(a,n) = 0 \) for \( n=0 \)
\( \alpha(a,n) = 1 \) for \( n=1 \)
\( \alpha(a,n) = a \) for \( n\ge 2 \)
as he also mentiones in his paper.

So he introduces a third initial value \( \alpha(a,n)=a \) besides 0 and 1 which causes the deviation from our operator sequence:
\( \varphi(a,b,1)=(c\mapsto\varphi(a,c,0)^{[b]}(\alpha(a,0))=(c\mapsto a+c)^{[b]}(0)=a\cdot b \).
\( \varphi(a,b,2)=(c\mapsto \varphi(a,c,1))^{[b]}(\alpha(a,1))=(c\mapsto a\cdot c)^{[b]}(1)=a^{b} \)
\( \varphi(a,b,3)=(c\mapsto \varphi(a,c,2))^{[b]}(\alpha(a,2))=(c\mapsto a^c)^{[b]}(a)=a [4] (b+1) \)

PS: Munafo gives a very detailed description of the different versions of the Ackermann-function here. It is a very good reference to show to someone for explaining about different versions of the Ackermann-function. All glory to Andrew for digging out such references.

[andydude]

Also, about a month ago, I redesigned the Hyperoperation page, to try and explain these differences.

[bo198214]

While verifying myself I found that the deviation (up to a difference of 1 in the rank) from our operator sequence comes from forming an unnecessary odd initial condition. I dont know why he does, perhaps it is more suitable for his proof of non-primitive recursiveness.

Oh now I found out where this odd initial conditions comes from!
I assert that Ackermann originally wanted to define left-braced hyperoperations!
Then this initial condition \( \alpha(a,n)=a \) for \( n\ge 2 \) makes sense!

Left-braced hyperoperations \( \psi \) would similarly be defined by:
\( \psi(a,b,0)=a+b \)
\( \psi(a,b,n+1)=(x\mapsto \psi(x,a,n))^{[b]}(\alpha(a,n)) \)

here again we have \( \psi(a,b,1)=ab \) and \( \psi(a,b,2)=a^b \).
But the forth operation is not \( a^{a^{b-1}} \) as one would obtain with the initial condition \( \alpha(a,2)=1 \), but it is \( \psi(a,b,3)=a^{a^b} \) due to the initial value \( \alpha(a,2)=a \)!

So this initial condition makes left-braced hyperoperations look simpler, while it makes right-braced hyperoperations looking odd.
I think he started with the left-braced hyperoperations and then switched to the faster growing right-braced hyperoperations, perhaps it was more suitable for his proof of non-primitive recursiveness of \( n\mapsto \phi(n,n,n) \)