# 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

## Related Questions

### Rings whose Frobenius is flat

0  Asked on December 30, 2020 by anon1432

### $ell^1$-norm of eigenvectors of Erdős-Renyi Graphs

1  Asked on December 30, 2020 by stefan-steinerberger

### The problems of global asymptotic freeness

1  Asked on December 29, 2020 by iliyo

### What OEIS sequence is this?

1  Asked on December 29, 2020 by a-z

### Reference for the rectifiablity of the boundary hypersurface of convex open set

1  Asked on December 28, 2020

### Tannakian group of Galois representations coming from geometry

0  Asked on December 27, 2020 by smn

### Why there is no 3-category or tricategory of bicategories?

1  Asked on December 27, 2020 by lolman

### Analytically controlling sizes in modular arithmetic to demonstrate Dirichlet pigeonhole application

1  Asked on December 27, 2020

### “Weakly” nuclear operators (terminology)

0  Asked on December 26, 2020 by pea

### holomorphy in infinite dimensions (holomorphic families of operators)

2  Asked on December 26, 2020 by andr-henriques

### Max weighted matching where edge weight depends on the matching

2  Asked on December 25, 2020

### Faltings’ height theorem for isogenies over finite fields

0  Asked on December 21, 2020 by asvin

### Probability of positivity of rational solutions to a diophantine system?

0  Asked on December 21, 2020 by vs

### On sup over boundaries of Sobolev functions

0  Asked on December 20, 2020 by yongmin-park

### On weaker forms of the abc conjecture from the theory of Hölder and logarithmic means

1  Asked on December 18, 2020 by user142929

### Set of points with a unique closest point in a compact set

2  Asked on December 18, 2020 by piotr-hajlasz

### Complex $2$ manifold $M$ with a given real 2 dimensional submanifold which meets all complex limit cycles of foliations of $M$

0  Asked on December 17, 2020 by ali-taghavi

### Rigorous multivariate differentiation of integral with moving boundaries (Leibniz integral rule)

1  Asked on December 17, 2020 by amir-sagiv

### Closed form of the sum $sum_{rge2}frac{zeta(r)}{r^2}$

0  Asked on December 15, 2020 by epic_math