I’m struggling with a certain connection the author draws in defining a certain “huge” number. The number is defined as follows:
Let T be the first-order theory of Zermelo-Fraenkel set theory plus the Axiom of Choice plus the axiom that there exists an I0 rank-into-rank cardinal.
Starting with P = 10:
- Search through all Turing machines with at most P states.
- Search through all proofs in T of length at most 2^^P that the program halts.
- Run all programs such that a halting proof exists, until they halt.
- Add up all the running times of all those programs.
- Set P to this sum.
- Repeat 10 times.
This is claimed to be the biggest “kind” of number we could theoretically compute. I’m not sure I understand enough to say whether this is true, but the definition seems quite straightforward to me. However the author also then says:
“The end result should be roughly equal to the fast-growing hierarchy at the proof-theoretic ordinal of T, plus 1, applied to 10“
I don’t get this part. My understanding was that a theory’s proof-theoretic ordinal corresponded to the fastest-growing function in a fast-growing hierarchy which the theory could prove total - I’m not seeing the connection between the two at all, why would the above function behave like the fast-growing hierarchy at this particular ordinal?
Not sure if this is me missing a deep intuitive connection/a lot of the argument has been hand-waved over/the author is confused, but I’d really appreciate some insight
Note that the $f_{PTO(T)}$ isn't a priori related to the functions $T$ proves total, as it isn't even defined without a system of fundamental sequences. However, it is generally believed that with respect to a 'natural' system of fundamental sequences (otherwise one could do some ridiculous system like "$\omega[n]=BB(n)$", with the busy beaver function) and 'natural' theories $T$ (otherwise, for a natural system of fundamental sequences and theory $T$, one can just add an axiom "$f_{PTO(T)+1}$ is total" without affecting the proof-theoretic ordinal), $f_{PTO(T)}$ is the first function in the fast-growing hierarchy that $T$ does not prove total.
Now let's consider how each execution of the loop affects $P$. the Turing machines that are run compute the functions $T$ proves total. To analyse how this affects $P$, we can conjecture that using $PTO(T)[n]=\sup \{\alpha:T\text{ proves }f_\alpha\text{ total with a proof of length at most }2\uparrow\uparrow n\}$ (note that this is a fundamental sequence by the first paragraph, the only question is how 'natural' it is). Then the execution times for the programs will be roughly around $f_{PTO(T)[P]}(P)$, and so it will map $P$ to $f_{PTO(T)[P]}(P)=f_{PTO(T)}(P)$. This means that after running the loop 10 times starting with $P=10$, the final value is roughly $f^{10}_{PTO(T)}(10)=f_{PTO(T)+1}(10)$.