Skip to main content
5 of 10
added 44 characters in body
SSequence
  • 881
  • 1
  • 5
  • 10

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 or halt immediately (both choices would seem to work OK).

(2) Suppose conversely that we have $\tau \geq \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.

SSequence
  • 881
  • 1
  • 5
  • 10