3
$\begingroup$

Does there exist a computable function that grows faster than fast growing hierarchy for every computable ordinal $\alpha$? Or does it follow that fast growing hierarchy grows as fast as any computable function? I honestly can't figure out how to even understand how I could tackle such problems, and indeed I am fairly new to all this. A quick definition of fast growing hierarchy for those who don't know:

$$f_\alpha(n)=\begin{cases}n+1&;\alpha=0\\\underbrace{f_{\alpha-1}(f_{\alpha-1}(\dots f_{\alpha-1}(n)\dots))}_{{n\text{ amount of }f's}}&;\alpha\text{ is a successor ordinal}\\f_{\alpha[n]}{n}&;\alpha\text{ is a limit ordinal}\end{cases}$$

where $n\in\mathbb N$ and $\alpha$ is some computable ordinal.

I imagine this is very hard to proof one way or the other, since the fast growing hierarchy can outgrow things like the TREE sequence, which are not provably total... so I honestly have no clue.

The most I can say is that FGH itself is computable.

$\endgroup$
  • $\begingroup$ I don't understand your definition of "reducible" - do you just mean "computable"? $\endgroup$ – Noah Schweber Mar 8 '17 at 21:09
  • $\begingroup$ @NoahSchweber Sorry, I didn't know that was the right term. $\endgroup$ – Simply Beautiful Art Mar 8 '17 at 21:09
  • $\begingroup$ I'm not sure it is, I was asking you. I suspect that's what you mean, though. $\endgroup$ – Noah Schweber Mar 8 '17 at 21:16
  • $\begingroup$ @NoahSchweber Yes, it is what I meant (the existence of uncomputable ordinals occured to me only yesterday, so I couldn't quite remember what it was) $\endgroup$ – Simply Beautiful Art Mar 8 '17 at 21:17
7
$\begingroup$

It's important to note that "$f_\alpha$" isn't really well-defined - if we pick different fundamental sequences, we get different functions.

Really, what you have when you get down to it is a function $f_n$ for each ordinal notation: for a given notation $n$ for a limit ordinal, there's a natural fundamental sequence associated to it, since we can enumerate the notations which are $<_\mathcal{O}n$. But different notations for the same ordinal may be incomparable in $\mathcal{O}$ (essentially: we can't tell in general whether two "computable descriptions" describe the same ordinal), and the associated functions can be wildly different.

It's not necessarily worth digging too deeply into the precise definition of $\mathcal{O}$; it's enough to think of it as a set of indices for computable ordinals which is "reasonably nice", and that will give you the right intuition. The specific definition is extremely useful for proving theorems, but those theorems only show up a ways down the road. For now, for example, we could just work for indices of Turing machines which happen to describe ordinals.

Now, usually we get around this by developing the fast-growing hierarchy below some specific "natural" notation for some fixed ordinal - e.g., the Lob-Wainer hierarchy works below a reasonable notation for $\epsilon_0$ - and in this case, Stella Biderman's answer is correct, that for any fixed ordinal notation we can of course diagonalize away from it. However, if you want to consider the fully general fast-growing hierarchy defined on all of $\mathcal{O}$, then it turns out that there is no escape! In fact, for any computable function $g$, I can come up with an ordinal notation $n_g$ for $\omega^2$ such that $f_{n_g}$ grows faster than $g$ (and such an $n_g$ can be computably gotten from (an index for) $g$!).

(This phenomenon - that $\omega^2$ is already enough - happens with annoying frequency when playing around with $\mathcal{O}$. Once we get to large enough (really, very small!) ordinals, there are "sufficiently weird" notations that do whatever you want. For instance, the Ershov hierarchy (link to be added once I find it :P) for sets computable from the Halting Problem has to be defined in terms of notations, since in terms of ordinals it collapses quite quickly.)

$\endgroup$
  • $\begingroup$ So if I choose my fundamental sequences so that we may remove the first two paragraphs of concern, it appears to me that it necessarily follows that there exists computable ordinals $\alpha$ for every $g(n)$ such that $f_\alpha(n)\gg g(n)$? $\endgroup$ – Simply Beautiful Art Mar 8 '17 at 21:23
  • 2
    $\begingroup$ @SimplyBeautifulArt Not necessarily - there are "bad" paths through $\mathcal{O}$ which will give you terrible fast-growing hierarchies. But we can find a (really complicated, sadly) path through $\mathcal{O}$ whose associated fast-growing hierarchy does eventually dominate every computable function. $\endgroup$ – Noah Schweber Mar 8 '17 at 21:24
  • $\begingroup$ Wow, that is quite impressive. Is there a formal sort of proof you could give me? (whenever you have time?) $\endgroup$ – Simply Beautiful Art Mar 8 '17 at 21:26
  • 1
    $\begingroup$ @SimplyBeautifulArt I'm not aware of any written proof of this fact, but it's not too hard. It's an exercise in Sacks' book that there are maximal chains in $\mathcal{O}$ of length $\omega^2$ (that is, really short!); they sort of "shoot off to the side" instead of going up the way we expect them to. This is easy to prove: list the notations for $\omega^2+1$, and at stage $n$ (when you get to choose a notation for $\omega n$) "veer away from" the $n$th such notation. (Note that this path is non-computable, of course.) (cont'd) $\endgroup$ – Noah Schweber Mar 8 '17 at 22:06
  • 1
    $\begingroup$ Now this construction can easily be tweaked to stay below a sufficiently fast-growing computable function; just pick your notation for $\omega n$ mentioned above to also not grow too fast. In fact, I'm pretty sure $f_{\omega^2+1}$ in the usual Lob-Wainer hierarchy is fast enough! $\endgroup$ – Noah Schweber Mar 8 '17 at 22:07

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.