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

One Answer

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

Add your own answers!

Ask a Question

Get help from others!

© 2024 All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP