Ackermann's function and all the up-arrow notation is based on exponentiating. We know for a fact that the factorial function grows faster than any power law so why not build an iterative sequence based on factorials? I am thinking of the simple function defined by
$$
a(n)=a(n-1)!
$$
and to start things off we need $a(1)=3$. The numbers generated are $3,6,24,720$ and the next one ($720!$) is roughly $10^{1746}$ and I can't even start to imagine what happens next!
Is it primitive recursive? Can it be coded up using for loops avoiding calls to itself? I think not but this is just a hunch. Computer scientists might have better chances of answering that than I.
Thanks in advance, I appreciate it.
Best Answer
So you mean the function $a(n)$ defined by $a(1)=3$ and $a(n) = a(n-1)!$.
This function is primitive recursive. Multiplication can be defined by a primitive recursive scheme. Based on this, the factorial function can be defined by a primitive recursive scheme. From here, you can use induction on $n$ to show that $a(n)$ is primitive recursive.