In this question, the notation $P^x(\alpha)$ denotes a situation where a particular [OTM-program](https://arxiv.org/abs/math/0502264) $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$?



How large is the smallest ordinal larger than any “minimal ordinal parameter” for any pair of an Ordinal Turing Machine and a real?
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 *Turing Computations on Ordinals*, 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.


