3
$\begingroup$

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$?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Simply Beautiful Art Jun 14 '17 at 11:53
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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)$. $\endgroup$ – Xoff Mar 13 '15 at 9:20
  • $\begingroup$ 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. $\endgroup$ – Deedlit Mar 13 '15 at 10:01
  • $\begingroup$ @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. $\endgroup$ – Wojowu Mar 13 '15 at 10:11
  • $\begingroup$ @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. $\endgroup$ – Xoff Mar 13 '15 at 10:15
  • $\begingroup$ @Xoff I'm sorry, I meant a computable function there, so it should say "$f_\alpha$ is never faster than certain computable function". $\endgroup$ – Wojowu Mar 13 '15 at 10:16

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.