How large is the supremum of halting times of Infinite Time Turing Machines, assuming that halting times are bounded and inputs are arbitrary?

Question

Given a fixed enumeration of Infinite Time Turing Machines (ITTMs), let $M_i(x)$ denote a computation of an $i$-th ITTM, assuming that the input $x$ is a real (an infinite binary sequence).

Then the function $f(i)$ (input: natural number, output: countable ordinal) is defined as follows:

1. if $M_i(x)$ does not halt for any real $x$, then $f(i) = 0$;
2. if there exists the largest countable ordinal $\alpha$ such that there exists a real $x$ such that $M_i(x)$ halts at time $\alpha$ (and there does not exist a real $y \neq x$ such that $M_i(y)$ halts at time $\beta > \alpha$), then $f(i) = \alpha$;
3. if both (1) and (2) are false (that is, if for any countable ordinal $\alpha$ there exists a real $x$ such that $M_i(x)$ halts at time $\beta > \alpha$), then $f(i) = 0$.

The ordinal $\tau$ is defined as the supremum of the infinite set $\{f(0), f(1), f(2), \ldots \}$. Question: how large is $\tau$? In particular, what is $\tau$ in comparison with the least $\Sigma_1$-stable ordinal (mentioned in the Definition 3.1 in the paper “Recognizable sets and Woodin cardinals: Computation beyond the constructible universe”)?

Answer 1

I will assume V=L for simplicity. Let $C$ denote the supremum of halting times for powerful enough (ordinal) programs (such as OTMs) on empty input and no parameters etc. Also, let $\eta$ be the ordinal mentioned in "definition-3.10 (ii)" in the linked paper. Let $\eta_0$ be the supremum of eventually writeables (e.g. for OTMs) that stabilize in countable time. Observe that $\eta_0<\eta$.

As I understand, the following two inequalities (as rough upper and lower bounds) can be shown without too much difficulty: (1) $\tau>C$ (2) $\tau \leq \eta_0$.

(1) For this I think we need to observe that a given well-order relation (on $\mathbb{N}$) for a sufficiently large (countable) ordinal $\alpha$, an ITTM can essentially simulate any OTM (roughly until $\alpha$).

So now let $A \subset \mathbb{N}$ be the index of all OTMs that halt on empty input. So any OTM whose index doesn't belong to $A$ will run forever (on empty input). Let $r_1$ be a real number which encodes $A$. Also, let $\alpha$ be any countable ordinal which is sufficiently greater than $C$. Now consider a real number $r_2$ which encodes any linear-order on $\mathbb{N}$ such that the ordinal corresponding to its initial well-founded segment is $\alpha$.

Once $r_1$ and $r_2$ are given in suitably encoded form as a single real number, we can show that we can halt at $C$, no matter what value $\alpha$ (as long as $\alpha>C$). First establish that $r_2$ is a linear-order on $\mathbb{N}$. Now the point is to use $r_2$ to simulate all OTM programs (on empty input), while also keeping a set $X_n \subset \mathbb{N}$ that changes with the (ordinal) stage number $n$ (which starts from $0$ and only ever increases in increments of $1$). We have initially $X_0=A$. At whatever stage $n$ an OTM program halts on empty input, we remove the index of that program from $X_n$ (it isn't difficult to define $X_n$ a bit more rigorously). Note that $X_m \subseteq X_n$ for all ordinals $m>n$.

So what we have to do is just keep a look for the stage number $N$ at which $X_N=\phi$. Note that we should have $N=C$. At that point we halt (and basically ignore the remaining initial well-founded segment of $r_2$). If $r_2$ represents a linear-order (on $\mathbb{N}$) and we run-out of the initial well-founded segment earlier than $C$ then it isn't a problem. We can just make our program run forever in that case.

To put it succinctly, for part-(1), if we think of $r_1$ as encoding a set $B \subseteq N$ (general case), then it seems that we can divide into following sub-cases: (i) $B \subset A$ (ii) $B=A$ (iii) $B \not \subseteq A$

(2) Suppose conversely that we have $\tau > \eta_0$. Then that means that there is a specific ITTM program with index $e \in \mathbb{N}$ such that when we define $\beta=\sup\{H_e(r)|r\in \mathbb{R}\}$, we get $\beta \geq \eta_0$ and $\beta<\omega_1$. Now the point is that we want to build an OTM program (or similar) which simulates this ITTM program with index $e$ for arbitrary real numbers.

So initially set a variable $v:=0$. The point now is to first simulate some OTM which systematically lists all constructible reals. At the same time the reals are being listed we simulate (using dovetailing etc.) each of these reals on the ITTM program with index $e$. Every time a halting on some given real number occurs, read the time/step at which the halting happens in the simulation (let's denote this time/step by $T$). If the current value of our variable $v$ is less than $T$ then increase it to $T$ and otherwise ignore and don't change the value of $v$.

It is reasonably clear that the value of $v$ won't ever increase to $\geq \eta_0$. But given how our program operates the final value of $v$ must be equal to $\beta$. Hence we have to conclude that our initial assumption $\beta \geq \eta_0$ was incorrect.

---

EDIT NOTE: After some thinking (prompted by @DmytroTaranovsky's comment and answer) I thought some more about this. I think I understand why $\tau <\eta_0$ is not possible (note that I am assuming V=L).

I decided to make the edit (after some deliberation). The reason I was hesitant was that it might just be quite similar to the other answer (which I don't understand) in less technical language. But I guess that perhaps, in that case, there might be some exposition value to it (e.g. for someone, like myself, much less knowledgeable about the topic).

(3) We want to show that $\tau<\eta_0$ is impossible. Let's assume it was true.

Consider any arbitrary ordinal $x<\eta_0$. We can show that there exists a program (no parameters, input etc.) such that it has a non-decreasing variable $v$ with initially $v:=0$ and the "final" value of $v$ is $<\eta_0$ and $\geq x$ (after reaching this final value the value of variable $v$ never changes). Further this final value of $v$ will be achieved at some time strictly below $\eta_0$.

So again consider two real numbers $r_1$, $r_2$ which encode any linear-order on $\mathbb{N}$ such that the ordinal corresponding to their initial well-founded segment are of length $\alpha_1$, $\alpha_2$ respectively (also we intend $\alpha_1<\alpha_2$ under normal input). Now let $e \in \mathbb{N}$ be the index of an OTM program (or similar) such that the final value of the variable $v$ (mentioned in previous paragraph) is both countable and $\geq \tau$. Let's call this final value $\beta$ (we have $\tau \leq \beta < \eta_0$).

Once again, suppose we are given $r_1$ and $r_2$ encoded as single real number $r$. Now build an ITTM program which, loosely speaking, does the following (the whole simulation the follows can be carried using $r_2$). If it turns out the $\alpha_1 \geq \alpha_2$, then run forever. If $\alpha_1<\alpha_2$, then find the (ordinal) length of the initial well-founded segment of the linear-order given by $r_1$ (essentially figure out $\alpha_1$). Now simulate the OTM program with index $e$ (till time/step $\alpha_2$) and keep a check on the variable $v$. If the value of $v$ does become $\geq \alpha_1$ then halt in that case (this is the only halting condition). And if the value of $v$ stays strictly below $\alpha_1$ till the exhaustion of initial well-founded segment of $r_2$, then go into a loop.

The point of the last paragraph is that whenever we have $\alpha_2$ as sufficiently large (basically $\geq \eta_0$ is enough) and $\tau \leq \alpha_1 \leq \beta$, our ITTM program will halt at a time above $\tau$. However, whenever we have $\alpha_2$ as sufficiently large and $\alpha_1>\beta$ our program loops forever. Finally, note that if the definitions for $f$ and $\tau$ in the OP were for OTMs (instead of ITTMs) then the construction just mentioned would be much simplified (because then we can ignore $r_2$, $\alpha_2$ etc.).

Answer 2

The ordinal is the supremum of the ordinals in the $Σ_2$ hull of $L_{ω_1}$. It is robust to the choice of the computational model as long as (uniformly in $x$) the halting problem is $Π^1_1(x)$-hard and $Σ^1_2(x)$, with commensurate halting times. ITRM, ITTM, and OTM are examples of such models.

For the lower bound, given a $Σ_2$ statement $φ$, halt (in time $≥δ$) iff real $x$ encodes $L_δ$ with $L_δ⊨¬φ$ (note that $δ<ω_1$ but not necessarily $<\!ω_1^L$). If ordinal $α$ is the least witness for $φ^{L_{ω_1}}$, then $∀δ<α \, (L_δ ≺_{Σ_1} L_{ω_1} ⇒ ¬φ^{L_δ}$), but $∀δ \, (α<δ<ω_1) \, φ^{L_δ}$. (Also, $δ$ with $L_δ ≺_{Σ_1} L_{ω_1}$ are unbounded in $ω_1$ and hence unbounded in the $Σ_2$ hull.)

For the matching upper bound, we use generic collapses and $Σ^1_2$ absoluteness. The halting time is bounded below $ω_1$ iff $∃α<ω_1 ∀β \, ∀γ \, (\max(α,β)<γ<ω_1 ∧ L_γ⊨\text{ZFC\P}) \; L_γ[\mathrm{Col}(ω,β)] ⊨$ “the halting time must be $<α$”, which is $Σ_2^{L_{ω_1}}$. $L_γ[\mathrm{Col}(ω,β)]$ is $Π^1_1$-correct, so it cannot falsely see a machine halt. Conversely, existence of a machine with halting time $β$ is $Σ^1_2(y)$ for every real $y$ encoding $β$, so $L[\mathrm{Col}(ω,β)]$ (and large enough $L_γ[\mathrm{Col}(ω,β)]$ as above) is correct about its existence.

Answer 3

This and related questions about decision times of ITTMs are addressed in this paper:

"Decision times of infinite computations" https://arxiv.org/abs/2011.04942

The ordinal you are asking for seems to be the supremum of the semi-decision times, which can be characterized in a number of ways.