2
$\begingroup$

After reading about Ackermann functions , tetration and similar, I considered the commutative following hyperoperator ?

$$ F(0,a,b) = a + b $$ $$ F(n,c,0) = F(n,0,c) = c $$ $$ F(n,a,b) = F(n-1,F(n,a-1,b),F(n,a,b-1)) $$

I have not seen this one before in any official papers. Why is this not considered ? Does it grow to slow ? Or to fast ?

It seems faster than Ackermann or am I wrong ?

Even faster is The similar

$$ T(0,a,b) = a + b $$ $$ T(n,c,0) = T(n,0,c) = n + c $$ $$ T(n,a,b) = T(n-1,T(n,a-1,b),T(n,a,b-1)) $$

which I got from a friend.

Notice if $nab = 0 $ then $T(n,a,b) = n + a + b $.

One possible idea to extend these 2 functions to real values , is to extend those “ zero rules “ to negative ones.

So for instance for the case $F$ :

$$ F(- n,a,b) = a + b $$ $$ F(n,-a,b) = -a + b $$ $$ F(n,a,-b) = a - b $$

The downside is this is not analytic in $n$.

Any references or suggestions ??

$\endgroup$
1
$\begingroup$

Let $F_n^{(a)}(b)=F_n(a,b)=F(n,a,b)$ and likewise $A_n(m)=A(n,m)$ for the Ackermann function.

Let $F_n(a)=F_n(a,a)$ as the symmetric case.

It is trivial to see this is increasing in all arguments. Thus we can make the following bounds:

$$F_n(a,b)\le F_{n-1}(\max\{F_n(a-1,b),F_n(a,b-1)\})$$

By induction, we can show that the optimal choice of $m$ will only subtract from one side, leading to

$$m=F_n(\min\{a,b\}-1,\max\{a,b\})$$

WLOG assume $a>b$. This thus gives us:

$$F_n^{(a)}(b)\le F_{n-1}(F_n^{(a)}(b-1)),~F_n^{(a)}(0)=a$$

In the end, this makes $F_n(a,b)$ behave like the usual Ackermann function with the base case modified from $A_n(0)=A_{n-1}(1)$ to $F_n^{(a)}(0)=a$.

So it's easy to see that this grows similarly to the Ackermann function and does not grow much faster or slower. The same analysis holds for $T$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.