Consider inverse of Ackermann function, can we conclude that the growth rate of it as the same as growth rate $\log^*n$?
1
-
2$\begingroup$ This is not what is written here. $\endgroup$– NathanielNov 20, 2021 at 16:02
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
No, since the Ackermann function grows faster than any primitive recursive function.
The iterated logarithm is one of the two inverse functions of tetration. As a primitive recursive function, Tetration with base 2 is "roughly" equivalent to $A(4,n)$, where $A(m,n)$ is the Ackermann function of two variables . $A(n,n)$ is assumed to be the Ackermann function in the question.
Exercise. Show that the inverse of Ackermann function grows slower than $\log^*(\log^∗n)$.
-
$\begingroup$ Here is one more exercise. Define the iterated "iterated logarithm". Show that the inverse of Ackermann function grows slower than it. $\endgroup$– John L.Nov 20, 2021 at 20:33
-
$\begingroup$ This answer is meant to provide an intuitive understanding, assuming the basic knowledge of primitive recursive function or the basic properties of the Ackermann functions. The terminologies and argument here is not meant to be strict. For example, $f$ grows faster than $g$ does not imply "the inverse" of $f$ grows slower than "the inverse" of $g" necessarily. $\endgroup$– John L.Nov 20, 2021 at 20:46
-
1$\begingroup$ My question is how we can show $\alpha(n)=o(\log^*n)$? $\endgroup$– AhmadNov 21, 2021 at 1:06
-
1$\begingroup$ @Ahmad, I will update to show that. Basically, $\alpha(A(5,m))=o(m)$ while $\log^*(A(5,m))=\omega(m)$. $\endgroup$– John L.Nov 21, 2021 at 1:41
-