patternMinor
Definition of the inverse of the Ackermann function
Viewed 0 times
definitiontheinversefunctionackermann
Problem
I am somewhat puzzled by the definition of the inverse of the Ackermann function: The normal Ackermann function $A$ can be used to define a function from $\mathbb{N} \to \mathbb{N}$ via $A(n, n)$. The inverse of this function, denoted by $\alpha$, is known as the inverse Ackermann function.
My problem is: Only bijective functions have an inverse. But I have seen no proof that $A(n, n)$ is indeed bijective. It seems highly unlikely to me that this is the case (since the value of $A(n, n)$ increases very quickly in $n$).
My guess is that $\alpha(m)$ should be defined as $\min \{n \mid A(n, n) \geq m\}$ or $\max \{n \mid A(n, n) \leq m\}$. Is that the case?
My problem is: Only bijective functions have an inverse. But I have seen no proof that $A(n, n)$ is indeed bijective. It seems highly unlikely to me that this is the case (since the value of $A(n, n)$ increases very quickly in $n$).
My guess is that $\alpha(m)$ should be defined as $\min \{n \mid A(n, n) \geq m\}$ or $\max \{n \mid A(n, n) \leq m\}$. Is that the case?
Solution
The Ackermann function $n \mapsto A(n,n)$ is definitely very far from being bijective, otherwise it could not grow so quickly. However, in the contexts it is usually employed (complexity theory, oh notations, ...) it is not really relevant which are the actual values of $\alpha$ point by point. You can add one or multiply by three and the results are the same, so nobody really cares about what is the actual definition. Any of your two will work.
Context
StackExchange Computer Science Q#75145, answer score: 5
Revisions (0)
No revisions yet.