For countless months (but countable, there's about 15 of them) we all have been considering higher order busy beaver functions \(\Sigma_k(n)\) to be on par with FGH extended, in some uniform way no one ever cared about, to admissible ordinal \(\omega^\text{CK}_k\). I believe I have actually been the first of us who started stating that. Argument I gave was that with halting oracle we can compute ordinal \(\omega^\text{CK}_1\), by trying out all machines, checking if they code ordinals and then adding up all the ordinals, and then we can sort of recurse through this ordinal and reach anywhere below \(\omega^\text{CK}_2\) (for higher orders it's just induction).
However, some time ago, somewhere on this wiki, I was told by Deedlit that checking if machine computes ordinal is actually a hard problem. A really hard problem. To be exact how hard it is, it's \(\Pi^1_1\)-complete problem, so it's at least as hard as any other \(\Pi^1_1\) problem, so it's far more complicated than any hyperarithmetical or arithmetical problem, including halting problem for many oracles. This means that it cannot be solved on halting oracle TM.
After a lot of time to rethink this, I came to a conclusion that it's actually impossible to, using any reasonable oracle machine, to compute CK ordinal, by following argument - we all know Kleene's O. Kleene's O can be interpreted as tree of height \(\omega^\text{CK}_1\), so we probably can, given some way of working with \(\omega^\text{CK}_1\), decide if number is part of Kleene's O, which is again \(\Pi^1_1\)-complete problem, so that's impossible.
I'm still not sure about this, but if my rethought intuition is correct, not even \(\Sigma_k(n)\) reaches \(f_{\omega^\text{CK}_1}(n)\). I wanted to ask you guys for your thoughts after reading this wall of text. LittlePeng9 (talk) 20:58, July 6, 2014 (UTC)
- Oh, and one more thing - hyperarithmetical sets are equivalent to oracle hierarchy iterated transfinitely \(\omega^\text{CK}_1\) times, so this might be an argument against strength of \(\Sigma_k(n)\) too. LittlePeng9 (talk) 21:00, July 6, 2014 (UTC)
- If you claim that \(\Sigma_k(n)\) doesn't reach \(f_{omega^\text{CK}_1}(n)\), you claim that \(\Sigma(n)\) doesn't reach \(f_{omega^\text{CK}_1}(n)\). The problem is that you now claim that \(\Sigma(n)\) is upper bounded by some recursive ordinal. Wythagoras (talk) 06:04, July 7, 2014 (UTC)
- No, I now claim that \(\Sigma(n\) is strictly above all \(f_\alpha(n)\) for \(\alpha\) revursive, but still below \(f_\text{CK}(n)\). FGH nor even HH or SGH doesn't exhaust all possible growth rates. For example, where in SGH would you put \(n\log n\)? It's significantly slower than \(g_{\omega^2}(n)=n^2\) but still outgrows every linear function \(kn=g_{\omega k}(n)\). So there are functions which fit inbetween SGH. So let me repeat: I claim similar happens for \(\Sigma(n)\) and \(\omega_1^\text{CK}\). LittlePeng9 (talk) 06:16, July 7, 2014 (UTC)
- A similiar thing happens for the Goodstein function? Wythagoras (talk) 06:47, July 7, 2014 (UTC)
- As far as I know, Goodstein's function is unarguably at level of \(\varepsilon_0\). LittlePeng9 (talk) 07:06, July 7, 2014 (UTC)
- Just realized this depends on definition of rate of growth, but my point still holds. LittlePeng9 (talk) 07:52, July 7, 2014 (UTC)
- Peng, . Hardy hierarchy has the relationship with FGH as , not turning s to n's freely. Ikosarakt1 (talk ^ contribs) 19:47, July 7, 2014 (UTC)
- I meant SGH there. My bad! LittlePeng9 (talk) 19:59, July 7, 2014 (UTC)
- A similiar thing happens for the Goodstein function? Wythagoras (talk) 06:47, July 7, 2014 (UTC)
- No, I now claim that \(\Sigma(n\) is strictly above all \(f_\alpha(n)\) for \(\alpha\) revursive, but still below \(f_\text{CK}(n)\). FGH nor even HH or SGH doesn't exhaust all possible growth rates. For example, where in SGH would you put \(n\log n\)? It's significantly slower than \(g_{\omega^2}(n)=n^2\) but still outgrows every linear function \(kn=g_{\omega k}(n)\). So there are functions which fit inbetween SGH. So let me repeat: I claim similar happens for \(\Sigma(n)\) and \(\omega_1^\text{CK}\). LittlePeng9 (talk) 06:16, July 7, 2014 (UTC)
- If you claim that \(\Sigma_k(n)\) doesn't reach \(f_{omega^\text{CK}_1}(n)\), you claim that \(\Sigma(n)\) doesn't reach \(f_{omega^\text{CK}_1}(n)\). The problem is that you now claim that \(\Sigma(n)\) is upper bounded by some recursive ordinal. Wythagoras (talk) 06:04, July 7, 2014 (UTC)
- I believe \(\Sigma(n)\) grows at least as fast as \(f_{\omega^\text{CK}_1}(n)\). I'm assuming that the fundamental sequence of \(\omega^\text{CK}_1\) is the largest ordinal representable by a Turing machine using \(n\) states or less, or something similar to that. In that case, we can define the FGH up to \(\omega^\text{CK}_1 [n]\) using something comparable to \(n\) states. (certainly less than \(n^2\), I would think) So we will have \(\Sigma(n^2) > f_{\omega^\text{CK}_1}(n)\). Deedlit11 (talk) 18:38, July 7, 2014 (UTC)
- I'd rather assume fundamental sequences from Kleene's O: \(\alpha[n]=\sup\{\mathcal{O}(m):m\leq n\}\). I don't really know why, but I prefer that definition. LittlePeng9 (talk) 18:50, July 7, 2014 (UTC)
- Okay, that's fine. That will make \(\omega^\text{CK}_1 [n]\) even slower growing, as you will need the notations to go to at least \(3 \cdot 5^{(4n+4)^{2n}}\) before we reach Turing machines with more than \(n\) states. Deedlit11 (talk) 19:12, July 7, 2014 (UTC)
- But for Kleene's O it might happen that a machine with index, say, 100, will compute some specific set of number indices which will further represent in O ordinals with upper bound being some enormous ordinal \(\alpha\), so \(\mathcal{O}(100)=\alpha\), while TMs with up to \(3\cdot 5^{100}\) states will not be able to define well-ordering with that order type (this is what I assume your definition used). Hence it isn't that obvious for me that your definition of FS is any stronger than mine. (my use of number 100 is huge underestimate for usual TM orderings, but the point might hold if we replace it with, say, \(10^{100}\) anyway. It's unlikely, but not impossible) LittlePeng9 (talk) 19:22, July 7, 2014 (UTC)
- Hmm, I see what you are saying. So we don't have a proof that \(\Sigma(n)\) grows as fast as \(f_{\omega^\text{CK}_1}(n)\). Your conjecture clashes with my intuition, though - \(f_{\omega^\text{CK}_1}(n)\) resolves immediately to recursive functions, so for it to vastly outgrow \(\Sigma(n)\) would require a ridiculously fast growing fundamental sequence. Your fundamental sequence doesn't seem all that fast growing to me. Deedlit11 (talk) 19:40, July 7, 2014 (UTC)
- I'd rather assume fundamental sequences from Kleene's O: \(\alpha[n]=\sup\{\mathcal{O}(m):m\leq n\}\). I don't really know why, but I prefer that definition. LittlePeng9 (talk) 18:50, July 7, 2014 (UTC)
- Well, the FGH certainly depends on fundamental sequences or norms or some sort of choice that we have to keep making as we get to higher and higher ordinals, I don't see a way around that. It would be great if we could define a canonical choice of fundamental sequences, or at least some notion of "natural" fundamental sequences - this has been an open problem for proof theory for quite some time, and no one has come up with a good solution, and I think the consensus is that there isn't any. Now for \(f_{\omega^\text{CK}_1}(n)\) we would like some notion of "first" nonrecursive function, but that doesn't seem to have a canonical definition either. Deedlit11 (talk) 00:55, July 8, 2014 (UTC)