2
$\begingroup$

I have been looking at this question Does there exist a computable function that grows faster than fast growing hierarchy?, but I dont understand the answer and cant use it to answer this question myself. I've been reading this article https://medium.com/@joshkerr/mind-blown-the-fast-growing-hierarchy-for-laymen-aka-enormous-numbers-d9a865c6443b . In this article, author is going through different ordinals and hierachies all the way up to $ \omega^{CK}_1 $, which is the growth rate comparable to that of Busy Beaver, but in this hierarchy are only functions using recursions and diagonalizations over a starting function, $f(n)=n+1$ in this case (at least that is how I understand it).

So, in theory, that does not mean necessarilly, that there can't be computable function $F$, such that for any ordinal $\alpha$ in the hierarchy bellow $ \omega^{CK}_1 $ there is infinitely many numbers $n$, such that $F(n)>f_{\alpha}(n)$. So, the function does not need to be monotone even, but more like no function in fast growing hierarchy outgrows it. Hope I described my question correctly. Can such a function exist, or is its existence contradiction?

$\endgroup$
  • $\begingroup$ As long as we can define the diagonalizations, we can continue the fast growing hierarchy forever. In principle, this should be possible. The busy beaver function grows faster than any computable function and the hierachy you mentioned is still computable. So, I do not think that we can claim that any growth rate in the fast growing hierarchy is comparable to busy-beaver. $\endgroup$ – Peter Aug 3 '17 at 15:22
  • $\begingroup$ But the author states this to the end of the article "This is the smallest ordinal that cannot be created through recursive functions. Up to this point, all of the functions we created used recursion. The Church Kleene Ordinal is so big that it cannot be reached via recursion. It cannot be described via recursive functions. Another way to say this is that there is no computable function that can reach this ordinal". Either he is wrong, or this is actually so complicated to reach it, that no amount of recursion (computationally equivalent to TM) can reach this growth rate. $\endgroup$ – TStancek Aug 3 '17 at 15:58
  • $\begingroup$ I am not sure, but I think functions can be computable even if they cannot be expressed via repeated recursions, but maybe I am wrong. $\endgroup$ – Peter Aug 3 '17 at 16:02
  • $\begingroup$ I thought that too, but the article says otherwise... $\endgroup$ – TStancek Aug 3 '17 at 16:04
  • 1
    $\begingroup$ Please, if you find the time, read the part after TREE function in the article. I don't know how or why, he is just going through more and more generalizations of diagonalizing, until somehow, he ends up with diagonalizing over all computable functions. I probably would need to take some lectures on the FGH, but with my understandings, it just does not make sense to me. But I was hoping, that for some genius mind it is "no-brainer". But apparently, I am not the only one struggling with understanding/accepting that. $\endgroup$ – TStancek Aug 3 '17 at 16:40
3
$\begingroup$

First, there is an error in Josh Kerr's article; while Kerr does not define what $\Psi_\alpha(\beta)$ is for $\alpha \ge 1$, presumably he intends to give some recursive definition, and therefore $\sup \lbrace \Psi(0), \Psi_{\Psi(0)}(0), \Psi_{\Psi_{\Psi(0)}(0)}(0), \ldots \rbrace$ will be a recursive ordinal, not $\omega_1^\text{CK}$. You can keep going and going with more and more diagonalizations, but as long as the notation you describe is recursive, i.e. you can interpret it with a computer program, you will never reach $\omega_1^\text{CK}$. So it is in a sense incredibly complex.

An important thing to note about "the" fast-growing hierarchy is that the general version is not uniquely defined. Specifically, in the third rule

  1. For limit $\alpha$, $f_\alpha (n) = f_{\alpha[n]}(n)$

we reference this undefined $\alpha[n]$ function, which is known as the fundamental sequence of $\alpha$. So to uniquely specify the fast-growing hierarchy, we have to define the fundamental sequences for all limit ordinals in the domain of our hierarchy.

Now, if we define our fundamental sequences in the "correct" way, we can observe some nice consequences. For example, if we define fundamental sequences up to $\varepsilon_0$ in the obvious way, we have that $f_\alpha$ is PA-recursive (here PA stands for the theory Peano Arithmetic) for $\alpha < \varepsilon_0$, $f_{\varepsilon_0}$ is not PA-recursive, and every PA-recursive is dominated by $f_\alpha$ for some $\alpha < \varepsilon_0$. ($f$ is dominated by $g$ if there exists a natural number $n$ such that for all $m > n, f(m) < g(m)$.) In fact, a recursive function is PA-recursive if and only if it can be computed by a Turing Machine in time $T(n)$ such that $T(n)$ is dominated by $f_\alpha(n)$ for some $\alpha < \varepsilon_0$. Why $\varepsilon_0$? Because the proof-theoretic ordinal of PA is $\varepsilon_0$!

If we extend the fast-growing hierarchy further, we can see the same phenomenon occurring for stronger and stronger theories. So, with the appropriate fundamental sequences, we have that $f_\alpha$ is ATR-recursive for $\alpha < \Gamma_0$, and every ATR-recursive function is dominated by some $f_\alpha$ for some $\alpha < \Gamma_0$. ($\Gamma_0$ being the proof-theoretic ordinal of the theory ATR) Similarly for the theory $\Pi^1_1-\text{CA}_0$ and the ordinal $\psi_0(\Omega_\omega)$.

So, one can optimistically hope for the following: so long as one sticks to "natural" definitions of fundamental sequences, for a strong "nice" theory T with proof theoretic ordinal $\tau$, we will have $f_\alpha$ T-recursive if and only if $\alpha < \tau$, and every T-recursive function is dominated by $f_\alpha$ for some $\alpha < \tau$. We need some requirement on fundamental sequences, since otherwise we could be mischievous and define $\omega[n] = BB(n)$ where $BB(n)$ is the Busy Beaver function, or something silly like that. We also need some requirement on the theories we use, since if the theory is unsound we can have peculiar things like having the proof-theoretic ordinal equal to $\omega_1^\text{CK}$. If our optimistic hope is true, then the statement you are asking about will be true as well: If $\alpha < \omega_1^\text{CK}$ then $\alpha$ will be less than the proof-theoretic ordinal for some nice theory T, and so $\alpha$ will be T-recursive, and therefore recursive. Going in the other direction, if $g$ is recursive, it will be T-recursive for some nice theory T with proof-theoretic ordinal $\tau$, so $g$ will be dominated by $f_\alpha$ for some $\alpha < \tau < \omega_1^\text{CK}$.

So that would be great. The problem is, there seems to be little hope of proving our dream scenario is in fact possible. The first problem is that it is not even a precise mathematical statement until we give a precise definition of "natural family of fundamental sequences". I believe this is a well-known problem in proof theory, and no one has really made any progress on it, nor do people believe that it can be done. So this seems to dash our hopes.

In the positive direction, it is possible to explicitly define fundamental sequences for all limit ordinals up to $\omega_1^\text{CK}$. (and even beyond) For example, Kleene's $\cal O$ gives a correspondence between recursive ordinals and natural numbers, although a single ordinal can correspond to many natural numbers. So we can define a fundamental sequence for a recursive ordinal $\alpha$ in the following way: define $\alpha[0] = 0$ and $N_\alpha(0) = 0$. ($0$ is the natural number corresponding to the ordinal $0$ in Kleene's $\cal O$.) Once $\alpha[n]$ and $N_\alpha(n)$ are defined, we define $N_\alpha(n+1)$ to be the smallest natural number greater than $N_\alpha(n)$ corresponding to an ordinal greater than $\alpha[n]$ but less than $\alpha$. We then define $\alpha[n+1]$ to be the ordinal corresponding to $N_\alpha(n+1)$. The result is that $\alpha[n]$ is an increasing sequence of ordinals converging to $\alpha$, as desired.

So, rather than have a notion of "natural" fundamental sequences, we have a unique family of fundamental sequences for recursive limit ordinals. So we only need to prove that this particular fast-growing hierarchy resulting from this family of fundamental sequences is such that $f_\alpha$ is recursive for $\alpha < \omega_1^\text{CK}$, and every recursive function is dominated by $f_\alpha$ for some $\alpha < \omega_1^\text{CK}$. However, I do not know how to prove this, and it seems like it may be dauntingly hard. Anyone have any particular ideas for how to approach this?

In summary, your statement is not necessarily true, as the fast-growing hierarchy depends on the fundamental sequences for limit ordinals in the domain. It is probably true for some family of fundamental sequences, since there are so many possibilities. Whether or not the statement is true for a particular family of fundamental sequences, like the one I described above, seems like a difficult problem.

$\endgroup$
  • $\begingroup$ Well, thank you very very much, gonna need some time to take it in though. $\endgroup$ – TStancek Aug 4 '17 at 7:54
  • $\begingroup$ So if I understand that correctly, we do not know how to (and possibly even can't) define a fundamental sequence that would stretch across the whole fast growing hierarchy. Or am I still missing something? $\endgroup$ – TStancek Sep 6 '17 at 7:03
  • $\begingroup$ Define a specific family of fundamental sequences is hardly a problem. You can easily do it with ${\mathcal O}$ for $\omega{_C}{_K}$, for example. Generally speaking, of course one can do it for any countable ordinal $\alpha$ almost by definition (since $\alpha$ has well-ordering on $\mathbb{N}$ with order-type $\alpha$). You can use a very simple algorithm-like procedure that uses the well-order relation to obtain a family of sequences right up till $\alpha$ (including $\alpha$ itself). $\endgroup$ – SSequence Sep 6 '17 at 7:30
  • $\begingroup$ @SSequence next time please use the @ username in the beggining of your comment, otherwise I will not get the notification. I do not know how to correctly express my understanding of this, but the fast growing hierarchy starts at +1 function and then uses iteration. Then uses diagonalisation to get $\omega$. Then creates a set of fundamental sequences for $\omega 2$, $\omega 3$ etc. and creates a new sequence from starts of these sequences. And generalizes this again and again. Basically what I meant in my comment is that we are unable to write down a total generalization of this process. $\endgroup$ – TStancek Sep 6 '17 at 10:37
  • $\begingroup$ @TStancek "Then uses diagonalisation to get $\omega$. Then creates a set of fundamental sequences for $\omega.2$, $\omega.3$ etc. and creates a new sequence from starts of these sequences. And generalizes this again and again." Even though I have very little familiarity with specifics of FGH, that doesn't seem quite right. And I think your confusion may be here. $\endgroup$ – SSequence Sep 6 '17 at 10:54

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.