4
$\begingroup$

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

$\endgroup$
0

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • $\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
    Commented May 4, 2021 at 19:39

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