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

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

• So your question is what is the least non-OTM-computable with a real parameter, am I correct? – Hanul Jeon Sep 19 '20 at 8:12
• @HanulJeon I didn't understand the question. Regarding what you wrote (just to be sure) did you mean: "what is the least non-OTM-computable ordinal with any arbitrary real parameter allowed"? Admittedly, I don't understand the second part of your answer though (w.r.t. upper-bound). For V=L, my personal reasoning goes as follows: Given any arbitrary ordinal parameters less than a countable $\alpha$ the sup of values clocked (with parameters $< \alpha$) can be shown to be countable. And hence the upper-bound follows (because any real can be computed with some countable ordinal parameter). – SSequence Sep 19 '20 at 10:48
• @SSequence: "I didn't understand the question" — can you please specify which part of the question is unclear? – lyrically wicked Sep 19 '20 at 11:07
• @SSequence: "You could just have $\omega$ as a parameter and a certain machine would halt regardless of what real input was placed on it" — yes, of course, a particular program $P_1$ will halt. But a particular program $P_2$ will not (with the same input.) I have emphasized that we take into account all programs, all inputs and all ordinal parameters (assuming that the parameter is minimal, as is written in the question). – lyrically wicked Sep 19 '20 at 11:44
• @SSequence: [1/2]: yes, of course, but these facts do not affect the definition of $\beta$ at all. Consider the following game. I pick an arbitrary ordinal $\tau_0$. You pick an arbitrary OTM $P$ and an arbitrary real $x$, then write $x$ on the cells indexed by finite ordinals. – lyrically wicked Sep 19 '20 at 12:13

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 $$x\in 2^\mathbb{N}$$ (also called a real, which is standard terminology in set theory) and an ordinal $$\alpha$$. Consider the set $$H = \{\alpha\mid \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 $$x\in 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:M\to 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.

• [1/2]: I am not sure what you mean by "real parameter $x$" and why you wrote "$x$ codes a well-order" and "$P$ halts with an input $\alpha_0$", so in order to avoid ambiguity, I have to clarify that $x$ is not a parameter, $x$ is an input: it is an arbitrary real (the word "real" here implies an infinite binary sequence) written on all cells indexed by natural numbers. Note that since $x$ is arbitrary, it is not required to code a well-order. – lyrically wicked Sep 19 '20 at 10:31
• [2/2]: Then $\alpha_0$ is not an input, it is always the smallest ordinal greater than or equal to $\omega$ such that a program $P$ halts given $x$ as the input and a single "1" written on the $\alpha_0$-th cell of the tape. Do these clarifications affect the answer? – lyrically wicked Sep 19 '20 at 10:32
• @lyricallywicked The second half of your question is difficult to understand. You don't seem to specify any relation between $\alpha$ and $\beta$ in your possibilities-(1),(2) in the second half of your question. The answer given is for the following question: "what is the least ordinal not reachable by any OTM (with no ordinal parameters and any arbitrary real input allowed)". – SSequence Sep 19 '20 at 10:59
• @SSequence: [1/2] "You don't seem to specify any relation between $\alpha$ and $\beta$ in your possibilities-(1),(2)" — why? I have provided the full definition. If there exists at least one ordinal parameter such that an arbitrary OTM halts with $\alpha$ as the parameter and $x$ as the input, then there is the smallest such parameter, denoted by $\alpha_0$. Then $\beta$ is the smallest ordinal greater than any $\alpha_0$ under the assumption that $x$ is an arbitrary real. – lyrically wicked Sep 19 '20 at 11:21
• @SSequence: [2/2] Regarding [The answer given is for the following question: "what is the least ordinal not reachable by any OTM (with no ordinal parameters and any arbitrary real input allowed)"] — if this is so, then no, this is not what this question is about. Definition of $\beta$ is not related to being (non-)reachable, (non-)computable or (non-)writable. It is related to ordinal parameters. Note that ordinal parameters for OTMs may be uncountable (for example, $0^{\sharp}$ is recognizable from $\omega_1$, if $0^{\sharp}$ exists, but it is not recognizable from any countable ordinal.) – lyrically wicked Sep 19 '20 at 11:27