Kleene's $O$ is a way to use natural numbers as notations for recursive ordinals. I’m wondering what happens if you modify the definition of Kleene’s $O$ to allow for arithmetical truth as an oracle. Let $T$ be the set of Godel numbers of true statements in the language of first-order arithmetic. Let $0$ be a notation for $0$, and if $i$ is a notation for $\alpha$, then $2^i$ is a notation for $\alpha+1$. If $\phi_e^T$ (the $e^{th}$ partial recursive function with access to $T$ as an oracle) is a total $T$-recursive function enumerating ordinal notations in strictly increasing order (as ordinals), then let $3\cdot 5^e$ be a notation for the least upper bound of the ordinals denoted by the range of $\phi_e$. Let $O_T$ be the set of all ordinal notations obtained in this way.
My question is, what is the smallest ordinal that does not have a notation in $O_T$? I realize that ordinal might be difficult to describe exactly, but can we at least put some upper and lower bounds on how big it is?
It's a theorem of Spector that every hyperarithmetic ordinal is computable (see Sacks' book). True (first-order) arithmetic is tiny in the hyperarithmetic hierarchy, so it doesn't get us any further than $\omega_1^{CK}$.
(Incidentally, it's also true that every computable ordinal is polynomial-time computable, so $\omega_1^{CK}$ is the first non-polytime-computable ordinal and the first non-hyperarithmetic ordinal. It's a really robust notion!)
Note that as usual, it's far simpler to talk about computable ordinals than notations. There are situations where notations are useful, but in my experience more as a tool than the initial definition.