2

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).

SSequence
  • 861
  • @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). – SSequence Mar 03 '19 at 02:22
  • (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. – Noah Schweber Mar 04 '19 at 16:25
  • 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). – Noah Schweber Mar 04 '19 at 16:27
  • @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$. – SSequence Mar 04 '19 at 17:10
  • @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. – SSequence Mar 05 '19 at 10:34
  • @NoahSchweber I have edited the question to make my point clearer. – SSequence Mar 10 '19 at 11:27
  • You still seem to have $p$ defined as the least thing not computable as opposed to the supremum of the computable things ("Then define $p$ as the smallest (limit) point that such programs can't reach. "), which leaves it the case that $p<\theta$ (indeed $p<\omega_1$) trivially (unless I'm wildly misunderstanding ORMs). I think it would be best to write an "edits-free" version of the question - that is, just one which asks what you want to ask right now, even minimizing motivation. Interested readers can look at the edit history for more data; at present I'm a little lost in the question. – Noah Schweber Mar 10 '19 at 22:18
  • @NoahSchweber I will try to go through your points in an ordered way. Quite simply, I just defined $p$ as the supremum of clockable values (when you give ORMs an additional command of addition by $\omega_1$ ...... this computational model is what I called $C_2$). Meaning we are just interested in the halting positions, when no input is given. Yes, you are right I was careless in writing "smallest point not reachable" (what I meant was "smallest point one can't go beyond"), since that point would just occur at a very small point (the beginning of first gap) .... – SSequence Mar 11 '19 at 04:39
  • I "assumed" it would be obvious that supremum was under discussion. My apology for that. With this out of the way, my question simply was about the comparison between the values $p$ and $\theta$. But you are right ..... my question right now is a bit different. I will just state it here: Whether we assume $p<\theta$ or $p>\theta$, in either case there must exist a value $\beta<\theta$ such that for all $t$ (where $\beta<t<\theta$) there is no program which "clocks"(halts on empty input) at time $t$. My question is can one give an explicit upper bound for this value $\beta$? – SSequence Mar 11 '19 at 04:39

1 Answers1

0

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.

SSequence
  • 861
  • Is checking whether an ordinal is admissible doable? (I'm not really familiar with ORMs.) – Noah Schweber Jan 02 '20 at 18:17
  • 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. – SSequence Jan 02 '20 at 18:43
  • 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. – SSequence May 31 '20 at 11:59