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$?


1 Answer 1


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.

  • $\begingroup$ 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$. $\endgroup$
    – SSequence
    May 4, 2021 at 19:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.