4
$\begingroup$

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”)?

$\endgroup$
7
  • 1
    $\begingroup$ It should be greater than $\sigma$ (the least $\Sigma_1$-stable ordinal). You can make a machine that, given a linear order $\alpha$ and a set $X \subseteq \omega$, simulates each OTM in $X$ along the well-founded part of $\alpha$ sequentially, entering an infinite loop if any run beyond the well-founded part. Then its runtime is maximized by giving it $\alpha = \sigma$ and $X$ halting OTMs with runtimes cofinal in $\sigma$. $\endgroup$ – Dan Turetsky Apr 8 at 5:40
  • $\begingroup$ @DanTuretsky At least under V=L [adding it to be on the safe side as my knowledge of sets is really lacking], upon a quick look it seems that for the ordinal mentioned as $\tau$ should be $\leq \eta$ (supremum of eventually writeables for OTMs). I haven't written it and just thought it mentally though, so I need to re-check it a bit. Also, I am a bit uncertain about the intention of the question. $\endgroup$ – SSequence Apr 8 at 10:01
  • $\begingroup$ @lyricallywicked I have the feeling that this is what you intend? You want to define a function $f:\mathbb{N} \rightarrow \omega_1$ with the following definition for $f(i)$. For a given $i \in \mathbb{N}$, denoting $\alpha_i=\sup\{H_i(x)\,|\,x \in \mathbb{R}\}$, you want to define $f(i)=0$ if $\alpha_i \geq \omega_1$ and $f(i)=\alpha_i$ if $\alpha_i<\omega_1$. The symbol $H_i(x)$ gives the halting time for an ITTM of index $i$ with an input real $x$ (and $0$ if the given ITTM never halts). Is this what you intend in your question? $\endgroup$ – SSequence Apr 8 at 10:08
  • $\begingroup$ With regards to second last comment, it seems that a stronger uppper-bound on $\tau$ could be inferred with $\tau \leq \eta_0$ (again taking V=L to be safe). Here $\eta_0$ is the supremum of eventually writeables (e.g. for OTMs) that stabilize in countable time. But two things are: (i) It depends on the interpretation of question being as in last comment (ii) It is just an upper-bound on $\tau$ and not a lower-bound. $\endgroup$ – SSequence Apr 8 at 10:56
  • $\begingroup$ @SSequence: it seems that your interpretation of the definition of $f$ is correct. Question: does "the supremum of eventually writeables" in the comment above matches the ordinal mentioned in Lemma 3.11 (3) in the linked paper? $\endgroup$ – lyrically wicked Apr 8 at 13:46
3
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ $H_e(r)$ is the halting time of ITTM of index $e$ when given a real $r$. If the ITTM runs forever on some given real $a$, then $H_e(a)=0$. $\endgroup$ – SSequence Apr 8 at 17:37
  • $\begingroup$ Regarding (posting in comment to avoid too many edits): "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)." I think I glossed this over in the initial reply, halting may not be a good idea. We would probably always want to loop forever when we run out of the initial well-founded segment of $r_2$. That would be to account for the case when $r_1$ encodes a strict super-set of $A$. $\endgroup$ – SSequence Apr 9 at 2:47
  • $\begingroup$ To put it succinctly, for part-(1), if we think of $r_1$ as encoding a set $B \subseteq \mathbb{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$. $\endgroup$ – SSequence Apr 10 at 8:28
  • 2
    $\begingroup$ Your upper bound is actually the exact answer, even if $V≠L$ (see my answer; also, note that $η_0=η$ if $0^\#$ exists). $\endgroup$ – Dmytro Taranovsky Apr 11 at 21:39
  • $\begingroup$ @DmytroTaranovsky Thanks, that's good to know. Actually, I was wondering about this part (and it didn't seem unreasonable that this ordinal $\tau$ in OP might just equal $\eta_0$). One other interesting thing is that while the original question defined the function $f$ and the corresponding ordinal $\tau$ w.r.t. ITTMs, $\eta_0$ still seemed to be upper-bound w.r.t. more general models such as OTMs. (it seems you have mentioned something similar in the first paragraph of your answer, but that's just guess on my part. Perhaps you might have meant something else) $\endgroup$ – SSequence Apr 12 at 3:12
2
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.