5
$\begingroup$

$\mathcal{O}$ notation describes an onto function $f:\mathcal{O} \rightarrow \omega_{CK}$. In calculating all values $n \in \mathbb{N}$ such that $f(n)=\alpha$, when $\alpha$ is a limit, all indexes $e$ of ordinary programs are considered such that $\phi_e(i)=n_i$ (with $i \in \mathbb{N}$). The values $n_i$ must satisfy the condition that $f(n_i)=\alpha_i$ with the $\alpha_i$'s forming a (fundamental) sequence for $\alpha$.

I am just interested in the variation where we don't consider indexes of normal programs but instead consider indexes of primitive recursive functions/programs (given a suitable indexing for them).

(Q1) How far would such a variation go? That is, what is the smallest ordinal it can't represent.

(Q2) Consider the notation system (described by a 1-1 function $g:\beta \rightarrow \mathbb{N}$) assigning a unique number to each ordinal in which on limit values $\alpha<\beta$ we seek the p.r. function with smallest index $e$ satisfying $\phi_e(i)=g(\alpha_i)$ where the $\alpha_i$'s must form a (fundamental) sequence for $\alpha$.

At what value $\beta$ would such a system stop?

I don't have proficiency with the underlying theory so if the question seems posed in a strange manner then that might be the reason.

$\endgroup$
  • 3
    $\begingroup$ If I recall correctly, every computable ordinal is an order type of a primitive recursive well-order. So the primitive recursive variant also goes all the way up to $\omega_1^{CK}$. $\endgroup$ – Wojowu Mar 2 at 9:44
  • 3
    $\begingroup$ Indeed, since we can always kill time by enumerating successors while we wait for a given recursive function to converge. $\endgroup$ – Dan Turetsky Mar 2 at 13:03
  • $\begingroup$ @DanTuretsky I have a small additional question. Would the system such as one in (Q2) also go to $\omega_{CK}$ [both for p.r. and ordinary programs]? $\endgroup$ – SSequence Mar 2 at 13:16
  • 1
    $\begingroup$ @Wojowu In fact, we can bring this down to polynomial-time computability (or indeed even less!) - $\omega_1^{CK}$ is unspeakably robust. $\endgroup$ – Noah Schweber Mar 2 at 18:26
5
$\begingroup$

For Q2, the answer is $\omega^2$, for both recursive and primitive recursive notations. It's not hard to see that every ordinal below $\omega^2$ can be reached.

To show that $\omega^2$ cannot be reached, the argument is the same for both primitive recursive and full recursive. For each $a$, we construct a $b$ ensuring that $a$ is not a notation of this sort for $\omega^2$. We will construct $b$ knowing its own index. For recursive notations, this is an application of the recursion theorem. For p.r. notations, even though we don't have the recursion theorem, this is still possible so long as we're willing to specify an a priori p.r. bound on the runtime. Since we intend to kill time by enumerating successors, an exponential bound will be fine.

Our first goal is to arrange that $b$ codes $\gamma+\omega$, where $\gamma$ is greatest such that some $c < b$ with $c <_\mathcal{O} a$ codes $\gamma$. So we unwrap the notation $a$ while enumerating successors. As soon as we see some $c < b$ with $c <_{\mathcal O} a$ and $|c|$ larger than any of the others yet seen, a c.e. event, we include $c$ in the sequence we're enumerating.

As soon as we see $b <_\mathcal{O} a$, we do something to ensure that $b$ is not a valid notation, e.g. break the monotonicity of our sequence.

If $a$ is a notation for $\omega^2$ with $b \not <_\mathcal{O} a$, then $\gamma+\omega < |a|$, and $b$ is the least notation for $\gamma+\omega$ (for any smaller notation would be included in the definition of $\gamma$, contradicting our choice of $\gamma$). So if $a$ is a notation of the desired sort for $\omega^2$, then $b <_\mathcal{O} a$. But then $b$ is not a notation, by construction, so $a$ is not a notation.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Very nice answer! I have to admit though that I am finding it quite difficult to understand the details in your answer due to my lack of understanding. But anyway, the answer to question is still quite useful/informative regardless. [and sry if you have flood of notifications ..... the 5 min. edit time-limit is difficult for me to manage] $\endgroup$ – SSequence Mar 4 at 18:22

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.