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

Abstract

We consider how changes in transfinite machine architecture can sometimes alter substantially their capabilities. We approach the subject by answering three open problems touching on: firstly differing halting time considerations for machines with multiple as opposed to single heads, secondly space requirements, and lastly limit rules. We: 1) use admissibility theory, $Σ_{2}$ -codes and $Π_{3}$ -reflection properties in the constructible hierarchy to classify the halting times of ITTMs with multiple independent heads; the same for Ordinal Turing Machines which have On length tapes; 2) determine which admissible lengths of tapes for transfinite time machines with long tapes allow the machine to address each of their cells – a question raised by B. Rin; 3) characterise exactly the strength and behaviour of transfinitely acting Blum–Shub–Smale machines using a Liminf rule on their registers – thereby establishing there is a universal such machine. This is in contradistinction to the machine using a ‘continuity’ rule which fails to be universal.

Keywords

Turing Machine computability Blum–Shub–Smale generalized recursion admissible set

1. Introduction

The study of transfinite computational models fully reemerged with the appearance of the Infinite Time Turing machines (ITTMs) of Hamkins and Kidder in [15].1

¹
We should like to thank Merlin Carl, Lorenzo Galeotti and Philipp Schlicht for conversations concerning some of the issues and arguments here.

It was not that there were no precursors to the idea of transcending the finite by some forms of recursive model: Machover [23], and Takeuti [29] formulated equational calculi involving ordinal recursive set functions, as did more famously perhaps Jensen and Karp [17], and Gandy [13]. It is hard not to view equational calculi of this type as being simply abstract ‘machines’ as well. However Platek explicitly thought of a register-like machine containing transfinite, rather than finite, ordinals. Kleene himself used a model comprising infinite but wellfounded trees whose nodes had (ordinary) Turing machines attached, for use in computing higher type recursion [18,19]. Rogers in his fundamental text [27] used the analogy of the ‘

ℵ_{0}

-mind’ as having some countably infinite memory storage with an ability to sort and manipulate countable amounts of information in single steps. This was in his account of a description of the hyperarithmetic sets. Even ITTMs had a precursor (it later transpired) with a device invented by Burd [5], for which, although being entirely similar to ITTMs, he seemingly only wrote one routine which took just

ω \cdot 2

steps to complete.

However [15] caught the imagination of not a few people, and thereafter various authors examined all sorts of finite based machines and tried to propel them into the transfinite. Others sought to tweak the parameters of an ITTM. Restricting to the latter for the moment, it transpired that the model was very robust under structural changes: whether one considered lim inf rather than the original lim sup rule at limit stages made no difference; neither did relaxing the requirement that the read/write (R/W)2

We use a variety of initialisms: “R/W” for “read/write”; “OT” for “output tape”; “TM” is not “Turing machine” but “Theory Machine”.

head return to the origin and enter a special limit state

q_{L}

make any difference to the functions on Cantor space,

2^{N}

, so computed. We further considered the question as to whether some other limit rule, say another

Σ_{2}

-definable limit rule, would allow for a wider class of functions to be rendered ITTM-computable. In [30] we showed that essentially the Liminf rule was ‘maximal’ or ‘universal’ amongst all other

Σ_{2}

-rules. This with hindsight is not very surprising: once one has established that standard ITTMs can compute (codes for) the levels of L up to

L_{ζ}

where ζ is the least

Σ_{2}

-extendible ordinal, that is the least so that there is some

Σ > ζ

with

L_{ζ} ≺_{Σ_{2}} L_{Σ}

(see the “λ-ζ-Σ-Theorem” of [30]), then, with any other limit rule being absolutely definable to L, this shows that an ITTM equipped with a different rule cannot do better than computing codes up to

L_{ζ}

, and would be subject to the same looping behaviour at

[ζ, Σ]

as the standard ITTM. It is then easy to see that the standard ITTM can simulate, via the L-hierarchy if need be, the non-standard one. So the latter cannot be stronger. (Limit rules at higher degrees of definability, so

Σ_{3}

and above, are altogether a different matter.)

Hamkins and Seabold [16] considered whether the three Input, Output and Scratch tapes of an ITTM could be replaced by a single tape. It turned out that the class of computable functions $F : 2^{ω} ⟶ ω$ was unchanged but $F : 2^{ω} ⟶ 2^{ω}$ would be smaller. Indeed, while it is easy to easy enough to conceive of using recursive subclasses of a single tape for scratch and output, it was shown that the compression of a tape to a single ‘output tape’ for presentation of the resulting element of $2^{ω}$ as output would go awry. It was noted that with larger alphabets, or a special reserved cell or some other gadget, would restore the full class. An example of this can be found in [33] where we considered the idea of using cells with blank contents: this allowed a blank for “ambiguity” to be used at limit stages λ when the cell’s value had changed unboundedly often below λ. On a one-tape model this restored the full computational power of the three-tape ITTM. Certain considerations would still nevertheless mean that halting times, or lengths of gaps in halting times would still change if the tapes or alphabet were to change – as one might imagine.

The original formulation of ITTMs in [15] used the idea that at limit ordinal times, μ say, the machine entered a special ‘reserved state’ $q_{L}$ to indicate it was at a limit, but also the R/W head was always returned to the starting position so that it was reading the first cells of each of the three tapes. Subsequent discussions showed that a designated state $q_{L}$ was somewhat unnecessary, as was the requirement to return to the beginning: instead the R/W head can be returned to the lim inf of the head positions prior to the limit ordinal μ, and the state number i (of $q_{i}$ ) at that time μ was then set to be the lim inf of the previous state numbers. This seemed anyway more rational as with reasonable programming desiderata, this arrangement had the R/W head, and the program, entering the chief or head subroutine that was initiated unboundedly often in time μ. It is easy to check that, e.g., the class of ITTM computable functions, semi-decidable sets, etc., is unchanged by this. The arguments of [15] that showed admissible ordinals cannot be halting times of an ITTM program, and that only admissibles may start gaps in these halting times (see Def. 1.1 below) of [32] adapt to this situation. We have adopted this formulation throughout this paper.

We address the question here of ITTMs with not only multiple tapes, but multiple and independently moving R/W heads. This of course has to be programmed into the state or transition table of the Turing program, as each head will be moving according to the independent diktats of whatever the head is observing at the time. However this is quite unproblematic and familiar to Turing machine theorists. A complete snapshot of the machine at any stage of time α now must also give information about the position of each of the heads, in addition to the ω-sequence of cell values on each of the tapes. To be concrete we imagine below an ITTM with two independent R/W heads and at least two tapes. This suffices for the arguments below: more tapes and heads does not make a difference to the results. The results illustrate a difference with the single head models considered to date: the same classes of functions are thereby computed, but the spectrum of halting times, whilst retaining the same supremum as before, now has a different distribution. For example $ω_{1}^{ck}$ now becomes a halting time of a multihead ITTM.

These results are also planned with the Ordinal Turing Machines of Koepke [20] in mind. These OTMs were a natural extension, in that a tape was allowed with an On-length of cells. Koepke gave a standard definition of such a machine using a single tape. However then he fairly quickly went to also allowing multiple tape, multi-head models. All such computed (on zero input) the same class of (codes of) sets: namely all of L the Gödel constructible hierarchy. Thus a new presentation of this hierarchy became available which only used this hardware plus a standard Turing program. Indeed he phrased this in terms of computing a truth predicate for L, where a formula and ordinal parameters could be submitted via the input tape, for query as to its truth in L and 1/0 output would be calculated. Questions of ‘halting times’ for programs $P_{e}$ for this model were not considered by him.

Definition 1.1.

We say that an ordinal α is OTM-clockable (ITTM-clockable) if for some OTM-program (ITTM program) $P_{e}$ , some $k \in ω$ , we have $P_{e} (k) ↓^{α}$ , that is, it halts in exactly α steps, and thus α is the halting time of $P_{e} (k)$ .

Carl in [8] considers this for a multitape and multihead version of OTM. He shows: any $Σ_{2}$ -admissible ordinal is not clockable in this sense. This provides an upper bound. As a lower bound he shows that any ‘gap’ in the clockable ordinals (meaning a maximal interval $[γ, δ)$ where no program $P_{e} (k)$ on integer input k halts at any time $α \in [γ, δ)$ ) must be initiated by an ordinal γ which is at least an admissible limit of admissibles. The possibility remained open that an admissible limit of admissibles could be such a gap-starting γ. We show that this is not the case, and eliminate the space between upper and lower bounds by pinning down the exact gap-starting ordinals by showing in Section 2:

Theorem 2.1.

Suppose we consider multiple head ITTMs.

Let α be $Π_{3}$ -reflecting. Then α is not ITTM-clockable.

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.

The same holds true for OTMs if again we allow multiple heads.

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.

Hence in contradistinction to the single head ITTMs, $ω_{1}^{ck}$ is a halting time for the multihead version. The above then also settles then the question of the clockable OTM ordinals, and those starting gaps. Nothing so far answers the following:

Question 1.

Is $ω_{1}^{ck}$ clockable by a single-head multi-tape OTM program?

However we’ll see as a Corollary of Theorem 2.10 that $ω_{1}^{ck}$ is also a halting time of a single-head OTM.

Corollary 2.11.

Let γ be a supremum of single-head OTM halting times. Then:

γ starts a gap ⟺ γ is either $Π_{3}$ -reflecting, or is an admissible limit of $Σ_{2}$ -extendibles.

Here we recall:

Definition 1.2.

An ordinal ξ is a $(Σ_{2})$ -extendible ordinal, if $L_{ξ}$ has a proper transitive $Σ_{2}$ -end-extension to some $L_{σ}$ : $L_{ξ} ≺_{Σ_{2}} L_{σ}$ .

The OTMs with ordinal tapes, as the ITTMs even do, beg the question of the nature of ITTM versions with tapes of some set length α, with $ω < α$ . It is reasonable to consider α with some amount of closure, for example, under primitive recursive set or ordinal functions, or else to be admissible. In the early days of ITTM or study of “α-ITTM” study, there had been some hope that since a machine theoretic description of these levels of the L hierarchy was possible, and the actions of such machines were so slowly restricted to one-step-at-a-time actions, that possible some new properties of L would discovered, or some approach to a new, or even the older, Jensen-style fine structure might emerge. Perhaps even a new proof, or aspects of proof, of combinatorial principles such as Jensen’s Square principle might be possible? Silver machines [4,10,25] give one a hope in this direction. However it seemed that these hopes were to be disappointed. Jensen fine structure (and Silver machines) depend very much on the notion of $Σ_{1}$ -definability. The $Σ_{2}$ -limit rule of α-ITTMs works against any finer dissection of the Jensen fine structure, or proofs of □. Arguments constructing □-sequences depend on taking $Σ_{0}$ -hulls and unions of such. A $Σ_{2}$ -hull is simply too rich.

There is a broader context in which to discuss ITTMs and their variants, and that is of the notion of quasi-inductive definition. This is strictly speaking not a discussion needed to undertake the results of the paper, but is more motivational of some the viewpoints we hold concerning basic definitions, and gives some historical background as well as tying in the older, but very developed, theory of inductive definitions, with ITTM theory. This notion is taken from nomenclature devised by John Burgess [6] in a paper discussing the Herzberger variant of the revision theory of truth of Gupta and Belnap [14]. This turns out to be formally equivalent, in some loose sense, when performed as a truth theory over the natural structure $N = ⟨ N, 0,^{'}, +, \times ⟩$ and the theory of ITTMs.

This revision theory uses a recursive process to define truth sets of sentences, so “truth-sets” over a first order structure, such as $N = ⟨ N, 0,^{'}, +, \times, T ⟩$ in, here, the language of arithmetic augmented by a $\dot{T}$ -symbol for a one place predicate whose extension $T_{α + 1}$ at stage $α + 1$ is the set of Gödel numbers of sentences in this extended language true in $⟨ N, 0,^{'}, +, \times, T_{α} ⟩$ . Unlike the Kripkean theories of truth that build up partial truth sets in such a language monotonically, here the extension is supposed to be total. However liar sentences (such as a simple liar $L ⟷ \neg L$ ) and other self-referential sentences are possible as elements of $T_{α}$ – and the rules for negation require that $⌜ L ⌝ \in T_{α} ⟷ ⌜ L ⌝ \notin T_{α + 1}$ ; hence the process is non-monotonic. The question that exercised revision theorists was what to do a limit stages, thus how should e.g. $T_{ω}$ be defined? Herzberger took a lim inf rule: $T_{λ} = {lim inf}_{α \to λ} T_{α}$ and the reader can no doubt surmise some connections to ITTMs building up the extension of the cell values of the Turing machine over stages α. Often for a Herzberger revision sequence that incorporated this liminf rule, one would start with $T_{0} = \emptyset$ although the more sophisticated revision theories considered all possible starting distributions of truth sets, and indeed all possible limit rules for a stage λ, with the proviso that it be consistent with the set of sentences already stabilized below λ.

Burgess considered arithmetical quasi-inductive definitions which were in general intermediate between the idea of recursive quasi-inductive definition afforded by an ITTM, and the fully first order, or $Δ_{ω}^{0}$ -, idea inherent in a Herzberger revision sequence. Just as at limit stages an ITTM defines its cell values by a $Σ_{2}$ -limit liminf rule, so does a Herzberger sequence define extensions to the λ-th stage $T_{λ}$ of a truth predicate, by a Liminf rule of the previous ‘revised’ sets of Gödel numbers $T_{α}$ for $α < λ$ . Löwe first pointed out the similarities between ITTMs and these revision theories. In [22] he wrote an ITTM program for simulating a given Herzberger revision sequence where the length of that sequence was itself writable by an independent ITTM program. That this latter restriction was unnecessary was argued in [31]: ITTMs can fully simulate any such revision sequences without fixing a length in advance.

Such lim inf rules do not have many examples in either mathematical, or philosophical, logic. This is perhaps unsurprising. The inbuilt nature of the ordinals to their definition, and the fact that the ordinals required turned out to need $Π_{3}^{1}$ - ${CA}_{0}$ to define them is a rarity (cf. [28]). This contrasts with the clearly natural inductive definition in particular the positive elementary inductive definition of [24].

A set $S \subseteq | A |$ (for some arbitrary relational structure $A$ ) is inductive over $A$ in this sense if it is (1-1) reducible to a fixed point arising from a positive elementary induction definition; more particularly it is a section of that fixed point.

In some more detail: let $A = ⟨ A, R_{1}, \dots, R_{k} ⟩$ be a relational structure. The language $L_{A}$ contains constant symbols $\dot{p}$ for elements p of $A = | A |$ , and relation symbols $\dot{R_{1}}, \dots, {\dot{R_{}}}_{k}$ . Let $φ \in L_{A}$ be $φ (v_{0}, \dots v_{n - 1}, p_{1}, \dots p_{m}, S)$ be a formula in which S occurs positively. We let φ define an operator: $\begin{matrix} Γ_{φ} : P (A^{n}) ⟶ P (A^{n}) by Γ_{φ} (S) = {\bar{x} : φ {(\bar{x}, \bar{p}, S)}^{A}} . \end{matrix}$

Such an inductive definition by the positivity of the occurrence of S results in $Γ_{φ}$ being a monotone operator, and hence we are guaranteed a fixed point. We thus define iterates: $\begin{matrix} I_{φ}^{< ξ} = ⋃_{τ < ξ} I_{φ}^{τ}; I_{φ}^{ξ} = Γ_{φ} (I_{φ}^{< ξ}); I_{φ} =_{df} I_{φ}^{\infty} . \end{matrix}$

Definition 1.3.

(i) P is inductive over $A$ , if for some φ, for some $\bar{p} \in A^{n}$ , then $\begin{matrix} P = {\bar{x} (\bar{x}, \bar{p}) \in I_{φ}} “ P \in {IND}_{A} ” \end{matrix}$ (ii) P is hyperelementary over $A$ if both P and $\neg P$ are inductive. “ $P \in {HYP}_{A}$ ”.

The inductive sets are closed under: $=, R_{i}, \lor, \land, \exists^{A}, \forall^{A}$ , HYP- substitution. We are going to replace the $Σ_{1}$ -rule of simple unions at limit stages by the $Σ_{2}$ -rule of taking lim inf’s: $\begin{matrix} I_{φ}^{< ξ} = \underset{α < ξ}{lim inf} I_{φ}^{α} = ⋃_{α < ξ} ⋂_{α < τ < ξ} I_{φ}^{τ}; I_{φ} = I_{φ}^{\infty} =_{df} \underset{τ < \infty}{lim inf} I_{φ}^{τ} . \end{matrix}$

Definition 1.4.

(i) P is quasi-inductive over $A$ ,if for some φ, for some $\bar{p} \in A^{n}$ , then $\begin{matrix} P = {\bar{x} (\bar{x}, \bar{p}) \in I_{φ}} “ P \in {qIND}_{A} ” . \end{matrix}$ (ii) P is quasi-hyperelementary over $A$ if both P and $\neg P$ are quasi-inductive. “ $P \in {qHYP}_{A}$ ”.

The quasi-inductive sets are then also closed under: $=, R_{i}, \lor, \land, \exists^{A}, \forall^{A}$ , qHYP- substitution.

That book [24] is dedicated to investigating the mathematics of inductive definitions as they occur over quite arbitrary abstract structures (or at least those equipped with a minimal amount of pairing and coding machinery – the ‘acceptable’ structures). This defines a class of subsets of the domain of the structure, as well as the class of sets of such subsets, as the ‘inductively definable’ ones. Theorems such as Stage Comparison, Boundedness Lemmata, an Abstract Spector–Gandy Theorem etc., etc. all come into place.

It is surprising how much of this can be extended when one deploys the notion of elementary quasi-inductive definition as defined above. The parallels with ITTMs are clear: consideration of the tapes’ contents moves us to think of a computation as convergent if the contents of the output tape eventually settles to some infinite sequence of values. Thinking of the ITTM with its tapes and cell structure as itself the abstract structure $A$ over which we perform the quasi-induction, a set of integers is quasi-inductive if it is again a section of a set arising as a quasi-induction in this sense over $A$ (this means in the case of an ω-ITTM, that the set is (1-1) reducible to a fixed part of the tapes’ contents at stage ζ). It is quasi-hyperelementary if it is both quasi-inductive and co-quasi-inductive. This comes down to: the quasi-hyperelementary sets are those that are eventually settled (on the OT), i.e. those that are eventually writable also known as (eventually) decidable. The quasi-inductive sets are the (eventually) semi-decidable sets.

Thus the emphasis of the ITTM or α-ITTM, is shifted away from the halting computations where the computation formally halts, to those that have simply finished writing to their OT’s – although they may be fiddling away pointlessly on their scratch tapes: in short formally halting is just a special case of convergence. This reflects the analysis of the λ-ζ-Σ-Theorem: the prime ordinal of interest is ζ, not λ: the latter is merely the supremum of the halting times of programs on integer input; ζ is the supremum of the times when a program on input may have ceased writing to its OT. Without analysing this phenomenon of ceasing to write, and ζ, the proof of the λ-ζ-Σ-Theorem would not have occurred. We thus regard ‘ceasing to write’ as prior to the notion of halting for ITTMs. An over-emphasis on ‘halting’ as opposed to this eventual settled behaviour, perhaps lead the original authors into investigating a degree theory in [15] that was based on analogies with ordinary Turing degree theory with its halting problems. This, to the current author’s thinking, was a red herring: the analogy of ITTM-degrees is not with Turing degrees but to something nearer hyperdegrees, indeed to something intermediate between hyperdegrees and $Δ_{2}^{1}$ , say $Δ_{3 ∖ 2}^{1}$ -degrees. The mathematics of ITTM-degrees bears out that this is the correct analogy: the semi-decidable sets form a Spector pointclass; there is a Spector criterion for the degrees and their jump operation. The above notion of convergence of ITTMs fits exactly with the notion of quasi-inductive over a Turing machine (or over $N$ ). Indeed both Herzberger revision sequences and ITTMs provide the prime and first examples of quasi-inductive processes over $N$ .

Pursuing this we come to the second question addressed here. When putting the framework of positive elementary inductive definitions in place for an arbitrary abstract structure $A$ , Moschovakis worked in a language $L_{A}$ containing constants $c_{a}$ for every a in the domain $| A |$ . One clearly has to be able to refer to the elements of the structure in order to build up extensions of some predicate: which are in, which are out.

B. Rin [26] identifies a problem in the model of Turing machines with transfinite length tapes being unable to access all of their cells if one disbars ‘constants’, that is parameters, from their architecture. This is indeed a problem. Parameters are normally allowed as part of the definition of a transfinite computation, particularly in OTMs: we allow a computation to proceed from a finite number of 1’s as input in cells $C_{ξ_{1}}, \dots, C_{ξ_{n}}$ to indicate, or stand in for, a finite list of ordinals $ξ_{1}, \dots, ξ_{n}$ . Such parameters then function as constants allowing us to address, or as Rin defines, ‘reach’ each cell. We may ‘address’ a cell on an α-machine if we have a name for that cell (e.g. in the case of $α = ω$ ) say, or we may ‘reach’ a cell by having a particular program $P_{e} (0)$ that halts exactly on that cell. (In which case we might call ‘e’ a name for that cell and say that this cell is ‘addressable’ or ‘reachable’.) For $α = ω$ we clearly need no such parameters to name or reach cells. But even for countable α the problem arises of what happens when α is sufficiently big that the addressing of all the cells on the tape is impossible? If $α = ω_{1}$ then computing on such a machine would allow the computation of, say a function $F : ω_{1} ⟶ 2$ on the work tape, but one would only have access to countably many values: namely those $F (β)$ for β addressable in this way, if one wanted to work with the function.

The main question left unresolved in [26] is the identity of the following $δ_{0}$ :

Question 2.

What is the least countable $δ_{0}$ so that there is some cell $C_{α}$ for an $α < δ_{0}$ , which cannot be reached by a $δ_{0}$ -ITTM program?

We characterise below precisely the lengths of such tapes for which this problem occurs: they are those for which there is no computation during which a wellordering appears which collapses the length of the tape, here δ, to be countable.

Theorem 3.1.

Every cell $α < δ$ can be reached by a δ-ITTM if and only if during a run of some program on such a machine, a wellorder of ω appears on its tape at some stage which has order type δ.

Corollary 3.4.

Every cell can be reached by a δ-ITTM if and only if $L_{Σ (δ)} ⊧$ “δ is countable” (where $Σ (δ)$ is the supremum of ordinals coded as subsets of ω appearing on the tapes of some δ-ITTM on integer input, at some stage of its computation).

In [9] it is established that $δ_{0}$ is the least ordinal which is uncountable in $L_{Σ (δ_{0})}$ , answering the question above. However the proof here is simpler and direct, and moreover characterises cell reachability for all primitive recursively closed ordinals δ.

We move next in Section 4 to Infinite Time Blum–Shub–Smale machines (IBSSMs). The author recalls a conversation in New York with Hamkins and Koepke, as to how to go about propelling BSS-machines into the transfinite. Two limit rules were proposed: the “continuity” rule, that required one to have a continuous limit of each register’s contents at a limit time; this seemed the most promising. A “Liminf” rule was mooted, but there was overall no further discussion. Koepke and Seyfferth then established several facts in [21] concerning the ‘Continuity’-IBSSMs, the principal one being that any such machine on integer/rational input would either halt or be in a permanent loop by time $ω^{ω}$ . Thus the continuity rule was a stringent one. This left open the strength of the functions computable by such machines. In [34] (Thm. 11) we showed that the class of functions so computed was exactly those in $L_{ω^{ω}}$ . In fact it showed more, that there were equivalent formulations in terms of classes of functions, with “polynomial time” ITTM-computable functions (these were those that halted in time some “polynomial in ω”, or in short by some time $ω^{k}$ for a $k < ω$ ), and those functions on ω-strings generated by the “safe recursive set functions” of Buss et al. [3]. We shall not define this class here, but refer the reader instead to [3]. One thus has some confluence of models computing the same classes – a sub-Church’s thesis perhaps for polytime on ω-strings (or equivalently elements of Cantor space $2^{N}$ ).

Theorem ([34] Thm. 11).

The following classes of functions of the form $F : {(2^{N})}^{k} \to 2^{N}$ are extensionally equivalent:

Those functions computed by a continuous IBSSM machine;

Those functions that are polynomial time ITTM: those computed by some time $ω^{k}$ for a $k < ω$ ;

Those functions that are safe recursive set functions.

Section 4 here seeks to show that the strength of IBSSMs equipped with a Liminf rule for the register contents, rather than the original continuity requirement allows, unsurprisingly, for much greater computational power. It turns out that they have the same power as ITTMs no less. Perhaps this is more surprising given that the notion of Liminf in a Euclidean setting of $R$ with its usual metric, is rather different from a Liminf of cell values in the setting of ITTMs on Cantor space $2^{N}$ . It shows that Liminf rules subsume much of the successor step character of the processes involved.

Essentially this comes from the fact that any ITTM computation $P_{e} (0)$ can be simulated on a ‘Liminf’-IBSSM $B_{\bar{e}} (0.0)$ . Consequently the IBSSMs can have no lesser strength than ITTMs. Since ITTMs can compute (codes for) levels of the $L_{α}$ hierarchy this means IBSSMs can do the same. It is easier to see that any IBSSM computations can be considered as absolute to L. This implies that they can be simulated by ITTMs. Hence we have the same λ-ζ-Σ phenomenon for IBSSMs, as for ITTMs: namely they must loop at latest by time ζ with a loop repeating at time Σ. Another corollary (Cor. 4.4) is that Liminf-IBSSMs have a universality property – this is because ITTMs do and the two classes of machine are ‘bi-simulable’. There is thus a universal such Liminf-IBSSM. This contrasts with the ‘Continuity’-IBSSMs where there is no such universal machine. (This follows easily from Theorem 1 of [21] which shows that for any IBSSM machine using the continuity criterion at limit stages, if a program has k computation nodes in its flow chart, then any halting computation must have length less than $ω^{k + 1}$ , and so is not reaching all the functions IBSSM-computable. Applying that, it is immediate that no such program can be universal.)

Corollary 4.5.
For liminf-IBSSMs the set Z of reals to which an IBSSM computation (on rational input) is convergent, is precisely the set Z of those reals in $L_{ζ}$ .

(A convergent computation (on rational input) is one in which a designated register, e.g. $R_{0}$ , has a final settled value from some point onwards.)

Preliminaries

We assume the reader is familiar with the machine architectures under discussion – to limit space we do not review these here, but instead refer the reader to the original papers or to [7].

The results here very much tie in with low level set theory and Gödel’s constructible hierarchy of sets $L = ⋃_{α \in O n} L_{α}$ the basic construction of which we assume (v. [11] for example or elsewhere).

The theory of ITTM halting times, and indeed computable sets is intimately tied up with the levels of the hierarchy which are admissible models of Kripke–Platek set theory which we may take as the weakening of ZFC by restricting to $Δ_{0}$ -Collection and $Δ_{0}$ -Separation. It is well known that in this theory $Δ_{1}$ -Separation and $Σ_{1}$ -Collection and Replacement are provable. In $Σ_{2}$ -admissibility theory, these axiom schemes are strengthened to $Σ_{2}$ -Collection and $Δ_{2}$ -Separation. The reader can consult [2] for the following results, or for admissibility theory in general. We shall need in addition to this notions of reflecting levels of the hierarchy.
Definition 1.5.
An ordinal $α > ω$ is $Π_{n}$ -reflecting, if for any $φ (v_{0}) \in Π_{n}$ , for any $x \in L_{α}$ , if $φ {[x]}^{L_{α}}$ then for some $β < α$ $φ {[x]}^{L_{β}}$ .
Remark.
(1) Admissibles are $Π_{2}$ -reflecting, ([2], V 7.15) and hence it is easily seen they are reflecting for Boolean combinations of $Π_{2}$ and $Σ_{2}$ formulae. Clearly even with parameters allowed, if a formula reflects once because of such a principle holding at α, it will reflect unboundedly often below α.

(2) By inspection the axioms of KP are formulable in a $Π_{3}$ -manner. Hence we can always take the β in the definition above to be admissible when considering $Π_{3}$ -reflection. (A $Π_{3}$ -reflecting ordinal is ‘recursively Mahlo’ in the terminology of [1] – although not conversely.)

(3) A $Π_{3}$ -reflecting ordinal is admissible, and is a limit of such. It is easy to see (by using similar reasoning to that for (1)) that (a) $Σ_{2}$ -admissibles are $Π_{3}$ -reflecting; however (b) the first admissible limit of admissibles is not; (c) for any $n < ω$ , the first $Π_{n}$ reflecting ordinal is less than the first $Σ_{2}$ admissible.

At one or two points we refer to, and indeed use the “Theory Machine” (TM) (see [12]). To make this paper a little more self-contained we sketch this program here. The idea of the TM is to produce in a coherent, and sequential fashion, codes (meaning reals coding the ∈-diagrams of levels of the L-hierarchy, $L_{α}$ , together with their $Σ_{2}$ -theories.

The motivating point behind the Theory Machine is that it constructs such codes and theories in a smooth uniform fashion. In [30] we used, in a slightly ad hoc fashion, a program that ran the universal ITTM, and simply collected together sums of ordinals appearing on the tapes as it progressed. Given such a sum, in a side manœuvre, we could then construct a segment of the L-hierarchy along this ordinal sum for our inspection. These sums, almost by definition, stretched out unboundedly in Σ. What the TM does is cut this collection process of ordinals out, and simply produces the $L_{α}$ for $α < Σ$ more directly.

An important point from the theory machine, is that in essence it is a version of the universal infinite time Turing machine program: ITTM operations are absolute to L, and the theories of various levels of $L_{α}$ contain the information about the universal ITTM run up to stage α. Then the information of the universal ITTM (on integer inputs) is all implicitly contained in the course of computation of the one single TM.

We set $T_{α}^{2}$ to be the $Σ_{2}$ -theory in the language of set theory of $(J_{α}, \in)$ . We use the J-hierarchy rather than the traditional L-hierarchy to avail ourselves of uniformly definable Skolem functions. This is not terribly important, but using the L-hierarchy is a bit more awkward. Recall that $O n \cap J_{α} = ω \cdot α$ and if $ω \cdot α = α$ (certainly when α is admissible or primitively recursively closed) then $J_{α} = L_{α}$ in any case, hence replacing $J_{α}$ ’s by $L_{α}$ ’s in the sequel will be no great lie for those unfamiliar with the former. The reader need not study the proof of the next Lemma nor the one following in order to understand the arguments of the paper. Lemma 1.6.
There is an ITTM programme $P_{e} =$ TM which does not converge, but continuously produces alternately codes $x_{α}$ for levels $J_{α}$ and their $Σ_{2}$ -theories $T_{α}^{2}$ for $α < Σ$ . At stage Σ as $T_{Σ}^{2} = T_{ζ}^{2}$ the TM loops back and reproduces the code $x_{ζ}$ and continues this process thereafter repeating codes and theories for $α \in [ζ, Σ)$ .
Proof.
We briefly sketch the effective procedure to be formalised. The input to TM is presumed to be zero. On the output tape at round α a code for $x_{α}$ is first written in one designated area and from this the theory $T_{α}^{2}$ is calculated and written in another. Then $x_{α + 1}$ is calculated from $T_{α}^{2}$ and overwrites $x_{α}$ . Then $T_{α + 1}^{2}$ is determined, and overwrites $T_{α}^{2}$ . At a limit stage λ the area for codes contains in general just an overwritten mess of integers, but the area for the theories contains – by the usual Liminf rules ${\hat{T}}_{λ} =_{df} {lim inf}_{α \to λ} T_{λ}^{2}$ . If λ is admissible then this equals $T_{λ}^{2}$ . But even if not, one may show that, uniformly in λ, $T_{λ}^{2}$ is recursively enumerable in the liminf theory ${\hat{T}}_{λ}$ . From this we may construct a code for $J_{λ}$ and continue. Each round of this process only takes roughly speaking another $ω^{2}$ -many steps. As one can surmise, the process must cycle around when it reaches stage Σ and this is because we must have ${\hat{T}}_{ζ} = {\hat{T}}_{Σ}$ and the next code produced falls back to $x_{ζ}$ once more.

This description suffices for this paper, and, again, the rest of this proof can be ignored, but we give a few more details here for the interested reader. A theory T is written with $φ_{n} \in T$ iff the n’th cell contains a 1. If σ is a sentence in this language, we let $⌜ σ ⌝$ be that n where σ is $φ_{n}$ in the given recursive enumeration. In the first $ω^{2} + ω \cdot 2$ stages TM writes the code of $J_{1} = L_{ω} = HF$ and its $Δ_{0}$ -diagram which we shall denote $d_{1}$ , to two reserved tapes, and its $Σ_{2}$ -theory to the OT. (It takes less than this, but it keeps the induction bookkeeping straight.) We assume inductively that at time $ω^{2} \cdot α + ω \cdot 2$ the OT contains the theory $T_{α}^{2}$ of $⟨ J_{α}, \in ⟩$ and the reserved tapes again the $Δ_{0}$ -diagram of $J_{α}$ , $d_{α}$ , and a code for $J_{α}$ . With the theory $T_{α}^{2}$ of $J_{α}$ TM can construct a code $x_{α + 1}$ for $J_{α + 1}$ in $ω^{2}$ additional steps together with its $Δ_{0}$ -diagram $d_{α + 1}$ (this is essentially an exercise, but uses the fact that for $α < Σ$ there is a uniform parameter free $Σ_{2}^{J_{α}}$ -definable partial map $f_{α} : ω \to J_{α}$ which is onto).

We are now at stage $ω^{2} \cdot α + ω \cdot 2 + ω^{2}$ . In an additional $ω \cdot 2$ steps $T_{α + 1}^{2}$ is calculated from $d_{α + 1}$ and written to OT. This will take us to stage $ω^{2} \cdot (α + 1) + ω \cdot 2$ . (This all takes some routine work to make clear, but essentially this two quantifier theory can be recovered from the double Turing jump of the code $d_{α}$ . Each jump can be written out by an ITTM in ω-steps (in fact the double jump can be so written, but we can ignore that), thus requiring $ω \cdot 2$ steps to write out the two jumps and thus obtain the complete theory $T_{α + 1}^{2}$ .)

Of course we do this writing simply by changing the cells one by one according to what has appeared or disappeared passing from $T_{α}^{2}$ to $T_{α + 1}^{2}$ . If $φ_{n}$ is in both theories, then the 1 in the n’th cell is not changed to a 0 and then back again to a 1. By this method of writing, at a limit stage $ω^{2} \cdot λ$ for $Lim (λ)$ , ${\hat{T}}_{λ}$ is on the OT, and thus the true $T_{λ}^{2}$ is r.e. in the OT, by the next lemma. Hence in ω further steps it can then write the correct $T_{λ}^{2}$ to the OT, thus by stage $ω^{2} \cdot λ + ω$ .

The following is then Lemma 1 from [12]. Lemma 1.7.
There is an (ordinary) Turing recursive function $f : ω \times ω ⟶ ω$ , so given by an index e, so that for any $Lim (λ)$ satisfying $J_{λ} ⊧$ “Every set x is countable”, if we set $T = {\hat{T}}_{λ}$ then $T_{λ}^{2}$ is uniformly r.e. in T, via f, that is: $⌜ σ ⌝ \in T_{λ}^{2} ⟷ \exists i f (i, ⌜ σ ⌝) \in T$ .
Proof.
Let $σ \equiv \exists u ψ (u)$ with $ψ \in Π_{1}$ . Let $h_{τ}$ be the canonical $Σ_{1}$ Skolem function for $J_{τ}$ . If $⟨ φ_{i} i < ω ⟩$ enumerates the $Σ_{1}$ formulæof the language of set theory, then if ${(\exists x φ_{i} (x, v_{1}, \dots, v_{n}))}^{J_{τ}}$ then $(φ_{i} {(h_{τ} (i, ⟨ v_{1}, \dots, v_{n} ⟩, v_{1}, \dots, v_{n}))}^{J_{τ}}$ . Thus $h_{τ}$ is a partial function from $ω \times^{< ω} J_{τ}$ to $J_{τ}$ and has the same definition in over any $J_{τ}$ uniformly in τ. Let $S_{τ}^{1} =_{df} {γ < τ J_{γ} ≺_{Σ_{1}} J_{τ}}$ . Then for any $γ \in S_{τ}^{1}$ we have that $h_{τ}$ “ $ω \times {γ}$ is the least $Σ_{1}$ Skolem Hull $X ≺_{Σ_{1}} J_{τ}$ with $γ \in X$ . If $J_{τ} ⊧$ “Every set x is countable”, then it is easy to show that $γ + 1 \subset X$ and moreover $X \cap O n \cap J_{τ}$ is the least element of $S_{τ}^{1} \cup {ω \cdot τ}$ strictly above γ. Claim.
$σ \in T_{λ}^{2} ⟷ \exists i [\exists τ_{0} \forall τ \in (τ_{0}, λ) J_{τ} ⊧ “ \exists β \in S_{τ}^{1} ({(σ)}^{J_{β}} \lor {(h_{τ} (i, β) ↓ \land ψ [h_{τ} (i, β)])}^{J_{τ}}) ”]$ .
Proof of Claim.
Case 1. $S_{λ}^{1}$ is unbounded in λ.

Suppose the left hand side holds of σ. Suppose $ψ {(u_{0})}^{J_{λ}}$ holds for $u_{0}$ . Then for some sufficiently large $β \in S_{λ}^{1}$ , $u_{0} \in J_{β}$ , and then $ψ {(u_{0})}^{J_{β}}$ . But $β \in S_{λ}^{1} ⟶ β \in S_{τ}^{1}$ for any $λ > τ > β$ ; consequently the first disjunct of the right hand side holds. For the converse direction, fix the given i. By the Case hypothesis we can assume that τ itself is in $S_{λ}^{1}$ . But then if the first disjunct holds, if ${(σ)}^{J_{β}}$ and $β \in S_{τ}^{1}$ then $β \in S_{λ}^{1}$ and thence ${(σ)}^{J_{λ}}$ . If the second disjunct holds for the supposed i $ψ {[h_{τ} (i, β)]}^{J_{λ}}$ holds for the same reasons.

Case 2 $β_{0} =_{df} max S_{λ}^{1} < λ$ exists.

By the bullet points above every $x \in J_{λ}$ is of the form $h_{λ} (i, β_{0})$ . Again suppose the left hand side holds of σ and $ψ {(u_{0})}^{J_{λ}}$ holds for $u_{0}$ . In particular now $u_{0} = h_{λ} (i, β_{0})$ for some i. Let $τ_{0} ⩾ β_{0}$ be sufficiently large so that ${(h_{τ_{0}} (i, β) ↓)}^{J_{τ_{0}}}$ and thence, by the fact of ψ being $Π_{1}$ , ${(ψ [h_{τ_{0}} (i, β)])}^{J_{τ_{0}}}$ . By the upwards persistence of $Σ_{1}$ formulae in the first case and downwards persistence of ψ in the second case, these will hold in all larger $J_{τ}$ for $τ ⩽ λ$ replacing $τ_{0}$ . But now the second disjunct of the right hand side holds.

Conversely suppose the right hand side holds. Let i be as supposed. By the maximality of $β_{0}$ for unboundedly many $τ^{'} \in (β_{0}, λ)$ some new $Σ_{1}$ -sentence about $β_{0}$ becomes true first in $J_{τ^{'} + 1}$ . Pick such a $τ = τ^{'} + 1$ of this form. Such a τ ensures that $S_{τ}^{1} = S_{λ}^{1}$ and thence $max S_{τ}^{1} = β_{0}$ too. So suppose the first disjunct holds for such a successor τ. Then if ${(σ)}^{J_{β}}$ holds for a $β \in S_{τ}^{1} = S_{λ}^{1}$ we shall have ${(σ)}^{J_{λ}}$ and we are done. Thus we now suppose the first disjunct fails for τ of this form; pick any such τ, then the second disjunct holds as witnessed by a $β \in S_{τ}^{1}$ .

Then if $β < β_{0}$ then ${(\exists y (y = h_{τ} (i, β)))}^{J_{τ}}$ implies ${(\exists y (y = h_{β_{0}} (i, β)))}^{J_{β_{0}}}$ by the uniformity of the definition of the $Σ_{1}$ -skolem function h, and the fact of $β_{0} \in S_{τ}^{1}$ . But then ${(h_{β_{0}} (i, β) ↓ \land ψ [h_{β_{0}} (i, β)])}^{J_{β_{0}}}$ . But this entails that the first conjunct holds for τ, which we are assuming does not happen. Hence we must have $β = β_{0}$ . However then $ψ {[h_{τ} (i, β_{0})]}^{J_{τ}}$ for any τ of this form, and so for such τ arbitrarily large below λ. By the upwards persistence of $h_{γ} (i, β_{0})$ for $γ \in [τ, λ]$ we have $ψ {[h_{τ} (i, β_{0})]}^{J_{λ}}$ and hence $σ^{J_{λ}}$ . This ends the proof of the Claim. □

We may then finish off the Lemma as follows. Note first that the expression in quotation marks on the right hand side, $η_{σ} (i)$ say, here is, if true, a member of $T_{τ}^{2}$ , being $Σ_{2}^{J_{τ}}$ in i. We thus shall have $σ \in T_{λ}^{2} \leftrightarrow \exists i ⌜ η_{σ} (i) ⌝ \in T$ and the Lemma is proven. This ends the proof of Lemma 1.7. □

Finally, by the last lemma the code $x_{λ}$ for $J_{λ}$ on the scratch tape can be written by stage $ω^{2} \cdot λ + ω + ω$ . A code for $J_{λ + 1}$ and the diagram $d_{λ + 1}$ is written by stage $ω^{2} \cdot (λ + 1)$ , and $T_{λ + 1}^{2}$ by $ω^{2} \cdot (λ + 1) + ω \cdot 2$ . This ends the proof of Lemma 1.6. □

2. Halting times of transfinite Turing machines

We show that the spectrum of halting times of ITTMs and OTMs is changed if we allow multiple independent read/write heads. An extra R/W head allows for example, $ω_{1}^{ck}$ , and other admissibles to become halting times.

2.1. Multiple head machines

Multitape/multihead ITTMs are not going to be able to compute more functions than the standard ITTMs, since the latter can simulate the former, either by directly programming them in, or else just appealing to the observation that multihead machines are still absolute to L in their actions. So knowing $L_{β}$ is to know the action of such a machine up to stage β as a sequence of snapshots of all its cell values, head positions, and states as a $Σ_{2}$ -recursion over $L_{β}$ , and thus in turn to know its behaviour from the $Σ_{2}$ -theory of $L_{β}$ . The latter in turn the single-head machine can discover through the Theory Machine of [12]. The only change that is relevant for this discussion is the change in possible halting times, which indeed the extra heads can facilitate. Recall that no admissible ordinal is the halting time of any $P_{e} (n)$ for a standard single head ITTM [15]. The following shows that all ordinals up to the first $Π_{3}$ -reflecting ordinal are such halting times.

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}_{β \to λ}^{} R^{k} (β) = {Liminf}_{β \to λ} 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} \subseteq 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} \lor Π_{2}$ .) We thus have some unbounded $D \subseteq D_{0}$ where these facts reflect to $γ \in 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 \subseteq C$ of ordinals γ where $r^{1} = R^{1} (γ)$ and $C_{r^{1}}^{1} (γ) = 1$ , just as in Case 0.

Case 1a) ${Liminf}_{β \to α} R^{0} (β) = ω$ .

Then $\forall z < ω \exists τ_{z} \forall τ \in (τ_{z}, α) (R^{0} (τ) > z)$ . However this is a $Π_{3}$ -sentence and we may reflect this down, simultaneously with the above $Σ_{2} \lor Π_{2}$ -statements about $r^{1}$ , to some $γ \in D$ . But again this yields the conditions for halting at a stage $γ < α$ as $R^{0} (γ) = 0 = r^{0}$ – a contradiction.

Case 1b) ${Liminf}_{β \to α} R^{0} (β) = 0$ .

Then $\forall τ_{0} \exists τ \in (τ_{0}, α) R^{0} (τ) = 0$ . This is $Π_{2}$ , so again can be reflected to some $γ \in 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} \land Σ_{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 $≺ -, - ≻ : ω \times ω ⟶ ω$ be a bijective recursive pairing function. Our assumptions imply that $h_{β}^{1}$ “ $ω \times (ω \cup {p}) = L_{β}$ . (Here $h = h_{β}^{1}$ is the standard – and uniformly defined – $Σ_{1}$ -skolem function for all limit $L_{β}$ ). Suppose $φ [x] \equiv \forall u \exists v \forall w ψ (u, v, w, x)$ for some $x \in L_{β}$ is a non-reflecting $Π_{3}$ -formula, chosen so that $L_{β} ⊧ φ [x]$ . This is equivalent to: $\begin{array}{l} (+) & \forall ≺ n, i ≻ < ω \exists α [h (i, n, p) ↑ \lor \exists v \in L_{α} \forall w ψ (h (i, n, p), v, w, x)] \end{array}$

holding in $L_{β}$ . Let $\begin{array}{l} G (≺ n, i ≻) & = the least α such that \exists v \in L_{α} \forall w ψ (h (i, n, p), v, w, x), if h (i, n, p) ↓ \\ = 0, if h (i, n, p) ↑ . \end{array}$ Then G is ${(Π_{2} \land Σ_{2}^{})}^{L_{β}} {p}$ – the ‘leastness of α’ requirement contributing a $Π_{2}^{L_{β}}$ clause: $\begin{matrix} \forall α^{'} < α \forall v \in L_{α^{'}} \neg \forall w ψ ((h (i, n, p), v, w, x)) . \end{matrix}$ We claim that for any limit $β^{'} < β$ with $x \in 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}$ “ $ω \times (ω \cup {p}) = L_{β^{'}}$ (although for those $h_{β}^{1} (i, n, p) \in 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_{β^{'}} ⊧$ “ $\forall ≺ \bar{n}, i ≻ ⩽ n^{'} (≺ \bar{n}, i ≻ \in dom (G))$ ”. Then for appropriate $β^{'} < β$ we must have $n (β^{'}) < ω$ , whilst $n (β) = ω$ .
Lemma 2.3.
${Liminf}_{β^{'} \to β} n (β^{'}) = ω$ , and $G {(≺ \bar{n}, i ≻)}^{L_{β^{'}}} ⟶ G {(≺ \bar{n}, i ≻)}^{L_{β}}$ .
Proof.
As $β^{'} \to β$ the value of $G {(≺ \bar{n}, i ≻)}^{L_{β^{'}}}$ eventually settles to the final value $G {(≺ \bar{n}, i ≻)}^{L_{β}}$ . To see this note that for a given $β^{'} < β$ the fact that $\forall v \in L_{β^{'}} \neg \forall 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 \in L_{β}$ and $φ [x] \equiv \forall u \exists v \forall 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} \land Σ_{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 \subseteq ω$ .

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}_{β^{'} \to β} 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} (τ) \in On, C_{δ}^{k} (τ) < 2$ (now for the δ’th cell of tape $T^{k} =_{df} {⟨ C_{δ}^{k} ⟩}_{δ \in 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} \in 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 \subseteq α$ 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 $τ \in C$ . We then just concentrate on $r^{1} \in 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} (τ) \in Lim$ and $R^{1} (τ + 1) < R^{1} (τ)$ (“no further going left at limit cells”).

Case 1 $\exists τ_{0} < α \forall τ \in (τ_{0}, α) R^{1} (τ) < ρ$ .

If $ρ < α$ then we can assume that $ρ < τ_{0}$ . In any case, by definition $ρ = {Liminf}_{τ \to α} R^{1} (τ)$ , so we have that ρ under our case hypothesis can be defined as: $\begin{matrix} y = ρ ⟷ \forall z < y \exists τ_{z} \forall τ \in (τ_{z}, α) (y > R^{1} (τ) > z) . \end{matrix}$

By $Π_{3}$ -reflection there is an admissible $β < α$ with $τ_{0} < β \land \forall τ \in (τ_{0}, β) R^{1} (τ) < ρ$ and also $\begin{matrix} \forall z < ρ \exists τ_{z} \forall τ \in (τ_{z}, β) (ρ > R^{1} (τ) > z) . \end{matrix}$

(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 $\forall τ_{2} \in (τ_{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 $\bar{α}$ . We’ve remarked above that we can assume by $Π_{2}$ reflection at the admissible α that there is a closed unbounded set $C \subseteq α$ of $\bar{α}$ , with $I (\bar{α}) = I (α) = s$ , and $R^{k} (\bar{α}) = 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 $\forall τ_{2} \in (τ_{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 $τ^{'} \in E_{0}$ where $E_{0}$ reflects (i) alone. Again the conditions for halting at α are reflected to any $\bar{α} \in 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] \equiv \forall u \exists v \forall 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} \land Σ_{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} = \emptyset$ . 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

For single head OTMs the situation is more subtle: there are some admissible ordinals that are not $Π_{3}$ -reflecting but which nevertheless start gaps. One may even ask:

Question 3.
Is $ω_{1}^{ck}$ clockable by a one head multi-tape OTM program?

Note that the ITTM argument of [15] which shows that $ω_{1}^{ck}$ is not clockable does not apply, since although there the machine has one head, we have diverged from their limit rules. The argument above, directly appealing to the non- $Π_{3}$ -reflection at $ω_{1}^{ck}$ , or alternatively that of Carl [8] where ITRMs (which do clock the $ω_{n}^{ck}$ ’s) are simulated on OTMs, both are with multiple heads and tapes, and thus do not apply either. We shall answer this question below.

As multihead machines subsume single head ones we have, as a corollary to Thm. 2.1(ii):
Corollary 2.9.
Let γ be $Π_{3}$ -reflecting. Then γ is not clockable by a single head OTM. Hence such γ either start a gap, or are interior to one.

We now characterise the rest of the ordinals that start gaps. Some admissible ordinals that are non- $Π_{3}$ -reflecting are clockable, some are not. Let $E^{}$ be the set of limit points of E the class of $Σ_{2}$ -extendibles.
Theorem 2.10.
Let γ be admissible, but not* $Π_{3}$ -reflecting. Suppose γ is a supremum of halting times for single head OTMs. Then $\begin{matrix} γ is clockable ⟷ γ is not a limit of Σ_{2} -extendibles. \end{matrix}$

Hence the class of such γ which start gaps consists of precisely those γ in $E^{}$ .
Proof.
Let γ be as assumed: admissible, but not $Π_{3}$ -reflecting, and a supremum of halting times for single head OTMs. Consider, as for ITTMs, the example case of an OTM with a single R/W head at position $R (τ)$ at time τ, but three tapes enumerated ${⟨ C_{α}^{k} ⟩}_{α \in On}$ for $k < 3$ with content at time τ ${⟨ C_{α}^{k} (τ) ⟩}_{α \in On}$ . As for ITTMs we envisage the head reading at any moment simultaneously a triple ${⟨ C_{α}^{k} ⟩}_{k < 3}$ .

$(⟶)$ We assume that γ is both a limit of extendibles and is clockable for a contradiction. At time γ let $I (γ) = i < ω$ . As above by $Π_{2}$ -reflection there is a closed and unbounded $C \subseteq γ$ with $I (δ) = i$ for $δ \in C$ . In the argument that follows, the main case is when the position of the head at time γ, here called ρ once more, is at neither extreme of 0 or γ. The dynamics of head movement allied with the limit rules will ensure this ρ cannot be a successor ordinal; coupled with the admissibility of γ, it cannot be a limit of limit ordinals. We then shall deduce that from some point onwards it is behaving isomorphically to an ITTM, in that it is restricted to an ω-sequence of cells $[\bar{ρ}, \bar{ρ} + ω)$ where $\bar{ρ} + ω = ρ$ . Then the assumption that γ is a limit of extendibles plays its role.

Case 1* $ρ = γ$ .

Then the R/W head is reading the three cells $C_{γ}^{k} (γ) = 0$ for each of $k < 3$ for the first time. This is $Π_{2}$ -expressible (“ $\forall δ \exists τ R (τ) ⩾ δ$ ”) and so reflects to an $α \in C$ , with $C_{α}^{k} (α) = 0$ ( $k < 3)$ and the conditions for halting are there at time α – a contradiction.

Case 2 $0 < ρ < γ$ .

Then there is some $τ_{0} < γ$ so that for all $τ \in (τ_{0}, γ)$ , if $R (τ) \in Lim$ , then $R (τ + 1) ≮ R (τ)$ (“No going left at a limit”). In particular this implies that we have just the two alternatives:

Either: $\exists τ_{0} < γ \forall τ \in (τ_{0}, γ) R (τ) \in [ρ, ρ + ω)$ . By an additional $Π_{2}$ -reflection clause then (using $τ_{0}$ as a parameter for example), there is a closed and unbounded set $D \subseteq C \subseteq γ$ with $τ \in D ⟶ R (τ) = ρ$ . Similarly there is an unbounded set $B \subseteq D$ to which the pattern $C_{ρ}^{k} (γ)$ for $k < 3$ reflects as $C_{ρ}^{k} (α)$ for $α \in B$ , and for which the conditions for halting are present. Contradiction.

Or: $\exists τ_{0} < γ \forall τ \in (τ_{0}, γ) R (τ) < ρ$ . Note ρ cannot be a successor ordinal. Nor can it be a compound limit. For, let $ρ_{n} < ρ_{n + 1}$ be an increasing sequence of limit ordinals with supremum ρ and with ${⟨ ρ_{n} ⟩}_{n} \in L_{γ}$ . As $R (γ) = ρ$ , for each n there is a least $τ_{n} > τ_{0}, ρ$ so that $R (τ_{n}) ⩾ ρ_{n}$ . On the one hand $n ↣ τ_{n}$ is a total $Σ_{1}^{L_{γ}} ({{⟨ ρ_{n} ⟩}_{n}, τ_{0}})$ definable function, but on the other if $\tilde{τ} = {sup}_{n} τ_{n}$ , then $R (\tilde{τ}) = ρ$ (here we are implicitly using that $ρ > 0$ to say $τ^{'} > τ_{n} ⟶ R (τ^{'}) ⩾ R (τ_{n})$ ). However our case hypothesis implies that $\tilde{τ} = γ$ – a contradiction to the admissibility of γ.

We are thus left with $ρ = \bar{ρ} + ω$ with $Lim (\bar{ρ})$ . Then $\exists τ_{0} < γ \forall τ \in (τ_{0}, γ) R (τ) \in [\bar{ρ}, \bar{ρ} + ω)$ . However then the program and OTM are behaving, within this interval of time, exactly as for an ITTM (with Liminf rules for the position of its R/W head of course) but working on the ω sequence of cells $[\bar{ρ}, \bar{ρ} + ω)$ rather than $[0, ω)$ . But now if $ξ > τ_{0}, ρ$ is the least $Σ_{2}$ -extendible, with $L_{ξ} ≺_{Σ_{2}} L_{σ}$ , this version of an ITTM will enter a final loop at time ξ (as halting at a time $γ^{'} < ξ < γ$ is ruled out). But γ is a limit of $Σ_{2}$ -extendibles, so $ξ < σ < γ$ . (If $ρ < ξ < γ < σ$ , as γ is posited a limit of extendibles there would be a further $ρ < ξ < ξ^{'} < σ^{'} < σ$ and $ξ^{'} < γ$ . But by $Σ_{1}$ -reflection applied in $L_{σ}$ to the pair $(ξ^{'}, σ^{'})$ there would be in any case another extendible pair $(ξ^{″}, σ^{″})$ in $L_{ξ}$ with $ρ < ξ^{″} < σ^{″} < γ$ as required.) So in fact the OTM will also loop rather than halt. Another contradiction.

Case 3 $ρ = 0$ .

If $\exists τ_{0} < γ \forall τ \in (τ_{0}, γ) R (τ) \in [0, ω)$ then this is argued as in Case 2 (indeed it is just another example of the ‘Either’ clause of Case 2). But $ρ = R (γ)$ could be 0 because for arbitrarily large $δ < γ$ we “went left at a limit”: $R (δ) \in Lim$ , $0 = R (δ + 1) < R (δ)$ . This is $Π_{2}$ -expressible. By the Liminf rule this means there is a closed and unbounded set C of δ below γ with $R (δ) = 0$ . So again by reflection there is an earlier $τ \in C$ with $R (τ) = 0$ , and arguing as above, with pattern match-up: $C_{0}^{k} (γ) = C_{0}^{k} (τ)$ for $k < 3$ . Again we have the conditions for halting at this τ, a contradiction. This ends the proof of (⟶). □

$(⟵)$ Assume γ is not a limit of extendibles and we shall show γ is clockable. Let $δ_{0}$ be the largest extendible, or limit of such, less than γ. As γ is a limit of clockables, there is $δ \in (δ_{0}, γ)$ and some $f, k$ so that $P_{f} (k) ↓^{δ}$ . This is a new $Σ_{1}$ -fact true in $L_{δ + 1}$ . This implies by standard constructibility theory, that $L_{δ + 2} ⊧$ “ $V = HC$ ”. Let $x_{δ} \in L_{δ + 2} \cap WO$ be the L-least code for δ. We describe a single head 3-tape OTM procedure.

(1) The Koepke L-machine runs constructing levels of L until it is seen that there is a level of L witnessing $P_{f} (k) ↓^{δ}$ , and then $x_{δ}$ is found. The discovery of $x_{δ}$ is a signal to advance to the rest of the main process. From this point onwards, thus some $τ_{0}$ onwards, $R (τ) \in [0, ω)$ , i.e. the process will be confined to just the first ω many cells of each tape. Only at time γ shall we have $R (γ) = ω = {Liminf}_{τ \to γ} R (τ)$ . At this point there will be flags, in other words a cell configuration, in ${⟨ C_{0}^{k} ⟩}_{k < 3}$ , which we can place there now, which will program an immediate halt, thus demonstrating the clockability of γ. Also at this point $τ_{0}$ we can write $x_{δ}$ to the first ω cells of the input tape, whilst those of the Scratch and Output tapes are reset to zeroes. After these preliminaries we proceed to:

(2) apply the notation of Lemma 2.2 above, which provided a cofinal function $G : ω \to γ$ which was ${(Π_{2} \land Σ_{2}^{})}^{L_{γ}}$ but so that for any $β < γ$ , $G^{L_{β}}$ was not a total function. (We note that no parameters are needed here, as by our assumption γ is the supremum of clockables $γ^{'}$ , and so the supremum of ordinals where new $Σ_{1}$ -facts become true. If $p_{γ}^{1} \neq \emptyset$ then, by standard arguments, we have that $L_{max p_{γ}^{1}} ≺_{Σ_{1}} L_{γ}$ and so there are no new $Σ_{1}$ -facts becoming true in the interval $(max p_{γ}^{1}, γ)$ .) We let $n (α)$ be as defined after that Lemma. We ensure whilst $n (α) = n_{0}$ say, that the program does not visit any cell $C_{t}^{k}$ for any $t < n_{0}$ . Since ${Liminf}_{α \to γ} n (α) = ω$ , this will ensure $R (γ) = ω$ as desired.

(3) In order to satisfy the workspace imposed by the insistence that we only use cells in $[n_{0}, ω)$ , we divide up the scratch tape of our master program via a (1-1) (ordinary) recursive function $π : ω \times 4 \times ω ⟶ Evens$ with the property that (i) $n < min {π (k, l, n) k < ω, l < 4}$ and (ii) $k < k^{'} ⟶ π (k, l, n) < π (k^{'}, l, n)$ . The reason for this choice is that we shall simulate an ω-sequence of ‘virtual machines’, $M^{n}$ , each with 4 tapes, thus: ${({⟨ C_{k}^{l} ⟩}_{l < 4, k < ω})}^{M^{n}}$ . Here ‘cell’ ${(C_{k}^{l})}^{M^{n}}$ of the simulation occupies cell $C_{π (k, l, n)}^{1}$ (in particular by (i) the ‘tapes’ of $M^{n}$ thus occupy real cells $C_{p}^{1}$ where $p > n$ ). That $r a n π \subseteq Evens$ is to leave the Odds ${⟨ C_{2 n + 1}^{1} ⟩}_{n < ω}$ free for scratch tape work of the master process. (Four tapes here is clearly unnecessary: we could recursively amalgamate the fourth tape and the output tape of $M^{n}$ and thus stick just with the usual three tapes.)

(4) Typically a process may involve searching through, or copying of, all the cells of an $M^{n}$ virtual tape. This could result in a Liminf value of the actual R/W head being an unwanted ω before its desired time. To obviate this we make otherwise redundant ‘insurance moves’: after a fixed number, say $10^{6}$ , of steps in this searching process being run by $M^{n}$ , the master process places a mark and current instruction number of the simulated process of $M^{n}$ at its current position, and returns the R/W head to the first quadruple of cells ${({⟨ C_{0}^{k} ⟩}_{k < 4})}^{M^{n}}$ that is to the initial group of virtual cells at the beginning of $M^{n}$ ’s virtual tape. As noted at the end of (3), this still keeps the actual R/W head above the actual cells ${⟨ C_{n}^{k} ⟩}_{k < 3}$ . After doing this run down, it runs back up to the mark and retrieves the next instruction number and does another $10^{6}$ steps of the search process on the virtual machine $M^{n}$ etc. This way after ω steps of its task the R/W head is not at the ω’th position. We shall refer to this as ‘making insurance moves’ without further specification (or indeed mention).

The overall process

Idea: We define essentially a program so that with input the code $x_{δ}$ for δ, and using Liminf rules for Instruction numbers and R/W head positions (so once more to emphasise, not those rules of [15]), it will satisfy ${Liminf}_{β \to γ^{'}} R (β) = ω$ first when $γ^{'} = γ$ . (In essence one could regard this as an ITTM program.)

(I) Let us name one of the 4 of $M^{n}$ ’s ‘tapes’ $S_{}^{n}$ – the other three being as usual for an OTM. On the input tapes of each of the $M^{n}$ we write a copy of $x_{δ}$ . We shall run the ITTM theory machine TM from time to time on differing $M^{n}$ using as input $x_{δ}$ as a base. This builds for us the $L_{τ} [x_{δ}]$ -hierarchy over the real $x_{δ}$ in each $M^{n}$ . For mildly closed limit $τ > δ$ $L_{τ} [x_{δ}] ⊧$ “ $V = L$ ” and indeed $L_{τ} [x_{δ}] = L_{τ}$ . We shall reserve $S^{n}$ for accumulating Gödel codes of $Σ_{1}$ -sentences true in such $L_{τ}$ . This theory we denote $T_{τ}^{1}$ .

(II) We set $n (0) = 0$ and on $M^{0}$ we initiate TM as indicated on the content of its ‘input tape’. We run this up to some τ where $Lim (τ)$ and with $L_{τ} [x_{δ}] = L_{τ}$ and which has a theory $T_{τ}^{1}$ with new $Σ_{1}$ -sentences appearing unboundedly in τ; whilst this happens we also write at the same time $T_{τ}^{1}$ to $S_{1}^{0}$ . (All this involves appropriate insurance moves.) The Turing jump of $T_{τ}^{1}$ , ${(T_{τ}^{1})}^{'}$ is recursively isomorphic to the complete $Σ_{2}$ -theory of $L_{τ}$ , $T_{τ}^{2}$ . $M^{0}$ computes this, and ascertains $n (τ)$ from it. The master program then copies $T_{τ}^{1}$ from $S^{0}$ to $S^{n (τ)}$ – again using insurance moves. This describes ‘Round 0’.

(III) Assume that at the beginning of Round η ( $η < γ$ ) the R/W head is positioned at the beginning of the $M^{n (η)}$ ‘tape’, i.e. on the first of the quadruple of cells, so on ${(C_{0}^{0})}^{M^{n (η)}}$ of ${{(⟨ C_{0}^{k} ⟩}_{k < 4})}^{M^{n (η)}}$ .

(A) $M^{n (η)}$ then runs a copy of the TM from its input tape, $x_{δ}$ , until it sees all the $Σ_{1}$ -sentences on $S^{n (η)}$ instantiated; it continues to run TM until it reaches a further limit τ satisfying that new sentences in $T_{τ}^{1}$ appears unboundedly in τ. These new sentences are added to $S^{n (η)}$ as they appear. Thus $S^{n (η)}$ becomes $T_{τ}^{1}$ . From this we compute a possibly new value $n (η + 1)$ (as at (II)).

(B) The master process copies $S^{n (η)}$ to $S^{n (η + 1)}$ . This requires insurance moves; but after this is done the R/W head is placed on ${(C_{0}^{0})}^{M^{n (η + 1)}}$ of ${{(⟨ C_{0}^{k} ⟩}_{k < 4})}^{M^{n (η + 1)}}$ and the procedure returns to (A).

Note: At no point during (A) does the R/W head drop lower down on the master tape below the cell which is ${(C_{0}^{0})}^{M^{n (η)}}$ , and during (B) below the cell which is ${(C_{0}^{0})}^{M^{n (η + 1)}}$ if $n (η + 1) < n (η)$ .

(IV) After a limit $λ < γ$ number of Rounds through (A) and (B), as ${lim inf}_{η \to λ} n (η)$ is still some finite number $n_{1}$ say, we shall have (a) a theory $T_{τ}^{1}$ written on $S_{1}^{n_{1}}$ ; and (b) by Liminf and insurance moves, the R/W head on ${(C_{0}^{0})}^{M^{n_{1}}}$ ; so we set $n (λ) = n_{1}$ and return to (A).

As $η \to γ$ more of the values $G^{L_{η}} (n)$ reach their final value of $G (n) =_{df} G^{L_{γ}} (n)$ , and so by Lemma 2.2 and the comment following, ${lim inf}_{η \to γ} n (η) = ω$ . This delivers $R (γ) = ω$ as desired. This ends the proof of $(⟵)$ ) and Theorem. □

Thus $ω_{1}^{ck}$ is, in particular, the halting time of a single head OTM. We leave the reader to verify that an inadmissible supremum of halting times is also a halting time. More generally we then have: Corollary 2.11.
For single head OTMs let γ be a supremum of halting times. Then: $\begin{matrix} γ starts a gap ⟷ γ is either Π_{3} -reflecting, or is an admissible limit of extendibles. \end{matrix}$

3. A question of Rin on δ-ITTMs

It is obvious that if one has an ITTM with an uncountable number of cells on the tape, e.g. an $ω_{1}$ -ITTM, then one cannot address all of the cells of the tape unless one allows ordinals parameters on the input tape of such machines: there are only countably many programs. Taking the hint about the uncountability of tape lengths causing unreachability through the scarcity of programs, we give a direct argument that globally characterises the category of tape lengths and their machines for which all cells can be reached.

We must turn then to considering computations in the class of functions computable by a δ-ITTM without parameters. We shall denote here the class of such machines by δ-ITTM₀. It is reasonable to require a modest amount of closure on the length δ of the three tapes: we take here closure under primitive recursive set functions (although weaker systems would suffice). This ensures that δ is closed under Gödel pairing.

Theorem 3.1.
Every cell can be reached by a δ-ITTM ₀ computation if and only if during a run of a program, a wellorder of ω appears on (one of) its tape(s) at some stage, which has order type δ.

Note: the requirement is not that the wellorder must be output by the machine, (although we see that it can be) but only that it appears at some point during the computation (in the description of Hamkins and Lewis [15], it is ‘accidental’). There is thus some computation on a δ-ITTM₀ which sees, even if temporarily, that ‘δ is countable’. For δ-ITTM₀ machines, Rin defines $λ_{0} (δ), γ_{0} (δ), ζ_{0} (δ)$ etc. by analogy with the ordinals for ITTMs, again see [15], which we should call here $λ_{0} (ω), γ_{0} (ω), ζ_{0} (ω)$ ... (Note that there is no difference between functions ω-ITTM₀ computable and ω-ITTM computable, since any cell number ‘n’ that could be used as a parameter, is readily definable.)
Definition 3.2.
$λ_{0} (δ) = sup {‖ y ‖ : y \subseteq ω, y \in WO \land y$ is the output of a halting δ-ITTM₀ program}. $\begin{matrix} Σ_{0} (δ) = sup {‖ y ‖ : y \subseteq ω, y \in WO \land y appears at some stage on some tape of a δ {-ITTM}_{0} program} . \end{matrix}$

We shall have also to consider the standard class of machines with length of tape δ: we’ll write these without the zero subscript to indicate that parameters are allowed. For example the definition of accidentally writable wellorders appearing on such computations reads:
Definition 3.3.
$Σ (δ) = sup {‖ y ‖ : y \subseteq ω, y \in WO \land y$ appears at some stage on some tape of a δ-ITTM program}

We put to use primitive recursive closure of δ, as in the next example to divide up our scratch tape into δ many slices ${⟨ S_{α} ⟩}_{α < δ}$ with each $S_{α}$ of order type δ. On this array (call it S, and we’ll call the routine we describe next the S-routine) we write in δ steps, via a δ-ITTM₀ computation, in the β’th slice $S_{β}$ , a code for β (either as a real, or as a subset of another ordinal, or even just a β-string of 1’s followed by 0’s, for definiteness, let us say the latter). We arrange this in such a way that a head never moves left whilst on a limit cell, but it first goes back to $C_{0}$ when this routine is completed.

We shall use the S-routine as a prefix to a run of the δ-ITTM₀-universal program $U_{0}$ , in which one subcomputation actually simulates a run of the full δ-ITTM $_{}$ -universal program U: we may imagine, running $U_{0}$ , that we simulate all δ-ITTM programs on $ω \times δ$ many slices of a scratch tape initiating in turn all $U (e, τ)$ for some $e \in ω$ , and increasing in turn some parameter $τ < δ$ which we now have access to via $S_{τ}$ . Notice then that any real, (indeed, we remark for below, any subset of δ) that appears on some $U (e, τ)$ tape also appears coded on some subprogram of $U_{0}$ on the δ-ITTM₀ hardware. (And trivially also the converse.) Hence

(1) $Σ_{0} (δ) = Σ (δ) ⩾ δ$ .
Remark.
Thus the difference between δ-ITTM₀ and δ-ITTM-computations, taken as a class, is not that they reach different classes of sets or functions during computations, it is the ability to halt with, or output those results that creates a difference: e.g., an $f : δ ⟶ δ$ may appear, but if for δ-ITTM₀s the cell α cannot be reached, we may not, in general have access to $f (α)$ .
Proof of Theorem 3.1.
$(\Leftarrow)$ Assume δ-ITTM₀-machines cannot reach some least cell $C_{α_{0}}$ for some $α_{0} < δ$ .

(2) $λ (δ) ⩽ α_{0} < δ$ .

As Rin remarks (his Prop. 2.10): if a real coding β is writable then every cell $C_{β^{'}}$ for $β^{'} ⩽ β$ is addressable.This ends the proof of (2). □

(3) No function collapsing δ to ω appears on any δ-ITTM₀-computation.

Using the slices $S_{α}$ from the array S, or otherwise, we can in a δ-ITTM₀-computation build up a wellorder on $δ \times δ$ of order type δ. Thence wellorders of type $δ + δ$ , $δ \cdot ω, \dots$ So order types of length $> δ$ can appear on δ-ITTM₀-computation tapes. So suppose for a contradiction during a run of the universal δ-ITTM₀ computation some real $\bar{x} \in WO$ appears with $| \bar{x} | = δ$ . (Thus showing $Σ (δ) > | \bar{x} | = δ$ .) We arrange our run of this universal computation, so that whenever a real $x^{'} \in WO$ appears, we split off to a subroutine that runs, for example, a copy of the S-routine indexing its stages along the wellorder $x^{'}$ until either $x^{'}$ is exhausted or S is completed. If the former, it returns to the main computation; if the latter it HALT’s with output $x^{'}$ . However then $λ (δ) ⩾ | x^{'} | ⩾ δ$ , contrary to (2). This ends the proof of (3). □

$(\Rightarrow)$ For the converse assume δ is such that every cell can be reached by a δ-ITTM₀-program. During a run of U we build a wellorder E on a scratch tape: let $e (α)$ be that $e \in ω$ for which $P_{e}$ halts first with its head on $C_{α}$ . As we run U we set $\begin{matrix} n E m ⟺ \exists α < α^{'} (n = e (α) \land m = e (α^{'})) . \end{matrix}$

Then $E \in WO$ , and demonstrates that $δ ⩽ λ (δ)$ : it will be completed and is even writable, once all the relevant $P_{e}$ ’s have halted. As E collapses δ this direction and the theorem are complete. This ends the proof of Thm 3.1. □
Remark.
As [15] shows, if α appears (coded) on a tape, there is another computation with a code for $L_{α}$ appearing on a tape. Then, by absoluteness of computations to the L-hierarchy, we shall have:
Corollary 3.4.
Every cell can be addressed in the δ-ITTM ₀ -class if and only if $L_{Σ (δ)} ⊧$ “δ is countable”.

We close this section with a remark à propos the Introduction: with the formalism of constants in the language we can now formulate the theory of quasi-inductive definitions over the structure $(δ, <)$ or indeed over a δ-ITTM considered as a relational structure generalising Moschovakis in [24]. Without such we should be restricted (for these purposes) to structures satisfying the conditions of the last Corollary, which would be unnatural as well as undesirable.
4. Infinite time Blum–Shub–Smale machines

This section seeks to show that the strength of IBSSMs equipped with a Liminf (in the Euclidean metric) rule for the register contents, rather than the original continuity requirement used in [21] allows, unsurprisingly, for much greater computational power. It is perhaps more surprising that ITTMs can be simulated on such a machine, so they have the latter’s power at least. It is easy then to see that the power is exactly that of ITTMs: since ITTMs can construct L and as IBSSMs computations, on rational input, are absolute to L, the latter can compute no more than the former.

We assume an IBSSM program $B_{e}$ with registers $R_{0}, R_{1,} \dots,, R_{n}$ . B has finitely many instructions $I_{0}, \dots, I_{k}$ . We suppose that at time α the instruction number in the enumeration of the flow diagram of $B_{e}$ about to be effected is $I (α$ ); again at limit times λ, we set $I (λ)$ to be $l = {lim inf}_{β \to λ} I (β)$ as in [21].

Definition 4.1.

Let $R_{i} (α) \in R$ be the real contents of register $R_{i}$ at time α.

We shall assume, wlog, that a real is expressed by its decimal expansion. At limit stages of time λ $R_{i} (λ) =_{df} {Liminf}_{α \to λ} R_{i} (α)$ . (If this Liminf becomes infinite we make some other decision, for sake of definiteness, allow the machine to crash.) Assume we start with 0.0’s (or rationals) in all registers. Note that for any limit λ, $i ⩽ n$ , $u = ⟨ R_{i} (γ) γ < α ⟩$ is $Σ_{1}^{L_{λ}} ({α})$ for any $α < λ$ . Let $(ζ, Σ)$ be as defined for ITTMs.

Lemma 4.2.

$R_{i} (ζ) = R_{i} (Σ)$ , and $B_{e}$ has either halted or, as for ITTMs, starts looping by at most stage ζ.

Proof.

We let $Q^{n}$ be the collection of rationals whose decimal expansion is of the form $0 . r_{1} r_{2} \cdot r_{n} 00000$ . Let $s_{n}^{i} (α) \in Q^{n}$ be the rational approximation whose expansion is the first n digits of $R_{i} (α)$ . We’ll simplify the discussion by assuming that a) we discuss only $R_{0}$ throughout and b) $R_{0} (α) \in [0, 1)$ . Towards this end we first define for limit ordinals λ: $\begin{matrix} I^{+} (t, n, λ) ⟷ t \in Q^{n} \land \forall α < λ \exists β \in (α, λ) (t > R_{0} (β) \land t - R_{0} (β) ⩽ 10^{- n}) . \end{matrix}$ If $R_{0} (λ) ↓$ (that is, is less than $\infty)$ ) then $\exists t \forall n I^{+} (t, n, λ) \neq \emptyset$ . Let $s_{n, λ}^{+} = min {t I^{+} (t, n, λ)}$ . Then $s_{n, λ}^{+} = y ⟷ y \in I^{+} (t, n, λ)} \land y - 10^{- n} \notin I^{+} (t, n, λ)}$ . Hence $s_{n, λ}^{+}$ is $Π_{2} \land Σ_{2}$ definable.

Claim.

$s_{n, λ}^{+} - 10^{- n} ⩽ s_{n}^{0}, R_{0} (λ) ⩽ s_{n, λ}^{+}$ .

Proof of Claim.

To avoid too much clutter, we set $s = s_{n}^{0} (λ)$ and $s^{+} = s_{n, λ}^{+}$ . We divide into two cases depending on how the liminf value at $R_{0} (λ)$ can be approached.

Case 1 $R_{0} (λ)$ is a simple limit from below of a subsequence $⟨ R (α_{ι}) ι < τ ⟩$ for some τ with ${⟨ α_{ι} ⟩}_{ι < τ}$ cofinal in λ.

Case 1a) $R_{0} (λ) = s$ . Then one can check that our definitions imply that $s^{+} = s$ and $s^{+} = R_{0} (λ) > s^{+} - 10^{- n}$ .

Case 1b) $R_{0} (λ) > s$ . Then $s^{+} > R_{0} (λ) > s^{+} - 10^{- n} = s$ .

Hence in both subcases we have $s^{+} ⩾ R_{0} (λ) > s^{+} - 10^{- n}$ with the equality holding if and only if $R_{0} (λ) = s$ .

Case 2 The sequence $⟨ R_{0} (α) ⟩$ for $α < λ$ approaches $R (λ)$ purely as a liminf from above (i.e. from some point on, no $R_{0} (α)$ is less than $R_{0} (λ)$ ).

Then, similar to the first case, $s^{+} > R_{0} (λ), s ⩾ s^{+} - 10^{- n}$ , with $R_{0} (λ) = s^{+} - 10^{- n}$ holding if and only if $R_{0} (λ) = s$ . This ends the proof of the Claim. □

From the Claim it follows that $\begin{array}{l} (*) & \forall λ, λ^{'} [\forall n (s_{n, λ}^{+} = s_{n, λ^{'}}^{+}) ⟶ R_{0} (λ) = R_{0} (λ^{'})] . \end{array}$

If we imagine the computation proceeding by a recursion within the L hierarchy then we shall have that $R_{0} (β)$ is a real definable over $L_{β}$ , by using, for example, the set of rational approximations ${s_{n, β}^{+}}_{n < ω}$ . As $L_{ζ} ≺_{Σ_{2}} L_{Σ}$ we shall have for any $n, t$ that $I (t, n, ζ) ⟷ I (t, n, Σ)$ and thus $s_{n, ζ}^{+} = s_{n, Σ}^{+}$ . But then $R_{0} (ζ) = R_{0} (Σ)$ by (∗) above. Identical arguments hold for the other registers $R_{i}$ . Also then by another straightforward application of $Σ_{2}$ -reflection we have that $R_{i} (γ) ⩾ R_{i} (ζ)$ for all $γ \in [ζ, Σ]$ .

These facts imply that no Liminf smaller than $R_{i} (ζ)$ can ever appear in $R_{i}$ at a later part of the computation, and the computation is looping. (This can also be seen by observing the $B_{e}$ computation coded inside the ITTM-theory machine – see below.) This ends the proof of Lemma 4.2. □

The harder part is the lower bound. A natural attempt is to somehow define an ITBSS program that continuously runs producing (reals coding) the theories of successive levels of the L-hierarchy much as in [12]. In, e.g., [34] at Theorem 11 we stated how one might produce successive Turing jumps for any $α < ω^{ω}$ on the continuity-IBSSMs. That however required one to know in advance how long a hierarchy was involved. In [12] the ITTM runs continuously irrespective of any fixed length, and indeed loops forever, deliberately so. It would seem difficult (but presumably not impossible in view of the sequel) to formulate this directly as an IBSSM. Instead we show how to simulate an ITTM computation $P_{e} (0)$ directly on an IBSSM as some $B_{\bar{e}} (0.0)$ .

The obvious first, and really only, hurdle if we don’t know how long the computation is intended to run, is how to keep a record of the infinite tape contents. Indeed, since the rest of the ITTM’s actions are simple effects from its state-transition table, which are easily simulable as IBSSM actions, keeping the ITTM cell tape’s contents is the main difficulty. It is easy to see what goes wrong with a too-simple approach: suppose one has a real with a decimal expansion 0.1101... with a 1 in the k’th position iff $C_{k}$ contains a 1; suppose before stage ω cells $C_{0}$ and $C_{1}$ have both changed value infinitely often, but so that at no finite stage are they both 0, then by the ITTM-Liminf rule $C_{0} (ω) = C_{1} (ω) = 0$ . But the IBSSM-Liminf rule applied to the sequence of reals as decimals of the form $0.10 xxx$ $0.01 xxxx$ always with a 1 in the first or second position, yields a liminf of $0.01 xxx$ rather than the intended $0.00 xxxxx$ .

So instead we use not just one, but an infinite number of places in the real’s expansion to code the correct cell contents of e.g., $C_{0}$ .

Let $π : ω \times ω \leftrightarrow ω$ be a recursive bijection. Let $H_{i} = {n \exists k π (⟨ i, k ⟩) = n}$ . Let $h_{i} : ω ↠ H_{i}$ be the, also recursive, strictly increasing enumeration of $H_{i}$ . We use $H_{i}$ to record information about $C_{i}$ . Suppose w.l.o.g. we initiate the ITTM-computation $P_{e} (0)$ on zero input with zeros in every cell. In the sequel, $r (α)$ denotes the real that is in $R_{0}$ at time α. We start the IBSSM-simulation $B_{e} (0.0000 \dots)$ by placing a real $r (1) \in [0, 1)$ in the register $R_{0}$ whose decimal expansion has 0 everywhere except for the $h_{i} (0)$ position for each $i < ω$ , where it has instead a 1. ( $r (1)$ thus has at time $t = 1$ , infinitely many 1’s in its expansion.)

The idea is that at stage α $C_{i} (α)$ equals a zero (or one) iff there is an even (resp. odd) number k with the $h_{i} (k)$ ’th position a 1 in the decimal expansion of $r (α)$ . For this to work at every moment in time α, each of the $H_{i}$ sets will have at most one 1 at its corresponding point in $r (α$ ). Otherwise the positions in $H_{i}$ are all 0.

∙ Note first that given a real r in $R_{0}$ , there are IBSSM-operations that first check whether r is conformable to a code for the whole tape $\vec{C_{i}}$ ; if so it can then read off whether $C_{i}$ is zero (or one), as coded into r: this involves computing whether r has in its expansion a 1 at position $h_{i} (2 k)$ (or at $h_{i} (2 k + 1)$ ). These latter checks merely involve calculations of the recursive function π, multiplications and divisions by powers of 10 etc., and can be programmed into a subroutine of the IBSSM $B_{e}$ ’s flow diagram. (Here and later we leave all this as an exercise for the reader).

∙ Secondly, suppose at time α we have $C_{i} (α) = 1 \neq C_{i} (α + 1)$ . There is thus a change in the value of $C_{i}$ initiated by the ITTM $P_{e}$ . We effect the following change on $r (α + 1)$ : we move the current 1 in its expansion, at some position of the form $h_{i} (2 k + 1)$ to position $h_{i} (2 k + 2)$ , and the $h_{i} (2 k + 1)$ ’th position in what will be $r (α + 2)$ reverts back to 0. Again these changes to $r (α + 1)$ in $R_{0}$ can be effected by simple IBSSM programmable arithmetic. (For $C_{i} (α) = 0 \neq C_{i} (α + 1)$ we make similar changes mutatis mutandis.)

The reader may wish to e.g., consider what happens to just cells $C_{0}$ and $C_{1}$ at some limit stage λ in $P_{e}$ . Suppose $C_{0}$ changes value cofinally often below λ but all other cells are fixed from some point α onwards below λ: each time there is a change a 1 gets pushed down a further stage in the $H_{0}$ -numbered positions to the right, thus decreasing the real in $R_{0}$ at least in terms of the values at the positions in $H_{0}$ . After infinitely many such moves to the right, when we consider $r (λ) = {Liminf}_{β \to λ} r (β)$ , this will be simply the real $r (α)$ but with all of the $H_{0}$ positions now set to zero. This corresponds to having in the ITTM-computation the Liminf operation setting $C_{0} (λ)$ to 0. To mirror this, at stage $λ + 1$ we simply modify the real $r (λ)$ in $R_{0}$ by just resetting the $h_{0} (0)$ ’th decimal position to a 1 (just as we initially did for $r (1)$ ) ready for any further changes at $C_{0} (γ$ ) for $γ > λ$ , that may occur (and leave all else alone).

Suppose $C_{1}$ alters infinitely often below λ as well. Then all the $H_{1}$ positions in the Liminf real $r (λ)$ have become 0 also. As before $r (λ + 1)$ is calculated so that the $h_{1} (0)$ position contains a 1.

However now note the relative independence of the IBSSM Liminf operation: making these infinitely many changes to r caused by the changes of $C_{0}$ followed afterwards by infinitely many changes to r, caused by those of $C_{1}$ sequentially, (all other cells being kept constant) results in the same Liminf real as if the changes to $C_{0}$ and $C_{1}$ had happened concurrently. If before a limit λ only finitely many changes have occurred in $C_{j}$ since there was last a 1 at position $h_{j} (0)$ , then $C_{j} (λ) = C_{j} (β)$ where the last change occurred at time β. This 1 is then preserved into the Liminf $r (λ)$ .

∙ Thus, to sum up, at any limit stage λ after $r (λ) = {Liminf}_{α \to λ} r (α)$ has been set, $B_{e}$ then inspects each of the $H_{i}$ sets in the expansion of $r (λ)$ in turn, and if $ran (h_{i})$ has no 1 in its range, then it calculates $r (λ + 1)$ so that $h_{i} (0) = 1$ ; it does this for each $i < ω$ in turn (possibly using further registers as scratch area). As before these are IBSSM-calculable arithmetic operations.

∙ A record of the head position of $P_{e}$ can be recorded in a register $R_{2}$ of $B_{e}$ : if this R/W head of $P_{e}$ is over the triple of cells $C_{3 k}, C_{3 k + 1}, C_{3 k + 2}$ then set $R_{2}$ to $\frac{1}{k}$ (for $k > 0$ , for $k = 0$ let $R_{2}$ be 0). Then if our model of ITTM computation replaces the R/W head to the beginning of its tape at each limit stage, we can set further flag registers to alert us to limit stages in the $P_{e}$ computation, in order to register this fact in $R_{2}$ .

This finishes (modulo some other programming details of no great interest) the simulation of $P_{e} (0)$ as some $B_{e} (0)$ .

Corollary 4.3.

The ITTM- and IBSSM-models are “bi-simulable”.

We have just prescribed a computation $B_{\bar{e}} (0.00 \dots)$ from $P_{e} (0)$ . But any given $B_{f} (0)$ can be run recursively inside the L-hierarchy, with a snapshot of its α’th stage definable over $L_{α}$ . However the theory machine of [12] constructs levels of the hierarchy, and their theories, for $α < Σ$ . It can thus decode the action of $B_{f}$ and find the sequence of snapshots of $B_{f}$ . This provides a way of emulating $B_{f}$ in some ITTM computation $P_{f^{'}}$ . □

Corollary 4.4.

There is a universal IBSSM.

Proof.

Every IBSSM program can be simulated on an ITTM. Because there is a universal ITTM program U say, and in turn this program can be simulated on an IBSSM as discussed above, we can design a universal IBSSM that decodes from the simulation of U on an IBSSM as described above, the action of any desired $B_{e} (k)$ for any IBSSM-program index e. □

Now we have such a result, we can take over into the Liminf-IBSSM many of the results and ideas from ITTM-theory. (For example we now know the sup of the IBSSM clockable or writable or eventually writable ordinals.)

We then have:

Corollary 4.5.

For IBSSM with the lim infrule, then the set Z of reals on which an IBSSM computation (on rational input) is convergent, is precisely the set Zof those reals in $L_{ζ}$ .

A convergent computation (on rational input) is one in which a designated register, e.g. $R_{0}$ has a final settled value from some point onwards. It would be of interest to find questions or properties more in the geometric/Euclidean flavour of the BSS-idea.

Let $T$ be the n-dimensional torus obtained as ${[0, 1)}^{n}$ (with 1 identified with 0). Let f be a continuous or effective function, $f : T \to T$ . Let $f^{α}$ be the α’th iterate of f. Here $f^{α + 1} (x) = f (f^{α} (x))$ , whilst $f^{λ} (x) = {lim inf}_{β \to λ} f^{β} (x)$ if $Lim (λ)$ . By the above an IBSSM can compute $f^{α} (x)$ for any $x \in R$ . Let $O = {p \in T \exists α (f^{α} (p) = 0)}$ ( $O$ is the ‘origin set’, the set of points that at some iterate of f get sent to the origin 0). One may show the following.

Theorem 4.6.

$Π_{3}^{1}$ - ${CA}_{0}$ proves the existence of the set $O$ . $Π_{2}^{1}$ - ${CA}_{0}$ is insufficient.

Theorem 4.7.

Let $τ_{f} = sup {α \exists p \in T (f^{α} (p) = 0) but \forall β < α (f^{β} (p) \neq 0)}$ , for recursive f. Then

(i) $τ_{f} ⩽ λ$ .

(ii) There exists a recursive f that attains this bound.

This is just a sample of possible properties from topological dynamics that are open to investigate when defined with transfinite actions.

References

Aczel and

Richter, Inductive definitions and analogies of large cardinals, in: Conference in Mathematical Logic London 70,

Hodges, ed., Lecture Notes in Mathematics, Vol. 255, Springer, 1971, pp. 1–9.

K.J.

Barwise, Admissible Sets and Structures, Perspectives in Mathematical Logic, Springer Verlag, 1975.

Beckmann,

Buss and

S.-D.

Friedman, Safe recursive set functions, J. Symbolic Logic 80(3) (2015), 335–369. doi:10.1017/jsl.2015.26.

Beller and

Litman, A strengthening of Jensen’s □ principles, Journal of Symbolic Logic 45(2) (1980), 251–264. doi:10.2307/2273186.

Burd, The Speed of an Infinite Computation, Master’s thesis, Rutgers, 1984.

J.P.

Burgess, The truth is never simple, Journal of Symbolic Logic 51(3) (1986), 663–681. doi:10.2307/2274021.

Carl, Ordinal Computability: An Introduction to Infinitary Machines, De Gruyter Series in Logic and Its Applications, De Gruyter, 2019.

Carl, Clockability for ordinal turing machines, in: Lecture Notes in Computer Science, Springer, 2020.

Carl,

Rin and

Schlicht, Writability and reachability for α-tape infinite time Turing machines, 2018, arXiv:1612:02982v1.

10.

Devlin, Constructibility, Perspectives in Mathematical Logic, Springer Verlag, Berlin, Heidelberg, 1984.

11.

A.J.

Dodd, The Core Model, London Mathematical Society Lecture Notes in Mathematics, Vol. 61, Cambridge University Press, Cambridge, 1982.

12.

S.-D.

Friedman and

P.D.

Welch, Two observations regarding infinite time Turing machines, in: Bonn Interational Workshop on Ordinal Computability,

Dimitriou, ed., Hausdorff Centre for Mathematics, University of Bonn, Bonn 2008, pp. 44–48, http://www.math.uni-bonn.de/ag/logik/events/biwoc/report.pdf .

13.

R.O.

Gandy, Set theoretic principles for elementary syntax, in: Axiomatic Set Theory,

Jech, ed., Proceedings of Symposia in Pure Mathematics, Vol. 13 II, American Mathematical Society, Providence, Rhode Island, 1974, pp. 103–126. doi:10.1090/pspum/013.2/0376348.

14.

Gupta and

Belnap, The Revision Theory of Truth, M.I.T. Press, Cambridge, 1993.

15.

J.D.

Hamkins and

Lewis, Infinite time Turing machines, Journal of Symbolic Logic 65(2) (2000), 567–604. doi:10.2307/2586556.

16.

J.D.

Hamkins and

Seabold, Infinite time Turing machines with only one tape, Mathematical Logic Quarterly 47(2) (2001), 271–287. doi:10.1002/1521-3870(200105)47:2<271::AID-MALQ271>3.0.CO;2-6.

17.

R.B.

Jensen and

Karp, Primitive recursive set functions, in: Axiomatic Set Theory,

Scott, ed., Proceedings of Symposia in Pure Mathematics, Vol. 13 I, American Mathematical Society, Providence, Rhode Island, 1971, pp. 143–167. doi:10.1090/pspum/013.1/0281602.

18.

S.C.

Kleene, Turing-machine computable functionals of finite type II, Proceedings of the London Mathematical Society 12 (1962), 245–258. doi:10.1112/plms/s3-12.1.245.

19.

S.C.

Kleene, Turing-machine computable functionals of finite type I, in: Proceedings 1960 Conference on Logic, Methodology and Philosophy of Science, Stanford University Press, 1962, pp. 38–45.

20.

Koepke, Turing computation on ordinals, Bulletin of Symbolic Logic 11 (2005), 377–397. doi:10.2178/bsl/1122038993.

21.

Koepke and

Seyfferth, Towards a theory of infinite time Blum–Shub–Smale machines, in: How the World Computes,

Cooper,

Dawar and

Löwe, eds, Lecture Notes in Computer Science, Vol. 7318, Spinger, 2012, pp. 405–415. doi:10.1007/978-3-642-30870-3_41.

22.

Löwe, Revision sequences and computers with an infinite amount of time, Journal of Logic and Computation 11 (2001), 25–40. doi:10.1093/logcom/11.1.25.

23.

Machover, The theory of transfinite recursion, Bulletin of the American Mathematical Society 67 (1961), 575–578. doi:10.1090/S0002-9904-1961-10696-4.

24.

Y.N.

Moschovakis, Elementary Induction on Abstract Structures, Studies in Logic Series, Vol. 77, North-Holland, Amsterdam, 1974.

25.

T.L.

Richardson, A Silver Machine approach to the Constructible Universe, PhD thesis, University of California, Berkeley, 1979.

26.

Rin, The computational strengths of α-tape infinite time Turing machines, Annals of Pure and Applied Logic 165(9) (2014), 1501–1511. doi:10.1016/j.apal.2014.04.016.

27.

Rogers, Recursive Function Theory, Higher Mathematics, McGraw, 1967.

28.

Simpson, Subsystems of Second Order Arithmetic, Perspectives in Mathematical Logic, Springer, 1999, p. 499.

29.

Takeuti, On the recursive functions of ordinal numbers, Journal of the Mathematical Society of Japan 12 (1960), 119–128. doi:10.2969/jmsj/01220119.

30.

P.D.

Welch, Eventually infinite time Turing degrees: Infinite time decidable reals, Journal of Symbolic Logic 65(3) (2000), 1193–1203. doi:10.2307/2586695.

31.

P.D.

Welch, On revision operators, Journal of Symbolic Logic 68(3) (2003), 689–711. doi:10.2178/jsl/1052669071.

32.

P.D.

Welch, Characteristics of discrete transfinite Turing machine models: Halting times, stabilization times, and normal form theorems, Theoretical Computer Science 410 (2009), 426–442. doi:10.1016/j.tcs.2008.09.050.

33.

P.D.

Welch, Discrete transfinite computation models, in: Computability in Context: Computation in the Real World,

S.B.

Cooper and

Sorbi, eds, Imperial College Press/World Scientific, 2010, pp. 375–414.

34.

P.D.

Welch, Discrete transfinite computation, in: Turing’s Revolution: The Impact of His Ideas About Computability,

Sommaruga and

Strahm, eds, Birkhäuser Verlag, Basel, 2015.

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

Abstract

Keywords

1. Introduction

1 We should like to thank Merlin Carl, Lorenzo Galeotti and Philipp Schlicht for conversations concerning some of the issues and arguments here.

2.1. Multiple head machines

References

¹
We should like to thank Merlin Carl, Lorenzo Galeotti and Philipp Schlicht for conversations concerning some of the issues and arguments here.