## FANDOM

10,825 Pages

Some of you might remember my other blog post in which I investigated functions which were sitting in the gap between class of computable functions and a representative function above this class, namely the busy beaver function. Conclusion was that, in a very specific sense, there exist functions in these gaps.

Later I was wondering if we can make similar constructions between other classes of functions. My initial idea was the gap between functions provably total in PA (or, Hardy's hierarchy below $$\varepsilon_0$$) and $$H_{\varepsilon_0}$$. $$H_{\varepsilon_0}$$ is a very natural function to choose to cap the hierarchy, so it might be a bit surprising to find functions between them. Of course, function like $$H_{\varepsilon_0}(n)-1$$ is something trivial we wouldn't want to bother about. We want to put quite strong condition on how much below $$H_{\varepsilon_0}$$ our function of interest should be. An idea is this: if we have function $$F$$, then we build recursive hierarchy $$F_\alpha,\alpha<\varepsilon_0$$, and we want every function of this hierarchy to still be dominated by $$H_{\varepsilon_0}$$. We also want $$F$$ to dominate all of $$H_\alpha,\alpha<\varepsilon_0$$.

These are quite strong conditions, which seem unlikely to be possible to be fulfilled. As turned out, thanks to personal communication with Andreas Weiermann, such function $$F$$ actually can exist! I don't think there is a direct reference where such is constructed, but here you can see him confirming this fact, and pointing to a paper where results of similar sorts are shown.

Going few levels lower, we can ask similar question about recursion not up to $$\varepsilon_0$$, but just up to $$\omega^\omega$$ (in which case it is strength-wise equivalent to primitive recursion). In this case, I was able to find a solid reference: in this paper it is shown that we can create a dense chain of primitive recursive degrees, which (in particular) implies that we can find such intermediate functions (in fact infinitely many) between $$f_n$$ and $$f_\omega$$. By adapting similar methods, I believe we can find uncountably many different functions with pairwaise different strengths (again, in some specific meaning), and I wouldn't be surprised at all if it could be used to find many functions between $$H_\alpha$$ and $$H_{\varepsilon_0}$$.