1
$\begingroup$

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

$\endgroup$
11
  • $\begingroup$ So your question is what is the least non-OTM-computable with a real parameter, am I correct? $\endgroup$
    – Hanul Jeon
    Sep 19 '20 at 8:12
  • $\begingroup$ @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). $\endgroup$
    – SSequence
    Sep 19 '20 at 10:48
  • $\begingroup$ @SSequence: "I didn't understand the question" — can you please specify which part of the question is unclear? $\endgroup$ Sep 19 '20 at 11:07
  • $\begingroup$ @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). $\endgroup$ Sep 19 '20 at 11:44
  • $\begingroup$ @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. $\endgroup$ Sep 19 '20 at 12:13
3
$\begingroup$

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.

$\endgroup$
12
  • $\begingroup$ [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. $\endgroup$ Sep 19 '20 at 10:31
  • $\begingroup$ [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? $\endgroup$ Sep 19 '20 at 10:32
  • $\begingroup$ @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)". $\endgroup$
    – SSequence
    Sep 19 '20 at 10:59
  • $\begingroup$ @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. $\endgroup$ Sep 19 '20 at 11:21
  • $\begingroup$ @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.) $\endgroup$ Sep 19 '20 at 11:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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