Skip to main content
9 of 10
added 29 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.

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 \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.


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) So let's suppose that $\tau \geq \eta_0$ was false. That means $\tau<\eta_0$. Now take 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 $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$.

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.).

SSequence
  • 881
  • 1
  • 5
  • 10