# What is the least ordinal $\beta$ for which the function $f_\beta(n)$ in fast-growing hierarchy is incomputable?

Fast-growing hierarchy consists of a transfinite succession of faster growing functions $f_\alpha$:

$f_0(n) := n+1$,

$f_{\alpha+1}(n) := f^n_\alpha(n)$,

$f_{\alpha}(n) := f_{\alpha[n]}(n)$ if $\alpha$ is a limit ordinal where $\alpha[n]$ denotes the n-th element of the fundamental sequence assigned to the limit ordinal $\alpha$.

Ackermann function grows about as fast as $f_\omega$. Some functions like busy beavers grow faster than any computable function. My question is:

What is the least ordinal $\beta$ for which the function $f_\beta(n)$ in fast-growing hierarchy is incomputable?

Clearly, $\beta$ is no greater than Church-Kleene ordinal $\omega^{CK}_1$ since that is the incomputable ordinal itself, but could $\beta$ be smaller, e.g. $\epsilon_0$?

• One could always just assign an uncomputable fundamental sequence: $$\omega=\sup\{BB(1),BB(2),BB(3),\dots\}$$ Indeed, you have to assign fundamental sequences to give meaning to what $f_\alpha$ means. – Simply Beautiful Art Jun 14 '17 at 11:53

That depends on the system of fundamental sequences that is used. If the system of fundamental sequences for all limit ordinals less than or equal to $\beta$ is computable, then $f_\beta$ will be computable.
More precisely, say we have a computable ordinal $\beta$ and some injective function $g: \beta+1 \mapsto \bf{N}$ such that the image of the limit ordinals, the image of the successor ordinals, and the predecessor function $j(g(\alpha+1)) = g(\alpha)$ are all computable. Suppose further that there is a computable function $h: \bf{N} \times \bf{N} \mapsto \bf{N}$ such that, for each limit ordinal $\alpha \le \beta$, $g^{-1}(h(g(\alpha),n))$, as a function of $n$, gives the fundamental sequence for $\alpha$. Then $f_\beta$ is computable.
Note that it would not be sufficient if for each limit ordinal $\alpha \le \beta$ there would be a computable function $h_\alpha$ such that $g^{-1}(h_\alpha(g(n))$ gives the fundamental sequence for $\alpha$. A counterexample would be to set $\omega (n+1) [m] = \omega n + BB(n+1)+m$ and $\omega^2 [m] = \omega m$, where $BB(n)$ is the busy beaver function. Then $f_{\omega^2}(n)$ would exceed the busy beaver function.
Also, it is not clear to me that $f_{\omega^{CK}_1}(n)$ must be incomputable. Certainly we cannot compute it through an ordinal notation for $\omega^{CK}_1$, but it may be computable some other way.
• I think that $f_{\omega_1^{CK}}$ is uncomputable because for any computable total function $\phi$ you can find a computable ordinal $\alpha$ such that $\exists N \forall x\ge N\;\phi(x)<f_{\alpha}(x)$. – Xoff Mar 13 '15 at 9:20
• That would do it, but how would you prove that statement? Note that $f_\alpha$ is not a uniquely defined function, it depends on the choice of fundamental sequences. – Deedlit Mar 13 '15 at 10:01
• @Xoff You are unfortunatelly mistaken. Indeed, we can find system of fundamental sequences such that $f_\alpha$ is never faster than certain uncomputable function. On the other hand, even if your claim was true and for any $\phi$ we could find such $\alpha$, it doesn't imply that $f_{\omega_1^{CK}}$ is uncomputable. – Wojowu Mar 13 '15 at 10:11
• @Wojowu : I don't understand why being bound by some uncomputable function is a contradiction to my claim. Can you explain ? But if my claim is true, it really means that $f_{\omega_1^{CK}} dominates all computable functions, and then can't be computable. – Xoff Mar 13 '15 at 10:15 • @Xoff I'm sorry, I meant a computable function there, so it should say "$f_\alpha\$ is never faster than certain computable function". – Wojowu Mar 13 '15 at 10:16