# How to compare three supremums of ordinals eventually writable by Ordinal Turing Machines?

This question implies that we have fixed: (i) a particular enumeration of Ordinal Turing machines; (ii) a particular way to encode an ordinal by an infinite binary sequence.

The class of $$[1]$$-machines is defined as the $$1$$st iteration of the strong jump operator for Ordinal Turing Machines. That is, a machine is equipped with an oracle able to answer any question of the following form (note that $$[0]$$-machines are Ordinal Turing Machines with no oracles):

Does an $$i$$-th $$[0]$$-machine halt given an infinite binary sequence $$x$$ as the input?

The ordinal $$\alpha_1$$ is defined as the supremum of ordinals eventually writable by $$[1]$$-machines with empty input.

Let $$m_i(x)$$ denote a computation performed by an $$i$$-th $$[0]$$-machine, assuming that the input is $$x$$. If $$m_i(x)$$ eventually writes a countable ordinal $$\alpha$$, then $$M_i(x) = \alpha$$. Otherwise, $$M_i(x) = 0$$.

Then the function $$F(i)$$ is defined as follows: if the value of $$\sup \{M_i(x) | x \in \mathbb{R}\}$$ is a countable ordinal, then $$F(i) = \sup \{M_i(x) | x \in \mathbb{R}\};$$ otherwise, $$F(i) = 0$$. Here “$$x \in \mathbb{R}$$” implies that we take into account all infinite binary sequences.

The ordinal $$\alpha_2$$ is defined as follows: $$\alpha_2 = \sup \{F(i) | i \in \mathbb{N}\}.$$.

The ordinal $$\eta$$ is defined as the least ordinal $$\gamma$$ such that $$L_\gamma$$ and $$L$$ have the same $$\Sigma_2$$-theory (see part 3 of Lemma 3.11 in the paper “Recognizable sets and Woodin cardinals: Computation beyond the constructible universe”). As far as I understand, $$\eta$$ is equal to the supremum of ordinals eventually writable by Ordinal Turing Machines ($$[0]$$-machines) with empty input.

Question: which ordinal is larger, $$\alpha_1$$ or $$\alpha_2$$? Is any of these two ordinals larger than $$\eta$$?

This is a rather incomplete answer because it doesn't address the harder part for the first half of question. (I hope it doesn't discourage any expert to answer the question in a more complete and techincal way.)

I have assumed that when you talk about infinite binary sequence $$x$$, you are talking about an $$\omega$$ length sequence of bits. I will assume V=L in the first half (as I find it an easier setting to work with). This is a bit tentative, but I have the feeling that $$\alpha_1=\eta$$. I probably need to double check the working desribed below.

It doesn't seem to me (at first look) that we could have $$\alpha_1>\eta$$. Note that $$\alpha_1 \geq \eta$$ trivially as $$[0]$$-machines are just weaker versions of $$[1]$$-machine any way. Now if we suppose that $$\alpha_1>\eta$$. Then there exists a $$[1]$$-machine program (say $$Q$$) which will be able to eventually point to an ordinal $$\beta \geq \eta$$. The main thing is that can we somehow "approximate" (using the word very loosely here) the working of the given $$[1]$$-machine program $$Q$$ within an ordinary OTM to be able to eventually write the ordinal $$\beta$$. If we can then we have shown that $$\alpha_1=\eta$$.

So now, we first use an OTM ($$[0]$$-machine) program $$P1$$ to mark the ordinal $$\omega_1$$. We want to build an OTM program $$P$$ which eventually writes $$\beta$$ by "approximating" the working of $$Q$$. The point is to look at time time $$\geq \omega_1$$. At this time $$P1$$ is correctly marking $$\omega_1$$.

Each time within the approximation of working of $$Q$$ (the $$[1]$$-machine program eventually writing $$\beta \geq \eta$$), when $$Q$$ seeks to use its oracle power, we can determine the answer by checking whether for the given OTM and given real no. (over which oracle was used) there is a halting till some point below $$\omega_1$$ or not. This way we will have the correct answer for everytime when the oracle was used.

One note that should be mentioned here. It is true that when $$P_1$$ hasn't correctly marked $$\omega_1$$ (and is at a countable ordinal) then the answers to oracle questions (of $$Q$$) will be wrong in our program $$P$$. However, the answer to all these questions will definitely be guaranteed to "become" correct once $$P_1$$ has marked $$\omega_1$$.

Regarding your second question about $$\alpha_2$$, it seems that we should have $$\alpha_2>\eta$$. And I think that this should be true regardless of whether V=L or not.

To see this, first let $$E \subset \mathbb{N}$$ denote the set of all $$[0]$$-machine programs which (on empty input) eventually write some ordinal $$x<\omega^L_1$$. We have a natural number $$n \not \in E$$ iff the corresponding program doesn't stabilize with a code of some ordinal (in the designated $$\omega$$ length section of its tape). Note that since the ordinal $$x$$ is written via a sequence of $$\omega$$ bits, so it can't encode a well-order relation (on $$\mathbb{N}$$) with order-type $$\geq \omega^L_1$$.

Our goal is to build a program with index $$e \in \mathbb{N}$$ such that $$F(e)=\eta+1$$ (the function $$F$$ is defined in the question) hence showing $$\alpha_2 > \eta$$. It is easy to see if we divide into cases. Imagine each real number given as input (to $$\phi_e$$) as a set $$A \subseteq \mathbb{N}$$ where a natural number $$n \in A$$ iff the $$n$$-th bit of the input real number is 1. We divide into following three cases and look at them one by one: $$(1)$$ $$A=E$$ $$(2)$$ $$A \subset E$$ $$(3)$$ $$A \not \subseteq E$$.

For any time $$t$$, our program $$\phi_e$$ just looks at the designated $$\omega$$ length sections of all programs $$\phi_i$$ (with $$i \in A$$) at this particular time $$t$$. Now for possibility-$$(1)$$, our program $$\phi_e$$ stabilizes with the eventual stabilized output giving the code for ordinal $$\eta+1$$. For $$(2)$$, our program $$\phi_e$$ stabilizes with the eventual stabilized output giving the code for some ordinal $$\leq \eta+1$$.

For $$(3)$$, either our program stabilizes while eventually writing some value $$\leq \eta+1$$ or it doesn't stabilize at all. This is due to the following additional possibility: "There will be unboundedly large times (within $$\mathrm{Ord}$$) where there is some program $$\phi_i$$ (with $$i \in A$$) whose designated $$\omega$$ length section doesn't contain a code of any ordinal." This shouldn't affect us because we can pretend that the given tape is writing the ordinal $$0$$ currently (when it doesn't contain a code for any ordinal).

Note that if we denote the $$r \in \mathbb{R}$$ as the real number corresponding to set $$A$$, then in possibility-(1) we have $$M_e(r)=\eta+1$$. In possibility-(2) we have $$M_e(r) \leq \eta+1$$. And in possibility-(3) we have $$M_e(r) \leq \eta+1$$. This guarantees that $$\sup \{M_e(x) | x \in \mathbb{R}\}$$ will be countable.

• It should be mentioned that I do not know whether the equality $\alpha_1=\eta$ remains valid or not in the case of $V \neq L$. It does seem that $\alpha_1=\eta$ in-case of $V=L$. – SSequence May 4 at 19:39