How large is the smallest ordinal larger than any “minimal ordinal parameter” for any pair of an Ordinal Turing Machine and a real?

MathOverflow Asked by lyrically wicked on December 4, 2020

In this question, the notation $$P^x(alpha)$$ denotes a situation where a particular OTM-program $$P$$ performs a computation on input $$x$$ with an ordinal parameter $$alpha$$, assuming that $$x$$ is written on the initial segment of length $$omega$$ (the smallest limit ordinal) of the tape of $$P$$ at time $$0$$. That is, $$x$$ is the input for $$P$$ written in cells indexed by finite ordinals $$(0, 1, 2, ldots)$$ before the start of computation, yet all cells indexed by all ordinals greater than or equal to $$omega$$ are initially blank, except one cell indexed by $$alpha$$ (this cell is marked by a non-zero symbol.)

Let $$beta$$ denote the smallest ordinal such that for any pair of an OTM-program $$P$$ and a real $$x$$ (that is, $$P$$ quantifies over all programs and $$x$$ quantifies over all reals) exactly one of the following statements is true:

1. There does not exist an (uncountable or countable) ordinal $$alpha$$ such that $$P^x(alpha)$$ halts;

2. If there exists at least one (uncountable or countable) ordinal $$alpha$$ such that $$P^x(alpha)$$ halts, then, assuming that $$alpha_0$$ is the smallest such ordinal, $$alpha_0 < beta.$$

How large is $$beta$$?

Since there is disputation on how to interpret the problem, I think it would be better to clarify my interpretation:

Let $$P(x,alpha)$$ be a program, which takes a binary sequence $$xin 2^mathbb{N}$$ (also called a real, which is standard terminology in set theory) and an ordinal $$alpha$$. Consider the set $$H = {alphamid text{alpha is the least ordinal such that P(x,alpha) halts for some x, P} }.$$ Then $$H$$ is a set. What is the value of $$sup H$$?

If I understand your problem correctly, then the answer is $$omega_1$$. Please feel free to comment if there is an error in my proof.

For the lower bound, we will find an OTM-program with a parameter $$xin 2^mathbb{N}$$ that computes a countable ordinal. Assume that $$x$$ codes a well-order over $$omega$$ whose order-type is $$alpha$$. Consider the following procedure: decode $$x$$ and enumerate ordinals less than the order-type of $$x$$ by brute force. (This is possible since there are only countably many members in $$x$$ and we have infinite time.) In this way, we can compute $$alpha$$ from $$x$$. Now take $$P(beta)$$ as follows: if $$beta=alpha$$, it halts. If not, it does not halt.

For the upper bound, assume that we have a program $$P$$ of real parameter $$x$$. By Lemma 2.6 of Koepke's Ordinal Computability, the ordinal computation by $$P$$ is absolute between $$V$$ and $$L[x]$$. Assume that $$P$$ halts with an input $$alpha_0$$, and $$alpha_0$$ is the smallest such an ordinal. Moreover assume that we take time $$theta$$ to compute $$P(alpha_0)$$.

Now consider the Skolem hull $$M$$ of sufficiently large $$L_gamma[x]$$ generated by $${theta,alpha_0,x}$$. By condensation, there is an isomorphism $$pi:Mto L_beta[x]$$ for some countable $$beta$$. Then $$L_beta[x]$$ thinks $$P$$ halts with an input $$pi(alpha_0)$$ and does not halt if we plug in ordinals smaller than $$pi(alpha_0)$$. By $$pi(alpha_0)le alpha_0$$, Lemma 2.6 of Koepke and minimality of $$alpha_0$$, we have $$pi(alpha_0)=alpha_0$$. Hence $$alpha_0$$ is countable.

Correct answer by Hanul Jeon on December 4, 2020