Characterisations of variant transfinite computational models: Infinite time Turing,ordinal time Turing,and Blum–Shub–Smale machines

Theorem 2.1.

(i) Suppose we consider multiple head ITTMs. (a) Let α be Π 3 -reflecting. Then α is not ITTM-clockable.

(b) The least Π 3 -reflecting α 0 starts the first gap in such clockables. In general, if α is not Π 3 -reflecting, then α does not start a gap; hence for such α, if it is a limit of clockables, it is itself clockable.

(ii) The same holds true for OTMs if again we allow multiple heads and tapes.

Proof.

(i)(a) We assume initially that there are just three tapes as on an ITTM, which have zeros written everywhere. Assume for a contradiction that P e ( 0 ) ↓ α . In an enumeration ⟨ C n k ⟩ n of the cells let C n k ( η ) = j indicate that the n’th cell of tape k, at time η has contents j < 2 for k < 3 , where k = 0 , 1 , 2 representing the Scratch, Output, and Input tapes respectively. Let R 0 ( τ ) , R 1 ( τ ) ,be respectively, the position of two R/W heads on the Input/Scratch and Output Tapes respectively (we might easily imagine a third head R 2 , and thus in effect we set R 0 ( τ ) = R 2 ( τ ) for any τ); let I ( τ ) be the current instruction or state number ( < ω ) at time τ for P e , for τ ⩽ α . We note that for τ < α that R k , I are Σ 1 L α -definable functions of τ. We shall assume that at limit times λ, a head returns to the Liminf of its positions on its tape if this is finite, otherwise the head returns to 0 the starting position. Mathematically put: at time λ, R k ( λ ) = Liminf β ⟶ λ ∗ R k ( β ) for k < 3 , where we define Liminf β → λ ∗ R k ( β ) = Liminf β → λ R k ( β ) if the latter is less than ω, otherwise set this to 0.

Now abbreviate r k = R k ( α ) for k = 0 , 1 (and set also r 2 = r 0 whenever it appears as r k for k = 2 ). By our assumption, the machine halts because of a particular configuration under the R/W heads C r k k ( α ) , the reason being that it is in a particular state I ( α ) whilst reading precisely those cells. By simple Π 2 reflection at the admissible α, I ( β ) = I ( α ) for an unbounded (indeed closed) set C of ordinals below α.

Case 0 Both r 0 , r 1 > 0 .

Then again by an additional Π 2 -reflection clause there is an unbounded set D 0 ⊆ C of ordinals γ below α where r k = R k ( γ ) for both k < 2 simultaneously. Note further that “ C r k k ( α ) = j k < 2 , for k < 3 ” is expressible as a Boolean combination of Σ 2 and Π 2 sentences. (For example, either j k = 1 , and then C r k k ( τ ) = 1 if it is 1 for all sufficiently large τ < α , or else it is 0, which happens by Liminf rules if we had that for all τ 0 < α , there is a τ > τ 0 with C r k k ( τ ) = 0 . So this is Σ 2 ∨ Π 2 .) We thus have some unbounded D ⊆ D 0 where these facts reflect to γ ∈ D . But then for such γ the conditions on I ( γ ) , C r k k ( γ ) were all there to halt exactly as at stage α. A contradiction.

Case 1 Just one of r k = 0 .

Suppose w.l.o.g. this is r 0 . Then there is an unbounded D ⊆ C of ordinals γ where r 1 = R 1 ( γ ) and C r 1 1 ( γ ) = 1 , just as in Case 0.

Case 1a) Liminf β → α R 0 ( β ) = ω .

Then ∀ z < ω ∃ τ z ∀ τ ∈ ( τ z , α ) ( R 0 ( τ ) > z ) . However this is a Π 3 -sentence and we may reflect this down, simultaneously with the above Σ 2 ∨ Π 2 -statements about r 1 , to some γ ∈ D . But again this yields the conditions for halting at a stage γ < α as R 0 ( γ ) = 0 = r 0  – a contradiction.

Case 1b) Liminf β → α R 0 ( β ) = 0 .

Then ∀ τ 0 ∃ τ ∈ ( τ 0 , α ) R 0 ( τ ) = 0 . This is Π 2 , so again can be reflected to some γ ∈ D as in Case 1a), reproducing the halting conditions at time γ. Again a contradiction.

Case 2 Both r k = 0 .

Then the argument is just a mixture of those of the previous Case, depending on the reason for each r k to be 0. We leave this as an exercise to the reader. This ends the proof of Thm 2.1 (i)(a). □

To continue we shall need a special case of the following Lemma.

Lemma 2.2.

Let β > ω be such that L β is not Π 3 -reflecting, is not a model of Σ 1 -Separation, but is an admissible model of “ V = HC ”. Then there is a ( Π 2 ∧ Σ 2 ) L β ( { p } ) function G : ω ⟶ β which is cofinal, where p = p β 1 is the standard parameter of L β , but so that for any β ′ < β with p = p β ′ , 1 G L β ′ is not a total function.

Proof.

Let ≺ − , − ≻ : ω × ω ⟶ ω be a bijective recursive pairing function. Our assumptions imply that h β 1 “ ω × ( ω ∪ { p } ) = L β . (Here h = h β 1 is the standard – and uniformly defined – Σ 1 -skolem function for all limit L β ). Suppose φ [ x ] ≡ ∀ u ∃ v ∀ w ψ ( u , v , w , x ) for some x ∈ L β is a non-reflecting Π 3 -formula, chosen so that L β ⊧ φ [ x ] . This is equivalent to: ( + ) ∀ ≺ n , i ≻ < ω ∃ α [ h ( i , n , p ) ↑ ∨ ∃ v ∈ L α ∀ w ψ ( h ( i , n , p ) , v , w , x ) ]

holding in L β . Let G ( ≺ n , i ≻ ) = the least α such that ∃ v ∈ L α ∀ w ψ ( h ( i , n , p ) , v , w , x ) , if h ( i , n , p ) ↓ = 0 , if h ( i , n , p ) ↑ . Then G is ( Π 2 ∧ Σ 2 ) L β { p }  – the ‘leastness of α’ requirement contributing a Π 2 L β clause: ∀ α ′ < α ∀ v ∈ L α ′ ¬ ∀ w ψ ( ( h ( i , n , p ) , v , w , x ) ) . We claim that for any limit β ′ < β with x ∈ L β ′ , and p = p β ′ 1 (and there are unboundedly many such β ′ below β), that G L β ′ is not a total function. Our assumptions show that again h β ′ 1 “ ω × ( ω ∪ { p } ) = L β ′ (although for those h β 1 ( i , n , p ) ∈ L β ∖ L β ′ we shall have h β ′ 1 ( i , n , p ) ↑ ). So were G L β ′ total, we should have that ( φ [ x ] ) L β ′ which is impossible. □

Now for limit β ′ ⩽ β let n ( β ′ ) = df maximal n ′ ⩽ ω s.t. L β ′ ⊧ “ ∀ ≺ n ¯ , i ≻ ⩽ n ′ ( ≺ n ¯ , i ≻ ∈ dom ( G ) ) ”. Then for appropriate β ′ < β we must have n ( β ′ ) < ω , whilst n ( β ) = ω .

Lemma 2.3.

Liminf β ′ → β n ( β ′ ) = ω , and G ( ≺ n ¯ , i ≻ ) L β ′ ⟶ G ( ≺ n ¯ , i ≻ ) L β .

Proof.

As β ′ → β the value of G ( ≺ n ¯ , i ≻ ) L β ′ eventually settles to the final value G ( ≺ n ¯ , i ≻ ) L β . To see this note that for a given β ′ < β the fact that ∀ v ∈ L β ′ ¬ ∀ w ψ ( h ( i , n , p ) , v , w , x ) L β is a Σ 1 { p , x } L β fact by admissibility of β, and so if true in L β will also be true in sufficiently large β ″ < β . Hence larger and larger initial portions of the domain of G become correctly calculated as β ′ increases. □

Lemma 2.4.

Suppose that ω < β is not Π 3 -reflecting and is a supremum of halting times of 2-head ITTM computations on integer input. Then β itself is such a halting time; it thus does not start a gap in such ITTM clockables.

Proof.

We in essence run the “Theory Machine” that computes successively the constructible levels of the L τ hierarchy, for τ < β < Σ ; by time β this machine has written (and overwritten) codes successively for all the L τ . We assume that β is admissible, since if not then we already know that β is clockable, as only admissibles start gaps even for single head machines (see [32], Thm. 50). Let x ∈ L β and φ [ x ] ≡ ∀ u ∃ v ∀ w ψ ( u , v , w , x ) . We assume φ [ x ] fails to be true in any L τ for τ < β but is true in L β . Let G : ω ⟶ L β be a cofinal, Π 2 ∧ Σ 2 L β function defined as above (parameter free), which arises from the fact that L β ⊧ “ V = HC ” and is not a model of Σ 1 -Sep. (This latter requirement and the parameter free-ness of the definition follows from β being a supremum of halting times.) We may thus assume without loss of generality that x ⊆ ω .

Now consider the amendment to the Theory Machine that is also recording on a separate tape T 1 with its own R/W head (this can be the Output Tape of the Theory Machine, ⟨ C n 1 ⟩ n , and we can arrange that this tape is otherwise not used by the Theory Machine) an initial sequence of: the first cell C 0 1 which is kept at 0, then in the next n ( β ′ ) + 1 cells 1’s are written with the head R 1 resting on the largest cell with a 1 after this write, namely C n ( β ′ ) + 1 1 , and thereafter by 0’s, to indicate, that at the current stage β ′ ⩽ β , n ( β ′ ) is our maximal n ⩽ ω as defined above. The value of n ( β ′ ) of course being found from inspection of the Σ 2 -theory of L β ′ that the TM provides.

Then β ′ ↣ n ( β ′ ) is a, not necessarily monotone, function into ω, but with Liminf β ′ → β n ( β ′ ) = ω (see Lemma 2.3). Thus at time β the R/W head of the tape T 1 , having been sent out to ω, is returned to its 0’th cell C 0 1 : R 1 ( β ) = 0 . Thus the head is reading a 0, and this is the first time this happens at any stage β ′ > 0 . So we can program a halt at this stage. This ends the proof of Lemma 2.4 & Thm. 2.1(i)(b). □

Proof of Theorem 2.1(ii)(a).

We adapt the above arguments for when we have an OTM with multiple heads, let us take three independent heads on three tapes, with the same notations of R k ( τ ) ∈ On , C δ k ( τ ) < 2 (now for the δ’th cell of tape T k = df ⟨ C δ k ⟩ δ ∈ On ) for k < 3 and I ( τ ) as before.

(a) We assume that α is Π 3 -reflecting, and show that it is not OTM-clockable under this regime. So assume for a contradiction that P e ( 0 ) ↓ α . Now the R/W heads can be at various combinations of positions once more. Let r k = R k ( α ) for k < 3 . We consider the case that r 1 ∈ Lim and that r 0 , r 2 are successor ordinals. This is the simplest but paradigm case: with r 0 , r 2 successor ordinals, there is by Π 2 -reflection as above a cub C ⊆ α where the heads on these two tapes T 0 , T 2 are at the same position (thus R k ( τ ) = r k for k = 0 , 2 ), and the instruction number I ( τ ) is the same, for any τ ∈ C . We then just concentrate on r 1 ∈ Lim . Let us further abbreviate r 1 as ρ.

As ρ > 0 there is some τ 0 < α so that for no later stage τ ⩾ τ 0 can we have R 1 ( τ ) ∈ Lim and R 1 ( τ + 1 ) < R 1 ( τ ) (“no further going left at limit cells”).

Case 1 ∃ τ 0 < α ∀ τ ∈ ( τ 0 , α ) R 1 ( τ ) < ρ .

If ρ < α then we can assume that ρ < τ 0 . In any case, by definition ρ = Liminf τ → α R 1 ( τ ) , so we have that ρ under our case hypothesis can be defined as: y = ρ ⟷ ∀ z < y ∃ τ z ∀ τ ∈ ( τ z , α ) ( y > R 1 ( τ ) > z ) .

By Π 3 -reflection there is an admissible β < α with τ 0 < β ∧ ∀ τ ∈ ( τ 0 , β ) R 1 ( τ ) < ρ and also ∀ z < ρ ∃ τ z ∀ τ ∈ ( τ z , β ) ( ρ > R 1 ( τ ) > z ) .

(In the case that ρ = α , then the ρ in both these last expressions is then taken to be β.)

Case 2 Otherwise (which implies ρ < α as R 1 ( τ ) < α for any τ < α ).

By increasing τ 0 if need be in this case we may assume ∀ τ 2 ∈ ( τ 0 , α ) R 1 ( τ 2 ) ⩾ ρ (as there is no going left at limits beyond τ 0 ).

We now argue that the conditions for P e ( m ) ↓ at time α also occurred at an earlier time α ¯ . We’ve remarked above that we can assume by Π 2 reflection at the admissible α that there is a closed unbounded set C ⊆ α of α ¯ , with I ( α ¯ ) = I ( α ) = s , and R k ( α ¯ ) = r k for k = 0 , 2 .

In Case 1 we have that R 1 ( β ) = ρ (respectively R 1 ( β ) = β if ρ = α ) . By the case hypothesis the value of the cell C ρ ( τ ) is unchanged in the interval ( τ 0 , α ) and so also in ( τ 0 , β ) . We may also assume by an additional reflection clause, that β is in the Π 2 -definable set C. We thus have that cell contents of C ρ k , head positions R k ( β ) , and state number I ( β ) = s are the same at times β and α. Thus all the ingredients are there for P e to halt at time β < α .

In Case 2 knowing that ∀ τ 2 ∈ ( τ 0 , α ) R 1 ( τ 2 ) ⩾ ρ , then the Π 2 fact about α (i) that R 1 ( α ) = ρ , and additionally (ii) C ρ 1 ( α ) = 0 (if the latter holds) reflect to an unbounded (in fact closed) subset E of C above ρ. If C ρ 1 ( α ) = 1 then we have C ρ 1 ( τ ′ ) = 1 for a tail of τ ′ < α , and so also on a tail of τ ′ ∈ E 0 where E 0 reflects (i) alone. Again the conditions for halting at α are reflected to any α ¯ ∈ E (or respectively E 0 ), and so P e must halt earlier. This ends the proof of Theorem 2.1 (ii)(a). □

The following discussion yields the version of Theorem 2.1(ii)(b) for OTMs. Definition 2.5.

σ 1 is the first stable ordinal: that is, it is the least σ so that L σ ≺ Σ 1 V .

Remark 2.6.

Now if any OTM program halts on some integer input, then this Σ 1 fact must reflect to L σ 1 , hence this halt must be at a stage α < σ 1 , and moreover with tape contents an element of L σ 1 . We note that halting times of OTMs on integer input, are cofinal in σ 1 : by the definition of σ 1 , there are arbitrarily large α < σ 1 where some new Σ 1 -sentence, φ say, is first true at L α + 1 , but not at L α . As Koepke shows we may run an OTM that produces codes for L β ’s. Then we may adopt this to halt when it finds one in which φ is true; this will take more than α, but less than σ 1 , many steps.

Lemma 2.7.

Suppose that ω < β is not Π 3 -reflecting and is a supremum of halting times of multi-head-OTM computations on integer input. Then β itself is such a halting time; it thus does not start a gap in the multihead-OTM clockables.

Proof.

This proof should just be: run the same construction as Lemma 2.4. We need to make some observations and adjustments pertinent to the OTM-scenario. Firstly, because β is assumed to be a supremum of such OTM-halting times, we have that L β ⊧ “ V = HC ”. This is because, if P e ( k ) ↓ α then this is a Σ 1 -fact, first true in L α + 1 , and it is then easily seen that α is not a cardinal in L α + ω . (Otherwise, by the Levy reflection Theorem applied in L α + ω , every such Σ 1 -fact would be true at a level before σ 1 L α + ω < ω 1 L α + ω < α + ω by assumption.) Hence any such L α + ω ⊧ “ω is the largest cardinal”. (And α < σ 1 .) As this holds for unboundedly many α + ω below β, it holds for L β .

Secondly, we assume that β is admissible. (If β is inadmissible, then known methods can find a suitable program P e ↓ β . We leave this to the reader.)

Essentially we run the same proof: here however we run Koepke’s version of the Theory Machine: we assume on the scratch tape that (adapting the truth predicate machine of [20]) that the program computes successively the constructible levels of the L τ hierarchy, now for τ < β ; by the admissible time β this machine has written codes successively for all the τ < β . As before we let φ [ x ] ≡ ∀ u ∃ v ∀ w ψ ( u , v , w , x ) , where we assume φ [ x ] fails to be true in any L τ for τ < β , but is true at L β . Define G as before: then still G : ω ⟶ β is a cofinal function, ( Π 2 ∧ Σ 2 ) L β (parameter free). That G exists uses the first observation that L β ⊧ “ V = HC ” and again, being a supremum of halting times, there are no proper Σ 1 -substructures of L β and hence p β 1 = ∅ . Now run the argument exactly as before. The only difference is that our definition of OTM behaviour has that the R/W head on tape T k does not return to C 0 k at some limit stage by overshooting the end of the tape, but can do so at a successor stage, either in the natural course of the Turing program or because it attempted to “move left whilst on a limit cell”. But all is well and at the very end of the above proof, at time β the R/W head of T 1 is not returned to its 0’th cell C 0 1 , but is placed on C ω 1 where however it is reading a 0, and again for this piece of the subroutine it is the first time this happens at any stage β ′ > 0 . So again we can program a halt at this stage. This ends the proof of Lemma 2.7 & Thm. 2.1 (ii). □

Corollary 2.8.

If γ is a supremum of halting times in either the ITTM or OTM multihead models, then γ starts a gap iff γ is Π 3 -reflecting.

2.2. Single head machines