2
$\begingroup$

This was posted as a side question in Formal definition of this ordinal? and was split as a separate question based upon suggestion in comments there.

Assume an ordinary ORM model (call it $C_1$). Suppose we add an extra instruction of the form to $u:=u+\omega_1$ (where $u$ is a variable) to the definition of an ordinal register style program (and one or two more basic commands in case they are necessary). Or just consider an OTM with a single parameter $\omega_1$ given to it. Call this model $C_2$. Then define $p$ as the supremum of halting times of these programs (no input). Now as the answer linked below uses $\theta$ to denote $\omega_{\omega_1+1}^{CK}$, I will use the same symbol for uniformity.

Which of the following possibilities can actually occur: (a) $p < \theta$ (b) $p = \theta$ (c) $p > \theta$.

Now given the discussion in comments, assuming the answer given in the linked topic to be correct, it is clear that the possibility (b) above is ruled out. But what about the other two possibilities. Another thing is confinality difference. Consider the possibility $p>\theta$. For that to be true, not only would it have to be true that there exists a program (in model $C_2$) which halts beyond $\theta$ on empty input. But it would also have to be true that there exists some value $\beta<\theta$ such that for all $t$ (where $\beta<t<\theta$) there exists no program which halts at time $t$ on empty input (if this weren't true $cf(\theta)$ would be countable).

Is there a nice/easy way to visualize $\beta$?

The ordinal $q$ was also defined in the previous version of question as follows: One could also consider well-orders of $\omega_1$ that these programs can calculate. For example, say $q$ is the least upper bound of all the ordinals $x$ such that: "there is some program (from model $C_2$) that computes a well-order relation ($\omega_1^2$ to $\{0,1\}$) describing well-order of/on $\omega_1$ with order-type $x$".

One can also ask about the relation of $q$ with $p$,$\theta$ (certainly it seems to me that $p \geq q$ should be true).

Improve this question
$\endgroup$
9
  • $\begingroup$ @NoahSchweber I have a very short question. What is the cofinality of $\omega_{\omega_1+1}^{CK}$? Is it countable or not? The reason for asking (as is probably obvious) is simply that $p$ should have countable cofinality (as I understand). $\endgroup$
    – SSequence
    Commented Mar 3, 2019 at 2:22
  • $\begingroup$ (FYI I can't be pinged if I'm not in the comment thread already.) Yes, $cf(p)=\omega$ since there are only $\omega$-many programs to consider. By contrast (and per my answer to your recent MSE question), $cf(\omega_{\omega_1+1}^{CK})=\omega_1$. So we do indeed have $p\not=\omega_{\omega_1+1}^{CK}$. As to which is bigger, I'm not certain - I'm not familiar with ORMs - but I tentatively disagree with your guess, at least the rationale for it: well-foundedness becomes quite simple at sufficiently closed ordinals, so things are a bit dubious to me. $\endgroup$
    – Noah Schweber
    Commented Mar 4, 2019 at 16:25
  • $\begingroup$ Incidentally, your connection between trees and orderings is quite correct. We can computably associate a tree $T$ to a linear order $S$ such that we can uniformly compute $(i)$ a descending sequence in $S$ given an infinite path through $T$ and $(ii)$ an infinite path through $T$ given an infinite descending sequence in $S$. And you essentially have the construction (search for the term "Kleene-Brouwer ordering" - strictly speaking this describes the reverse situation, but it still gives the key ideas). $\endgroup$
    – Noah Schweber
    Commented Mar 4, 2019 at 16:27
  • $\begingroup$ @NoahSchweber So you can't ping someone who isn't in a thread already? Hmm OK. Anyway, I will update/edit the question tomorrow probably. The comment about "trees" was bit of side-remark (though it is nice to know it can be made to work). I couldn't get that method to work fully ....... so I thought of another method later on (which I am reasonably confident works). Anyway, I will make an edit tomorrow probably ....... Also explaining why I am quite puzzled (perhaps temporarily till someone explains properly?) by $p \neq \theta$. $\endgroup$
    – SSequence
    Commented Mar 4, 2019 at 17:10
  • $\begingroup$ @NoahSchweber I assume when you say: "but I tentatively disagree with your guess, at least the rationale for it", I think you are probably referring to when I wrote $p \geq \theta$ as a possibility. Honestly, I was thinking of $p=\theta$ at that point really, so that particular remark wouldn't quite hold after your answer. $\endgroup$
    – SSequence
    Commented Mar 5, 2019 at 10:34

1 Answer 1

Reset to default
0
$\begingroup$

It seems that the relation between $p$ and $\theta$ should be fairly simple (with $p>\theta$). Because we are talking about sufficiently general programs, $p$ is just the supremum of clocking times given a single parameter $\omega_1$.

To observe why $p>\theta$ is true, we can do the following. First set a counter variable $n$ to $\omega_1+1$. Now just check for the admissibility of $n$. If the check returns false then just increase the value of $n$ by $1$ and check again. The smallest point at which this check will return true will be $\theta$.

Another thing is that if we define $q(\omega_1)$ same as $q$ but by limiting run-times to $\omega_1$, then we have: $q(\omega_1)< \beta < \theta<p$. We can observe that $q(\omega_1)<\theta$ because $q(\omega_1) \leq |\, \omega_1-\mathrm{computable} \,|\,\,$ by its definition. And, since $\omega_1$ is a bad ordinal, we further have $|\, \omega_1-\mathrm{computable} \,|<\theta\,\,$ giving us $q(\omega_1)<\theta$.

The relation of $q$ to the other ordinals isn't clear to me though.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Is checking whether an ordinal is admissible doable? (I'm not really familiar with ORMs.) $\endgroup$
    – Noah Schweber
    Commented Jan 2, 2020 at 18:17
  • $\begingroup$ As far as I understand things, yes. Mainly because given an $\alpha \in Ord$ we can try all possible combinations of (finite) parameters $< \alpha$. That would be using the co-finality based definition. That is, given an ordinal $\alpha$ we could write a total predicate $checkAdmissible:Ord \rightarrow \{0,1\}$ such that $checkAdmissible(\alpha)$ returns true iff $\alpha$ is admissible. Also, the question has an easy equivalent formulation in terms of OTMs too (which I have also mentioned in text of question after edit). Just have $\omega_1$ number of $1$'s on the tape initially. $\endgroup$
    – SSequence
    Commented Jan 2, 2020 at 18:43
  • $\begingroup$ Not sure why this question keeps getting bumped (somewhat unnecessarily, since the answer to primary question seems reasonably clear to me). I guess perhaps I should accept my own answer ...... I didn't accept it initially because I thought someone would point out if I was completely mistaken about something basic. $\endgroup$
    – SSequence
    Commented May 31, 2020 at 11:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .