Lower bounds on β ( α ) and other properties of α -register machines

Abstract

This paper extends our paper (In Revolutions and Revelations in Computability. CiE 2022 (2022)) for the conference “Computability in Europe” 2022.

After Infinite Time Turing Machines (ITTM) were introduced in Hamkins and Lewis (Journal of Symbolic Logic65 (2000)), a number of machine models of computability have been generalized to the transfinite. While for some of these models the computational strength has been successfully determined, there are still several white spots on the map of transfinite computability. In this paper, we contribute to the understanding of the computational strength of transfinite machine models by (i) proving lower bounds on the computational strength of α-Infinite Time Register Machines (α-ITRMs) for certain values of α, refuting a conjecture about their strength made in (Annals of Pure and Applied Logic173 (2022)), (ii) showing that the computational strength of cardinal-recognizing ITRMs is equal to that of ITRMs and (iii) showing that non-solvability of the bounded halting problem, existence of a universal machine and an increase of computational power by allowing machines to recognize cardinals are equivalent for α-ITRMs for all relevant values of α.

Finally, we give some results indicating how the picture changes when the use of parameters is dropped or restricted.

Keywords

Ordinal computability Infinite Time Register Machines Gandy ordinals

1. Introduction

Ordinal computability studies generalizations of models of computability to the transfinite, thereby connecting set theory (in particular descriptive set theory and constructibility) and computability theory. The models of computability studied in ordinal computability include Infinite Time Turing Machines (ITTMs) (Hamkins and Lewis, [27]), Ordinal Turing Machines (OTMs) (Koepke, [32]), α-Turing Machines (Koepke and Seyfferth, [35]), α-ITTMs (Koepke, [33]), $(α, β)$ -ITTMs ([13,35]), weak and strong Infinite Time Register Machines ((w)ITRMs, Koepke [32], Koepke and Miller [34]), Ordinal Register Machines (Koepke and Syders [37]), α-(w)ITRMs (Koepke, [33]), $(α, β)$ -(w)ITRMs (ibid.), Infinite Time Blum–Shub–Smale-Machines (Koepke and Seyfferth, [36]), Surreal Blum–Shub–Smale-Machines (Galeotti and Nobrega, [23]), Ordinal λ-Calculus (Fischbach and Seyfferth, [22]) and Deterministic Ordinal Automata ([9]). Given this great diversity of models, one might be excused to utter the objection that, in contrast to classical computability theory with Turing computability as its central notion, this is a zoo rather than a model, and the area lacks coherence, thus significantly reducing the interest of results about such models.

Counter to this view, we offer the following perspective: Among the “maximal” models, with fully ordinalized resources, tape models, register models, λ-calculus etc. all lead to the same notion of computability, which coincides with constructibility (see, e.g., Fischbach [21]). The other models should be viewed as resource-bounded versions of this one, stable notion of computability, arising, e.g., by restricting the available time or the available space.1

¹
But also in other ways, for example, by stipulating that the content of a tape cell may only change finitely often.

They are then not analogous to Turing machines, but to complexity classes, which indeed form a “zoo” in the classical setting, albeit one very worthy of study. The main difference to the finitary case is that, in the transfinite, constant resource bounds, such as restricting the tape length to ω, lead to interesting and stable notions. But this is a feature, rather than a bug, of ordinal computability.

Another point of critique is that ordinal computability is focused too much on its different models rather than general topics of computability: one should rather look at concepts, rather than machines. To this, we reply that the growing literature on ordinal computability contains works, for example, on transfinite versions of degree theory ([28,45]), algorithmic randomness ([14,40]), computable model theory [29], Weihrauch reducibility [6,23], complexity theory ([5,20]) and realizability ([12]); and that it has fruitfully interacted with such areas as constructibility theory [31], descriptive set theory ([16,18]) and, recently, proof theory ([12,41]). Thus, there is no shortage of conceptual work, applications and interactions.2

⁴
That we allow the simultaneous comparison of two finite sequences, rather than just two, registers, has again technical advantages explained in [8], p. 2

are equal and otherwise proceeds with the next program line, (iv) an oracle command, which checks whether the content of some register is contained in the oracle and changes the content of that register to 1 if that is the case and otherwise to 0.5

⁵

Note that the “reset” command for replacing the content of a register by 0 can be carried out by having a register with value 0 and using the copy instruction; for this reason, it is not included here, in contrast to the account in [33].

For technical reasons, we start the enumeration of the program lines with 1 rather than 0.

Computations of an α-ITRM then works as follows: At successor stages, we simply carry out the program as we would in a classical (finite) register machine.6

⁶

If α is a successor ordinal, the incrementation operation may lead to the register content α; in that case, the content is replaced by 0. However, we will be mostly concerned with limit values of α in this paper.

At limit stages, the content of each register is the inferior limit of the sequence of earlier contents of this register; if this happens to be α, we say that the register “overflows” and set its content to 0. The active program line is just the inferior limit of the sequence of earlier active program lines. In the case

α = ω

, one drops the prefix and merely speaks of ITRMs, which have been studied in detail ([10,33,34]). A subset

x \subseteq α

is called α-ITRM-computable relative to

y \subseteq α

if and only if there is are an α-ITRM-program P and some

ξ < α

such that, for all

ι < α

, we have

\begin{matrix} P^{y} (ξ, ι) ↓ = \{\begin{array}{ll} 1, & if ι \in x \\ 0, & otherwise. \end{array} \end{matrix}

There is also a weaker model for register computations on α, known as “weak” or “unresetting” α-ITRMs, abbreviated α-wITRMs. These differ from α-ITRMs in that a register overflow – i.e., if, due to a limit operation, or (if α is a successor ordinal) due to an incrementation step – has the consequence that the computation is not defined. In the special case that $α = ω$ , these are called wITRMs, which were introduced and studied in Koepke [32]. The more general type was first mentioned in Koepke [33], but received little attention until [8].

In [33], Koepke showed that, for $α = ω$ , the subsets of α computable by such an α-ITRM are exactly those in $L_{ω_{ω}^{CK}}$ . Further information on ω-ITRMs was obtained in [10] and [34]. It is also known from Koepke and Siders [38] that, when one lets α be On, i.e., when one imposes no restriction on the size of register contents, the computable sets of ordinals are exactly the constructible ones. Recently, strengthening a result in [4], it was shown in [8] that the α-ITRM-computable subsets of α coincide with those in $L_{α + 1}$ if and only if $L_{α} ⊧ {ZF}^{-}$ ; and moreover, it was shown that, for any exponentially closed α, the α-ITRM-computable subsets of α are exactly those in $L_{β (α)}$ , where $β (α)$ is the supremum of the α-ITRM-halting times, which coincides with the supremum of the ordinals that have α-ITRM-computable codes. To determine the computational strength of α-ITRMs for some exponentially closed ordinal α, one thus needs to determine $β (α)$ . However, except for the cases $α = ω$ , $α = On$ and $L_{α} ⊧ {ZF}^{-}$ , no value of $β (α)$ is currently known. A reasonable conjecture compatible with all results obtained in [8] was that $β (α) = α^{+ ω}$ , the first limit of admissible ordinals greater than α, unless $L_{α} ⊧ {ZF}^{-}$ , which would be the most obvious analogue of Koepke’s result on ω-ITRMs. This, however, will be shown to be false below. As a result, there is currently not even a good conjecture about what the values of $β (α)$ might be, making the problem even more difficult.

Concerning weak register machines, we know from Koepke [32] that the subsets of ω computable by a wITRM are precisely the hyperarithmetic ones, i.e., those contained in $L_{ω_{1}^{CK}}$ . It was then shown in [8] that, when α is $Π_{3}$ -reflecting,7

⁷

We recall that α is $Π_{3}$ -reflecting if and only if, for each $Π_{3}$ -formula $ϕ (\vec{x})$ and each tuple $\vec{a}$ of elements of $L_{α}$ of the right length, we have $L_{α} ⊧ ϕ (\vec{a}) \Leftrightarrow L ⊧ ϕ (\vec{a})$ ; see, e.g., [39].

the α-wITRM-computable subsets of α are precisely those that are

Δ_{1}

over

L_{α}

. Ordinals with the latter property are called “u-weak”, and it is known that u-weak ordinal need not be

Π_{3}

-reflecting ([7], Theorem 53) (although they need to be admissible ([7], Theorem 52), but not every admissible ordinal is u-weak ([7], Theorem 53)). A full characterization of u-weak ordinals, or, more generally, of the computational strength of α-ITRMs for values of α that are neither ω nor

Π_{3}

-reflecting is still wanting.

In this paper, we will obtain lower bounds on the computational strength of α-ITRMs by showing how, when α is exponentially closed, α-ITRMs can compute transfinite (in fact $α \cdot ω$ long) iterations of β-ITRM-computable operators for $β < α$ . As a consequence, we are able to show that the conjecture mentioned above fails dramatically: In fact, for the first exponentially closed ordinal $ε_{0}$ larger than ω, we will already have $β (ε_{0}) ⩾ ω_{ε_{0} \cdot ω}^{CK}$ , while the next limit of admissible ordinals after $ε_{0}$ is of course still $ω_{ω}^{CK}$ . This improves Corollary 48 of [8], where it was shown that $β (α) ⩾ α^{+ ω}$ when α is an index ordinal.8

⁸

Recall that α is an index ordinal if and only if $L_{α + 1} ∖ L_{α}$ contains a real number.

⁹

Thus, while the goal of our project is to “tame” the “zoo” of machine models, this paper rather indicates that the “zoo” may in fact be a jungle. We hope that this will attract adventurers.

We also show that α-ITRMs are either able to solve the halting problem for α-ITRMs restricted to programs using a fixed number k of registers for every $k \in ω$ or allow for a universal α-ITRM. For $α = ω$ , the first alternative is known to hold by Koepke and Miller [34] and for $L_{α} ⊧ {ZF}^{-}$ , this follows from the results in [8], while for $α = On$ , the second alternative holds by [38]. We currently do not know which alternative holds for any other values of α. We then offer a third characterization of these α by showing that the restricted halting problem is solvable precisely for those α for which granting the machine the ability to notice when its working time reaches a cardinal does not change their computational power. Such cardinal-recognizing variants were first considered for ITTMs by Habic, see [26].

In the considerations so far, α-(w)ITRMs computations are always understood to be allowed the use of parameters, i.e., some registers besides the input register may initially contain ordinals other than 0. Dropping or restricting parameters, the picture changes considerably and resembles the situation for parameter-free tape models, so called α-ITTMs, as described in [42] and [15]: In particular, there are pairs of ordinals α, β such that α-ITRMs and β-ITRMs are incomparable with respect to their computational strength.

For an ordinal α, we will write $α^{+}$ to denote the smallest admissible ordinal strictly larger than α. Moreover, for $α, ι \in On$ , we recursively define $α^{+ 0} = α$ , $α^{+ (ι + 1)} = {(α^{+ ι})}^{+}$ and $α^{+ ι} = {sup}_{ξ < ι} α^{+ ξ}$ when ι is a limit ordinal. We use $p (α, β)$ for Cantor’s ordinal pairing function. For $x \subseteq α$ , P an α-(w)ITRM-program, $ρ < α$ , we write $P^{x} (ρ) ↓ = ι$ to indicate that the program P, when run in the oracle x and with ρ initially in its first register, halts with ι in its first register, and we write $P^{x} (ρ) ↑$ to indicate that the computation does not halt; when x is empty, the superscript is omitted.

1.2. A survey of the computational strength of transfinite register machine models

In this section, we want to summarize the results known so far on the computational strength of register models of transfinite computability.

Definition 1.
Recall that an ordinal β is α-(w)ITRM-clockable if and only if there is an α-(w)ITRM-program P and a parameter $ρ < α$ such that $P (ρ)$ halts in precisely β many steps.

Let us denote by ${COMP}_{α - wITRM}$ and ${COMP}_{α - ITRM}$ the sets of subsets of α computable by α-wITRMs and α-ITRMs (both with parameters), respectively.

Moreover, we recall from [8] that $β (α)$ denotes the supremum of the α-ITRM-clockable ordinals, while $β^{w} (α)$ denotes the supremum of the α-wITRM-clockable ordinals.

We use a standard way of encoding transitive ∈-structures as subsets of ordinals: Given a transitive ∈-structure S, an ordinal α and a bijection $f : α \to S$ , we can code S by ${p (ι, ξ) : ι, ξ \in α \land f (ι) \in f (ξ)}$ . When α is closed under the pairing function, this will yield a subset of α, in which case it is called a α-code for S. We can then say that S is α-ITRM-computable if and only if S has an α-ITRM-computable α-code.

Since every α-wITRM-computation is also an α-ITRM-computation, it is clear that the computational strength of α-wITRMs is no greater than that of α-ITRMs; and we see from the above that, when $α = ω$ , the computational strength of α-ITRMs considerably exceeds that of α-wITRMs. We note that this holds for unboundedly many ordinals, while it fails for unboundedly many others. For most ordinals, we currently do not know the answer.
Proposition 2.

There are unboundedly many ordinals α such that $\begin{matrix} {COMP}_{α - wITRM} ⊊ {COMP}_{α - ITRM} . \end{matrix}$

There are unboundedly many ordinals α such that $\begin{matrix} {COMP}_{α - wITRM} = {COMP}_{α - ITRM} . \end{matrix}$ In fact, for each ordinal α and each $γ \in [α + 1, α ω)$ , we have $\begin{matrix} {COMP}_{γ - ITRM} = {COMP}_{γ - wITRM} . \end{matrix}$

Proof.

Let α be such that $L_{α} ⊧ {ZF}^{-}$ . (It is easy to see that there are unboundedly many ordinals with this property; for instance, every regular cardinal is of this kind.) Now, by Theorem 19 of [8], we have ${COMP}_{α - ITRM} = P (α) \cap L_{α + 1}$ . On the other hand, each such ordinal is clearly $Π_{3}$ -reflecting, and thus, by Theorem 37 of [8], we have ${COMP}_{α - wITRM} = Δ_{1} (L_{α}) \cap P (α)$ . This is clearly a proper subset of $P (α) \cap L_{α + 1}$ .

Let $α = β + 1$ be a successor ordinal. It is easy to see that a β-ITRM-computation can be simulated by an α-wITRM-computation (using β as a parameter) in which each register that contains β is reset to 0. Thus, we have ${COMP}_{β - ITRM} \subseteq {COMP}_{α - wITRM}$ .

We will show in Proposition 9 below that ${COMP}_{β - ITRM} = {COMP}_{(β + 1) - ITRM}$ for all ordinals β. From this, it follows that, for $γ \in [α + 2, α ω)$ , we have: ${COMP}_{γ - wITRM} \subseteq {COMP}_{γ - ITRM} = {COMP}_{(α + 1) - ITRM} \subseteq {COMP}_{(α + 2) - wITRM} \subseteq {COMP}_{γ - wITRM}$ .
□
Question 3.
Characterize those ordinals α for which $\begin{matrix} {COMP}_{α - ITRM} = {COMP}_{α - wITRM} . \end{matrix}$

The results known so far about the computational strength of α-ITRMs and α-wITRMs are the following:
Definition 4.
An ordinal α is called (w)ITRM-singular if and only if there is an α-(w)ITRM-computable cofinal function $f : β \to α$ with $β < α$ .

We also recall that α is a ${ZF}^{-}$ -ordinal if and only if $L_{α} ⊧ {ZF}^{-}$ , where ${ZF}^{-}$ denotes ZF set theory without the power set axiom and with replacement replaced by collection.10
¹⁰
For the subtleties of the axiomatization of ${ZF}^{-}$ , see [24].

Theorem 5.

An ordinal α is ITRM-singular if and only if it is not a ${ZF}^{-}$ -ordinal. ([ 8 ], Lemma 24).

If α is ITRM-singular, then an ordinal is α-ITRM-clockable if and only if it is α-ITRM-computable ([ 8 ], Lemma 37 and Corollary 39).11
¹¹
More precisely, Lemma 39 of [8] states that the set of clockable ordinals and the set of computable ordinals have the same supremum, while Lemma 37 states that the set of clockable ordinals is downwards closed. Since it is easy to see that the set of computable ordinals is also downwards closed, this implies that the sets in fact agree. This result generalizes the result for ω-ITRMs in [10].

${COMP}_{ω - ITRM} = P (ω) \cap L_{ω_{ω}^{CK}}$ , and $β (ω) = ω_{ω}^{CK}$ (Koepke, [ 33 ], Theorem 5 and Theorem 6).

${COMP}_{ω - wITRM} = P (ω) \cap L_{ω_{1}^{CK}}$ , and $β^{w} (ω) = ω_{1}^{CK}$ (Koepke, [ 32 ], Theorem 1 and Lemma 1).

By slight abuse of notation, ${COMP}_{On - ITRM} = {COMP}_{On - wITRM} = P (On) \cap L$ . (Koepke and Siders, [ 38 ], Theorem 1)

${COMP}_{α - ITRM} = P (α) \cap L_{α + 1}$ if and only if $L_{α} ⊧ {ZF}^{-}$ ([ 8 ], Theorem 1) if and only if α is not ITRM-singular (ibid., Lemma 24). In this case, we have $β (α) = α^{ω}$ ; in fact, for each $k \in ω$ , an α-ITRM-program using k many registers will halt in less than $α^{k}$ many steps ([ 8 ], Theorem 14).

In all other cases, ${COMP}_{α - ITRM} = P (α) \cap L_{β (α)}$ ([ 8 ], Theorem 42).

If α is $Π_{3}$ -reflecting, then $β^{w} (α) = α$ and ${COMP}_{α - wITRM} = Δ_{1} (L_{α})$ ([ 8 ], Theorem 46).

For (ω-)ITRMs, we have the following important result by Koepke and Miller [34]: Theorem 6.
[Koepke and Miller, [ 34 ], Theorem 4] For every $k \in ω$ , there is an ITRM-program that solves the halting problem for ITRM-programs using at most k many registers.

2. Lower bounds on jump ordinals for register models

It is easy to see that, if parameters are allowed, computations of α-ITRMs can be simulated on β-wITRMs whenever $β > α$ , so that ${COMP}_{α - ITRM} \subseteq {COMP}_{β - wITRM}$ for all ordinals $α < β$ .

A natural task is then to determine those ordinals where the computational strength does actually increase, i.e., for each ordinal α, the minimal ordinal $α^{'}$ such that $β (α^{'}) > β (α)$ . In this section, we show that $β (α) = β (α^{'})$ whenever $α^{'} \in [α, α ω)$ .

Definition 7.
Let α be an ordinal. Then $α_{ITRM}^{j}$ , the “ordinal ITRM-jump of α”, denotes the minimal ordinal γ such that $β (γ) > β (α)$ .

The “jump”-terminology is justified by the following observation:12
¹²
It may be tempting to try to prove the next lemma using a simulation argument, simulating an arbitrary α-ITRM-program on a γ-ITRM and clocking $β (α)$ along the way. However, we point out that we know of no way to “trade” increased register capacity for extra register in a simulation; that is, we do not know how to simulate k α-registers with fewer than k many γ-registers, even if γ is much larger than α.

Lemma 8.
For each infinite α, the ordinal $α_{ITRM}^{j}$ is the smallest ordinal γ such that the halting problem for α-ITRMs is solvable by a γ-ITRM.
Proof.
We observe that, by Lemma 31 from [8], if $β (γ) > β (α)$ , there will be a γ-ITRM that clocks $β (α)$ , so $β (α)$ is γ-ITRM-computable, and hence, so is a subset of α coding $L_{β (α)}$ from which the halting set for α-ITRMs is then γ-ITRM-computable.

To see that $α_{ITRM}^{j}$ is minimal with this property, note that the halting problem for α-ITRMs cannot be an element of $L_{β (α)}$ by Theorem 5(vii), so that any γ for which it is γ-ITRM-computable must satisfy $β (γ) > β (α)$ . □

Towards the goal of this section, we recall the following result, along with its proof, from [8], Proposition 69:
Proposition 9.
For each ordinal α and all $α^{'} \in [α + 1, α ω)$ , we have $β (α + 1) = β (α^{'})$ . Thus, for all $γ, δ \in [α + 1, α ω)$ , we have ${COMP}_{γ - ITRM} = {COMP}_{δ - ITRM}$ .
Proof.
It is clear that $β (α^{'}) ⩾ β (α + 1)$ , as, for $γ_{0} < γ_{1}$ , $γ_{0}$ -ITRMs can be simulated on $γ_{1}$ -ITRMs.

For the reverse direction, we recall the brief argument from [8] for the sake of the reader.

Suppose that α is a limit ordinal. Since $α < α^{'} < α ω$ , there is $k \in ω$ such that $α^{'} < α \cdot k$ . We can thus simulate an $α \cdot k$ -ITRM on an $(α + 1)$ -ITRM by replacing each register R of the $α \cdot k$ -ITRM with k registers $R_{1}, \dots, R_{k}$ of the $(α + 1)$ -ITRM, representing the ordinal $γ < α \cdot k$ by writing γ as $α \cdot i + ρ$ with $i < k$ and $ρ < α$ and then letting $R_{1}, \dots, R_{i}$ contain α, letting $R_{i + 1}$ contain ρ and letting $R_{j}$ contain 0 for $j > (i + 1)$ .

It follows that $β (α) ⩽ β (α^{'}) ⩽ β (α \cdot k) = β (α)$ , so that $β (α) = β (α^{'})$ .

If α is a successor ordinal, write α as $\hat{α} + k$ , where $\hat{α}$ is limit ordinal and $k ⩾ 1$ is a natural number, so that $α + 1 ⩾ \hat{α} + 2$ . Then the above shows that, for $k \in ω$ sufficiently large, $β (\hat{α} + 1) ⩽ β (α + 1) ⩽ β (α^{'}) ⩽ β (\hat{α} \cdot k) = β (\hat{α})$ , so $β (α + 1) = β (α^{'})$ , as desired.13
¹³
Note that this shows, in contrast to the above footnote, how to “trade” increased register number for register capacity for some cases of not multiplicatively closed ordinals.

□

It thus remains to see that $β (α) = β (α + 1)$ . Remark 10.
Note that Proposition 9 fails for unresetting machines: For example, given that $α + 1$ -wITRMs can simulate α-ITRMs, and using Theorem 5, we have $\begin{matrix} {COMP}_{ω - wITRM} = P (ω) \cap L_{ω_{1}^{CK}} ⊊ P (ω) \cap L_{ω_{ω}^{CK}} = {COMP}_{ω - ITRM} \subseteq {COMP}_{(ω + 1) - wITRM} . \end{matrix}$
Lemma 11.
For all ordinals α, we have $β (α) = β (α + 1)$ .
Proof.
If $α = \bar{α} + 1$ is a successor ordinal, this follows from Proposition 9: For then, applying Proposition 9 to $\bar{α}$ , we have $β (α + 1) = β ((\bar{α} + 1) + 1) = β (\bar{α} + 2) = β (\bar{α} + 1) = β (α)$ .

We can thus assume without loss of generality that α is a limit ordinal.

Let P be an $(α + 1)$ -ITRM-program using the registers $R_{1}, \dots, R_{n}$ . We show how the actions of P can be simulated on an α-ITRM. Each register $R_{i}$ is represented by a triple $(γ, j, k) \in α \times {0, 1} \times {0, 1}$ . These triples are stored in three registers $(A_{i}, F_{i}, D_{i})$ (where A stands for “α-part”, F for “final part” and D for “detector”). The representation works via a decoding function f, which is defined by $\begin{matrix} f (γ, j, k) = \{\begin{array}{ll} γ, & if j = 0 \\ α, & if j = 1 . \end{array} \end{matrix}$ Note that this coding does not need the last component k; this will be used in the simulation to detect overflows at limit times: to this end, $D_{i}$ will contain 0 when $A_{i}$ contains 0 and otherwise, $D_{i}$ will contain 1. (This can be achieved by checking, after each computation step and at each limit time, whether or not $A_{i}$ contains 0 and then changing the content of $D_{i}$ accordingly.) We also use two flag registers to detect limit times.14
¹⁴
See, e.g., [4], p. 17. We use two registers $R_{0}$ , $R_{1}$ that initially contain 0 and 1 and swap their contents at each computation step. Thus, the computation will be at a limit time if and only if both registers contain 0.

Now, if, at some limit time δ – as detected using the flags – $A_{i}$ contains 0, this is either due to $A_{i}$ having contained 0 cofinally often before δ or due to an overflow in $A_{i}$ . These two cases can be told apart using $D_{i}$ : In the first case, $D_{i}$ will have contained 0 cofinally often before δ as well, and thus contain 0 at time δ, while in the second case, there is $ξ < δ$ such that the content of $A_{i}$ has never been 0 between times ξ and δ, so that the content of $D_{i}$ was always 1 between these times, and hence also at time δ. Thus, if both flags and $A_{i}$ contain 0, then this is due to an overflow if and only if $D_{i}$ contains 1.

We now explain how the simulation works at successor stages. Suppose that P is run and the active program line is L. Then our simulation works as follows (where we abuse notation by confusing registers with their contents):
If L contains $COPY (i, j)$ , then the contents of $A_{j}$ , $F_{j}$ and $D_{j}$ are replaced by those of $A_{i}$ , $F_{i}$ and $D_{i}$ , respectively.

If L contains $R_{i} + 1$ (i.e., an incrementation by 1), we distinguish two subcases:

(i) If $F_{i} = 0$ , then leave $F_{i}$ and replace the content of $A_{i}$ by its successor (this will always work, since, by assumption, α is a limit ordinal). If $A_{i} = 0$ , additionally replace the content of $D_{i}$ by 1. If $A_{i} = 0$ and $D_{i} = 1$ at a limit time, leave the content of $A_{i}$ unchanged and let $F_{i} = 1$ (this case applies when $A_{i}$ has overflown, i.e., $R_{i}$ should contain α).

(ii) If $F_{i} = 1$ , replace the contents of $A_{i}$ , $F_{i}$ and $D_{i}$ by 0 (this corresponds to a reset due to an overflow).

If L contains “IF $R_{i} = R_{j}$ THEN GOTO l” and we have both $A_{i} = A_{j}$ and $F_{i} = F_{j}$ , change the active program line to l. Otherwise, continue with the next program line.15
¹⁵
This adapts to the comparison of finite sequences of registers in the obvious way.

At a limit time δ, it is not always the case that applying f to the contents of $(A_{i}, F_{i}, D_{i})$ at time δ is the content of $R_{i}$ at time δ. However, this content is easily calculated: Namely, if $A_{i} \neq 0$ (that is, the inferior limit in $R_{i}$ was different from 0, but below α) or $A_{i} = D_{i} = 0$ (i.e., if $R_{i}$ contained 0 cofinally often), we leave the contents of $A_{i}$ , $F_{i}$ and $D_{i}$ unchanged. If $A_{i} = 0$ and $D_{i} \neq 0$ , an overflow has taken place, and we replace the content of $F_{i}$ by 0, leaving $A_{i}$ and $D_{i}$ unchanged at 0.

It is now easy to see that this simulation works as desired. □
Corollary 12.
For all ordinals α and all $α^{'} \in [α, α ω)$ , we have $β (α) = β (α^{'})$ .
Proof.
Immediate from Proposition 9 and Lemma 11. □
Question 13.
Given Corollary 12 , one might now conjecture that, in general, we have $α^{j} = α ω$ for all $α \in On$ . Is this true? Note that, below, we will show that $α^{ω} ⩾ α^{j}$ for certain values of α.

3. The BH-dichotomy

A particularly peculiar property of ITRMs is Theorem 6, i.e., the fact that, for any $k \in ω$ the halting problem for ITRMs using at most k registers is solvable by an ITRM-program (which, of course, uses more than k registers); see Koepke and Miller [34], Theorem 4. From this, it is deduced in [34] that there is no universal ITRM. The argument relies crucially on properties of ω and does not generalize to any other multiplicatively closed ordinal.16

¹⁶
In [4], Exercise 2.3.10, it is shown how the proof can be generalized to ordinals of the form $ω \cdot k$ for $k \in ω$ .

In fact, we do not know whether any other such ordinals besides ω and

{ZF}^{-}

-ordinals have this property. In this section, we will show that, for each α, either α has the property just described, or there is, in a certain sense, a universal α-ITRM. Definition 14.

An ordinal α has the ‘bounded halting property’ if and only if, for any $k \in ω$ , there are an α-ITRM-program P and an ordinal $ζ < α$ such that $P (ζ)$ solves the halting problem for α-ITRMs using at most k registers. More specifically, for all $i \in ω$ , $ξ < α$ , $P (i, ξ, ζ)$ halts with output 1 if and only if, for the i-th program $P_{i}$ using at most k registers, $P_{i} (ξ)$ halts and otherwise, it halts with output 0.

If α has the bounded halting property, we also say that α is BH.

Definition 15.

If P is an α-ITRM-program and $ζ < α$ , we say that $(P, ζ)$ is α-universal if and only if, for any α-ITRM-computable set $x \subseteq α$ , there are $j \in ω$ , $ν < α$ such that, for every $ι < α$ , $P (j, ν, ι, ζ)$ halts with output 1 if and only if $ι \in x$ and otherwise with output 0.

Theorem 16.

Let α be an ordinal. Then α is either BH or there are a program P and $ζ < α$ such that $(P, ζ)$ is α-universal.

Proof.

If α is a ${ZF}^{-}$ -ordinal, then, by Theorem 5(vi), α-ITRM-programs using k registers halt before time $α^{k + 1}$ ; and moreover, it is easy to see that $α^{k + 1}$ is α-ITRM-clockable for every $k \in ω$ . Consequently, the first alternative holds and the second fails.

We thus assume from now on that α is ITRM-singular. In particular, by Lemma 34 of [8], we can carry out a well-foundedness check for orderings coded by subsets of α on an α-ITRM.

Suppose that α is BH. We show that no $(P, ζ)$ can be universal for α. Suppose for a contradiction that $(P, ζ)$ is universal for α; let P use k many registers; moreover, pick an α-ITRM-program W that can test subsets of α for coding well-orderings and suppose that W uses l registers. Now, let H be a program that solves the halting problem for α-ITRMs with $k + l$ registers. Consider the following α-ITRM-program Q: Run through all pairs $(i, ξ) \in ω \times α$ such that i codes a program using at most k registers and use H to determine whether $P_{i} (ξ)$ will halt; if yes, run $P_{i} (ξ)$ and then continue with the next pair, if not, continue with the next pair immediately. We show that this will halt after all α-ITRM-halting times, which will be a contradiction. To see this, note that, by assumption, all α-ITRM-clockable ordinals are computable by P for an appropriate choice of the parameters. But now, Q in particular runs those programs that compute a code for some ordinal γ and apply W to this code, which takes at least γ many steps. Since this happens for all clockable γ, the halting time of Q will be above any α-ITRM-clockable ordinal, a contradiction.

On the other hand, suppose that α is not BH. This implies that there is $k \in ω$ such that the supremum of the ordinals clockable with an α-ITRM using at most k many registers is equal to $β (α)$ , for otherwise, we could use a program that halts after more steps as a stopwatch to solve the bounded halting problem for k registers, contradicting the assumption that α is not BH. Pick k such that this supremum attains $β (α)$ . It is not hard to see that there is a natural number $k^{'}$ such that, in fact, every ordinal $< β (α)$ is clockable by an α-ITRM-program using $k^{'}$ many registers: Namely, to clock $ξ < β (α)$ , pick a program Q using k registers that halts in $ν ⩾ ξ$ many steps. By Lemma 30 in [8] (which generalizes a result from [10] on ITRMs), no configuration can occur in the halting computation of Q at least $ω^{ω}$ many times. Thus, there is some ordinal $ξ^{'} < ω^{ω}$ and some Q-configuration c such that, in the computation of Q, c appears for the $ξ^{'}$ -th time at time ξ. Using a few extra registers and given c and $ξ^{'}$ as parameters, this can be detected and used to clock ξ. Moreover, by Theorem 5(ii), α-ITRM-clockable ordinals have α-ITRM-computable codes for α ITRM-singular and in fact, the transition from a program P that clocks ξ to one that computes a code for ξ is uniform in P and uses a fixed number of extra registers depending only on the number of registers used by P. Thus, there is $k^{″} \in ω$ such that, for each $ξ < β (α)$ , there is an α-ITRM-program using at most $k^{″}$ many registers that computes a code for ξ.

Now, our universal program $U$ will work as follows: Let P be an α-ITRM-program that computes some set $x \subseteq α$ . Pick $ξ < β (α)$ minimal such that $x \in L_{ξ}$ . By assumption, there must be an α-ITRM-program $P^{'}$ that uses at most $k^{″}$ many registers and computes a code for ξ. But now, by Lemma 3.4.26(i) from [4], there is an α-ITRM-program $P_{L}$ that computes a code d for $L_{ξ}$ from a code for ξ, uniformly in the code for ξ. Finally, again by results in [4],17

¹⁷

See [4], Corollary 3.4.27(ii).

a code d for

L_{ξ}

can be used to read out any

y \subseteq α

contained in

L_{ξ}

when the index

ι^{'}

coding y in the sense of d is given. □

Remark 17.

We note that the above theorem yields a universal machine only in a rather weak sense of the word: Although we indeed obtain a program U that is universal in the sense that, for given i and γ, there are parameters j and ρ such that, in the parameters j and ρ, U will compute the same function as $P_{i} (γ)$ , this does not work in any proper sense by U simulating the work of $P_{i}$ , but rather by computing the same function in a completely different way. This can be made precise by observing that (i) we have no effective way of obtaining ρ from i and γ and (ii) there is no reason to expect U to work relative to oracles $x \subseteq α$ : Currently, we are unable exclude the possibility that for some α that is not BH, the bounded halting problem for α-ITRMs relative to some oracle x could be solvable for α-ITRMs in the oracle x. A more satisfying result would be that, for each α and $x \subseteq α$ , either the bounded halting problem for α-ITRMs is solvable on α-ITRMs uniformly in x – i.e., there is, for each $k \in ω$ , an α-ITRM-program $H_{k}$ that solves the halting problem for α-ITRMs with k registers relative to every oracle $x \subseteq α$ – or there exists a program U such that, for all $x \subseteq α$ , all $i \in ω$ and all $γ \in α$ , $U^{x} (i, γ)$ computes the same function as $P_{i}^{x}$ .

4. Restricted parameters

Unless $α = ω$ or $L_{α} ⊧ {ZF}^{-}$ , where the answer is positive, we are currently unable to answer whether the computational strength of α-ITRMs increases with the number of registers. It is natural to conjecture that this is the case in general.18

¹⁸
We point out that, for ordinal register machines (ORMs), which have no bound on their register contents, there is indeed a universal machine with 10 registers, see Koepke and Siders [44]. However, since overflows are ruled out for these machines, this seems to bear little analogy to α-ITRMs.

Another natural stratification of the computational power of α-ITRMs is the size of parameters: Restricting the initial register contents to elements of some

γ ⩽ α

, and denoting by

{COMP}_{α - ITRM}^{γ}

the set of subsets of α thus computable, and by

β_{γ} (α)

the supremum of ordinals thus clockable (and by

{COMP}_{α - wITRM}^{γ}

and

β_{γ}^{w} (α)

the analogous concepts for α-wITRMs), one would naturally expect that

β_{γ} (α)

keeps increasing with γ, at least for certain values of α. However, it is not hard to see that these two natural conjectures contradict each other at least in certain cases:

Definition 18.

We say that α satisfies the bounded parameter property (BP) if and only if, for cofinally in α many γ, we have $β_{γ} (α) > {sup}_{ι < γ} β_{ι} (α)$ .

Moreover, for $k \in ω$ , let us denote by $β^{k} (α)$ the supremum of ordinals clockable by α-ITRMs (using arbitrary parameters) using at most k many registers.

Proposition 19.

If $cf (α) > ω$ , then the bounded halting property and the bounded parameter property cannot hold simultaneously for α.

Proof.

Suppose otherwise, so that α satisfies $ρ : = cf (α) > ω$ and α is both BH and BP. Clearly, we have $β (α) = {sup}_{ι < α} β_{ι} (α)$ and $β (α) = {sup}_{k \in ω} β^{k} (α)$ . But this would imply that $cf (α) = cf (β (α)) = ω$ , contradicting our assumption. □

We will now investigate the properties of α-ITRMs with no or restricted parameters. This was considered in the case of α-Turing machines by Rin in [42], and several of the questions considered below are motivated by Rin’s work.

The following is a variant of Theorem 30 of [8] (which, in turn, is a generalization of Lemma 4 of [10]) for α-ITRMs with restricted parameters.

Lemma 20.

For each ordinal α, each $γ ⩽ α$ and each ordinal τ, if τ is α-ITRM-clockable with parameters in γ, then τ is also α-ITRM-computable with parameters in γ.

Proof.

The proof of [8], Theorem 30, is easily seen to adapt to parameter restrictions. □

Remark 21.

Note, however, that the downwards closure of the set of α-ITRM-clockable ordinals, which is proved in [8], Lemma 31 (generalizing Lemma 3 of [10]), does not necessarily continue to hold when parameters are restricted: Thus, for example, it is easy to see that $ω_{1}$ is clockable on an $ω_{1}$ -ITRM without parameters, but as long as only parameters contained in some $γ < ω_{1}$ are admitted, there will only be countable (and thus boundedly) many $ω_{1}$ -ITRM-clockable ordinals below $ω_{1}$ . It is also easy to construct countable examples of this behavior via condensation arguments.

Definition 22.

For $X \subseteq M$ , let us write $Σ^{M} (X)$ for the $Σ_{1}$ -Skolem hull of X in M under the canonical $Σ_{1}$ -Skolem function for L (in the language of set theory).

We need a slight strengthening of Lemma 40 from [8]:

Lemma 23.

Let α be exponentially closed. Then there are α-ITRM-programs $P_{0}$ and $P_{1}$ with the following properties: For each α-ITRM-clockable γ, there is an α-ITRM-computable code $c \subseteq α$ , such that:

For each $ι < α$ that represents an ordinal $ξ < α$ in the sense of c, $P_{0} (ι) ↓ = ξ$ .

For each $ι < α$ , $P_{1} ((0, ι))$ computes the ordinal ξ which represents ι in the sense of c, while $P_{1} ((0, 0))$ computes the ordinal ξ which represents α in the sense of c.

In fact, an α-ITRM-program P and a parameter ρ such that

(P, ρ)

computes c can be obtained uniformly from a program

P^{'}

and a parameter τ such that

(P^{'}, τ)

clocks γ.

Proof.

See [8], Lemma 40(2).

We recall from the proof of [8], Lemma 35, that c is obtained by encoding each configuration occuring in a computation that clocks γ, together with an ordinal indicating how often it has appeared in the computation so far, as a single ordinal below α and then ordering these by the order in which they appear in the computation (recall that no configuration can occur more than $ω^{ω}$ many times in a halting α-ITRM-computation by [8], Lemma 30).19

¹⁹

This generalizes results about ω-ITRMs obtained in [10], Theorem 5.

^,20

²⁰

In [8], such codes were called “clockably extracted α-codes”.

In [8], Lemma 40, (2) was proved restricted to the first case (i.e.,

ξ < α

). However, it is easy to see how to extend the argument to α itself: on input

(0, ξ)

, we proceed as in the proof of Lemma 40 in [8], while on input

(1, 0)

, we let the program C that clocks γ run for α many steps, thus computing the configuration of this program at time α, and then run it again for α many steps to count how often this configuration occurs; the configuration at time α and the number of appearances of this configuration up to time α yield the desired index. To run C for α many steps, simply run C while counting upwards in some specified register until that register overflows.

□

Theorem 24.

Let $γ ⩽ α \in On$ , and suppose that α is exponentially closed.

If α is ITRM-singular, then ${COMP}_{α - ITRM}^{γ} = Σ_{1}^{L_{β_{γ} (α)}} (γ \cup {α}) \cap P (α)$ .

Proof.

Let us write $H : = Σ_{1}^{L_{β_{γ} (α)}} (γ \cup {α}) \cap P (α)$ .

First, suppose that $x \in {COMP}_{α - ITRM}^{γ}$ . Let P be a program and $ρ < γ$ a parameter such that $P (ρ)$ computes x. Let $\tilde{P} (ξ)$ be the program that, successively for all $ι < α$ , runs $P (ξ, ι)$ . Since $P (ρ)$ is still a program running in the parameter $ρ < γ$ and $P (ρ, ι)$ halts for every $ι < α$ by assumption, $\tilde{P} (ρ)$ halts in less than $β_{γ} (α)$ many steps; denote by τ the halting time of $\tilde{P} (ρ)$ . Then x is definable over $L_{τ}$ and thus an element of $L_{β_{γ} (α)}$ . Moreover, the formula saying that $P (ρ)$ has a halting time is $Σ_{1}$ in the parameters ρ and α over $L_{β_{γ} (α)}$ , and thus we have $τ \in H$ . Since satisfaction in $L_{τ}$ for arbitrary ∈-formulas is $Δ_{1}$ over $L_{β_{γ} (α)}$ in τ, it follows that x is $Σ_{1}$ over $L_{β_{γ} (α)}$ in $ι < γ$ and α, and thus $x \in H$ .

Conversely, assume that $x \in H$ , and let ϕ be an $Σ_{1}$ -formula and $ρ < γ$ such that x is the $<_{L}$ -minimal witness of $ϕ (ρ, α, y)$ . Pick $δ < β_{γ} (α)$ minimal such that $L_{δ} ⊧ \exists y ϕ (ρ, α, y)$ , so that $x \in L_{δ}$ . By definition of $β_{γ} (α)$ , there is an ordinal $η > δ$ which is α-ITRM-clockable with some parameter $ξ < γ$ . By Lemma 20, η is α-ITRM-computable in parameters $< γ$ , so let c be an α-ITRM-computable code for η as in Lemma 23 (i.e., a clockably extracted code). As in the proof of Lemma 34 of [8], we can now compute a code $d \subseteq α$ for $L_{η}$ from c in which, for each $ξ < α$ , the ordinal represented by ξ in c is represented by $ω ξ$ . From the parameter ρ, we can compute the ordinal $ρ^{'} < α$ which codes ρ in d; similarly, we can compute the ordinal $α^{'} < α$ which codes α in d.21

²¹

This is the reason why Lemma 33 from [8] had to be extended to include the search for the ordinal coding α itself: Although this is a single ordinal below α, it may be larger than γ, so that we cannot use it as a parameter in the current context.

Now, $L_{η} ⊧ \exists y ϕ (ρ, α, y)$ by upwards absoluteness of $Σ_{1}$ -formulas and thus, $x \in L_{η}$ . By searching exhaustively through α (i.e., counting upwards from 0 in some register and checking every new register content until an overflow occurs), and using $ρ^{'}$ and $α^{'}$ , we can identify the ordinal $ι \in α$ that codes the $<_{L}$ -minimal witness for $ϕ (ρ, α, y)$ (i.e., x).

Given ι, we can check whether a given ordinal $ξ < α$ belongs to x by using $P_{1}$ from Lemma 23 to determine the ordinal $ξ^{'}$ coding ξ in the sense of $c -$ which means that $ω \cdot ξ^{'}$ codes ξ in the sense of $d -$ , and then checking whether $p (ω ξ^{'}, ι) \in d$ . It follows that x is α-ITRM-computable in the parameter ρ. □

Remark 25.

Without the assumption of ITRM-singularity, this is clearly false, for then, we have $L_{α} ⊧ {ZF}^{-}$ , so ${COMP}_{α - ITRM} = P (α) \cap L_{α + 1}$ , while $L_{β_{0} (α)} = L_{β (α)} = L_{α^{ω}}$ . Now let $γ = α$ in Theorem 24. In $L_{α^{ω}}$ , using the parameter α, we can easily define $L_{α + 2}$ and $L_{α + 1}$ by $Σ_{1}$ -formulas and then use the $Σ_{1}$ -formula “There is an element of $L_{α + 2}$ which is not contained in $L_{α + 1}$ ” to obtain an element of H which is not α-ITRM-computable.

Since there are only countable many programs, it is clear that there are (many) values $ι < ω_{1}$ such that a parameter-free $ω_{1}$ -(w)ITRM cannot halt with ι in its first register. The same is true for every ordinal $⩾ ω_{1}$ . Moreover, via condensation, the same result can be seen to hold for unboundedly in $ω_{1}$ many ordinals.

Question 26.

Determine the minimal ordinal α such that, for some $ι < α$ , ${ι}$ is not α-ITRM-computable without parameters. 22

²²

The analogous question for α-ITTMs was considered and answered in [15].

Dropping parameters has the effect that the set of clockable ordinals can have gaps.

Lemma 27.

There exists an ordinal ρ such that, for all $μ < ρ$ , there are ordinals $α < β < γ$ such that α and γ are halting times of ρ-ITRM-computations using only parameters $< μ$ , but β is not.

Proof.

Let $ρ = ω_{1}^{L}$ . Then the L-countable ordinals that are clockable by a ρ-ITRM with parameters less than μ have a countable supremum (since they form a countable set of countable ordinals); let us denote this supremum by $ξ (μ)$ . Now, every ordinal between $ξ (μ)$ and $ω_{1}^{L}$ will fail to be ρ-ITRM-clockable with parameters $< μ$ ; but clearly, $ω_{1}^{L}$ is ρ-clockable (e.g., by a program that counts upwards in some register until an overflow is detected). So we can let $α = ω$ , $β = ξ (μ)$ and $γ = ω_{1}^{L}$ . □

Remark 28.

Countable examples of this phenomenon can be obtained by forming the elementary hull H of the empty set in $L_{ω_{2}}$ , taking the transitive collapse $\overline{H}$ of H and considering the image of $ω_{1}$ under the collapsing map.

In Rin [42], Theorem 2.8, it was shown that, for parameter-free α-Turing machines, there exist values α and β such that the computational strength of α-Turing machines and β-Turing machines are incomparable with respect to the computable subsets of $min {α, β}$ – that is, none is a subset of the other.

We note here that the same obtains for register machines. The argument morally (i.e., with respect to the overall strategy) resembles those in [42] and [15]; however, the considerable differences between tape and register models – such as the unavailability of a universal program that enumerates all computable sets – require extra efforts.

The following lemma will come in handy.

Definition 29.

Let α be an ordinal. A set $C \subseteq P (α)$ is α-ITRM-decidable if and only if there is an α-ITRM-program P and some parameter ρ such that, for all $x \subseteq α$ , $P^{x} (ρ)$ halts with output 1 if and only if $x \in C$ , and otherwise, $P^{x} (ρ)$ halts with output 0.

Lemma 30.

Suppose that α is an exponentially closed ordinal and ITRM-singular 23

²³

The ITRM-singularity is not necessary for the lemma to hold; however, the proof becomes somewhat more involved without this assumption and this is the only case that we will need.

ordinal and

C \subseteq P (α)

is α-ITRM-decidable without parameters such that

(L_{α + 1} ∖ L_{α}) \cap C \neq \emptyset

. Then

(L_{α + 1} ∖ L_{α}) \cap C

contains a parameter-freely α-ITRM-computable element.

Proof.

By Lemma 41 of [8], $L_{α}$ has a parameter-freely α-ITRM-computable code c which is such that the function f mapping $ι < α$ to the ordinal coding ι in the sense of c, along with its inverse function are α-ITRM-computable without parameters.24

²⁴

Strictly speaking, the inverse function is a partial function. In the case that it is not defined, the algorithm is supposed to indicate this, e.g., by writing the value 1 in some register specifically reserved for this purpose. Given that f is α–ITRM-computable, it is easy to see that this can be decided by simply checking, given $ξ < α$ , for each $ι < α$ whether $f (ξ) = ι$ .

Given c and f (along with its inverse), it is now possible to check, for each $x \subseteq α$ , whether or not $x \in L_{α}$ : To do this, run through α, and, for each $ι \in α$ , check whether ι happens to code x in the sense of c. This, in turn, can be done by again searching through α and, for each $ξ < α$ , testing whether $ξ \in x \leftrightarrow p (f (ξ), ι) \in c$ and also whether, if $p (ξ, ι) \in c$ , ξ has a preimage under f.

Pick $y \in (L_{α + 1} ∖ L_{α}) \cap C$ . By [8], Lemma 4, there are an α-ITRM-program P, some $n \in ω$ and some $ρ < α$ such that $P (ρ)$ computes y in less than $α^{n}$ many steps.25

²⁵

The time bound is left implicit in [8], so a remark is in order how it is obtained: Roughly, P works by evaluating truth in $L_{α}$ for the formula ϕ defining x over $L_{α}$ ; if ϕ is $Σ_{n}$ , this can be done by n nested exhausted searches through α, which can be done with time bound $α^{n}$ .

For

ι < α

, denote by

c (ι)

the set

{ξ < α : P (ι, ξ) ↓ = 1 in less than α^{n} many steps}

. Thus,

c (ρ) = y

. It is clear that

c (ι)

is α-ITRM-computable uniformly in ι, since

α^{n}

is easily seen to be α-ITRM-clockable (without parameters) for any

n \in ω

(simply perform n nested runs through α in n separate registers). Moreover, let Q be an α-ITRM-program that decides C.

Now, the desired program works like this: We count through α in some register. For every $ι < α$ , we (i) use c to check whether $c (ι) \in L_{α}$ and (ii) run $Q^{c (ι)}$ (which is possible since $c (ι)$ is uniformly α-ITRM-computable from ι). If the answer to (i) is positive or if $Q^{c (ι)} ↓ = 0$ , we continue with $ι + 1$ . Otherwise, a parameter ξ has been identified such that P computes a set $z \subseteq α$ with the desired properties in the parameter ξ. Since ξ was computed without the use of parameters, z is parameter-freely α-ITRM-computable. But it is clear that this will eventually happen, since, for $ι = ρ$ at the latest, we obtain $c (ι) = y$ , which is as desired. □

Lemma 31.

[Cf. [ 42 ], Theorem 2.8] For every ordinal μ, there are ordinals $α < β$ such that neither $\begin{matrix} {COMP}_{α - ITRM}^{μ} \subseteq {COMP}_{β - ITRM}^{μ} \cap P (α) \end{matrix}$ nor $\begin{matrix} {COMP}_{α - ITRM}^{μ} \supseteq {COMP}_{β - ITRM}^{μ} \cap P (α) . \end{matrix}$

Proof.

We deal with the case $μ = 0$ ; the general case is an easy variation of this case.

Let us say that an ordinal γ is an $ω_{1}^{L}$ -index if and only if $(L_{γ + 1} ∖ L_{γ}) \cap P (ω_{1}^{L}) \neq \emptyset$ . Let us write $I$ for the set of $ω_{1}^{L}$ -indices. Claim 32.

For each $ζ \in I$ , $I ∖ ζ$ has order type strictly greater than $ω_{1}^{L}$ .

Proof.

To see this, let, for $ι ⩽ ω_{1}^{L}$ , $ξ_{ι}$ denote the minimal ordinal for which $L_{ξ_{ι}} ⊧$ “There are at least ι many ${ZF}^{-}$ -ordinals greater than ζ”. Clearly, we have $ξ_{ι} \in I$ for all such ι, and moreover, we have $ξ_{ι_{0}} < ξ_{ι_{1}}$ whenever $ι_{0} < ι_{1} ⩽ ω_{1}^{L}$ . □

Claim 33.

For each $ξ \in I$ , we also have $β (ξ) + 1 \in I$ .

Proof.

Let $ξ \in I$ . Let $x \subseteq ω_{1}^{L}$ be such that $x \in (L_{ξ + 1} ∖ L_{ξ})$ . Consider the $Σ_{1}$ -formula that states “There are ordinals $α, β$ such that $x \in (L_{α + 1} ∖ L_{α})$ and, every α-ITRM-computation halts or loops in less than β many steps and $L_{β}$ believes that, for every γ, there is an α-ITRM-computation that halts in γ many steps”. Clearly, $L_{β (α) + 1}$ is the minimal L-level in which this formula is true. By a standard fine-structural argument,26

²⁶

We sketch the argument for the sake of the reader: Since $L_{β (α) + 1}$ is the minimal L-level in which this $Σ_{1}$ -formula is true, the $Σ_{1}$ -hull of $ω_{1}^{L} \cup {x}$ in $L_{β (α) + 1}$ will be isomorphic to $L_{β (α) + 1}$ . Thus, there is a bijection, definable over $L_{β (α) + 1}$ , between $ω_{1}^{L}$ and $L_{β (α) + 1}$ . This implies that $L_{β (α) + 2}$ contains a subset of $ω_{1}^{L}$ which codes $L_{β (α) + 1}$ , and this subset cannot be contained in $L_{β (α) + 1}$ .

it follows that

β (α) + 1

is an

ω_{1}^{L}

-index. □

Claim 34.

If α is an $ω_{1}^{L}$ -index, then there is a parameter-freely α-ITRM-computable set c such that $c \in (L_{α + 1} ∖ L_{α}) \cap P (ω_{1}^{L})$ .

Proof.

We use Lemma 30, where $C = P (ω_{1}^{L})$ . We thus need to check that the assumptions of this lemma are satisfied.

First, since α is an $ω_{1}^{L}$ -index, $L_{α}$ is not a model of ${ZF}^{-}$ and thus ITRM-singular by [8], Lemma 24.

Second, we need to see that $P (ω_{1}^{L})$ is α-ITRM-decidable without parameters. As in the proof of Lemma 30, there is a parameter-freely α-ITRM-computable code $c \subseteq α$ for $L_{α}$ such that the coding function f and its inverse, the decoding function are parameter-freely α-ITRM-computable. By Lemma 25 of [8], there is a parameter-free α-ITRM-program T that evaluates truth of ∈-formulas in $L_{α}$ . Let ϕ be the formula “x is the smallest uncountable cardinal”. We can now run through α and use T to check, for each $ι < α$ , whether $f (ι)$ is the smallest uncountable cardinal in $L_{α}$ . Since $α > ω_{1}^{L}$ , the answer will eventually be positive, and then we will have found the unique $ζ < α$ which codes $ω_{1}^{L}$ in the sense of c, i.e., such that $f (ω_{1}^{L}) = ζ$ . Now, to check whether a given set $x \subseteq α$ is in fact a subset of $ω_{1}^{L}$ , run through α and check, for every $ι < α$ , whether $ι \in x \to p (f (ι), ζ) \in c$ . If this is the case for all $ι < α$ , we return 1, otherwise, we return 0. □

It is now easy to see that we cannot have $\begin{matrix} {COMP}_{α - ITRM}^{0} \cap P (ω_{1}^{L}) \subseteq {COMP}_{β - ITRM}^{0} \cap P (ω_{1}^{L}) \end{matrix}$ for all $α, β \in I$ with $β > α$ : Otherwise, if η is the $ω_{1}^{L}$ -th element of $I ∖ α$ – which exists by the first claim – ${COMP}_{η - ITRM}^{0}$ would have to contain some specific subset $y (ξ) \in (L_{ξ + 1} ∖ L_{ξ}) \cap P (ω_{1}^{L})$ for each $ξ \in I ↾ η$ , so we would have a constructible injection from $ω_{1}^{L}$ into ${COMP}_{η - ITRM}^{0}$ , contradicting the fact that, since there are only countable many programs, ${COMP}_{η - ITRM}^{0}$ is clearly countable in L.

It follows that there are $α, β \in I$ such that $β > β (α)$ and $\begin{matrix} {COMP}_{α - ITRM}^{0} \cap P (ω_{1}^{L}) ⊈ {COMP}_{β - ITRM}^{0} \cap P (ω_{1}^{L}) . \end{matrix}$ Thus, some parameter-freely α-ITRM-computable subset of $ω_{1}^{L}$ is not β-ITRM-computable.

However, by the third claim, there is a parameter-freely β-ITRM-computable subset z of $ω_{1}^{L}$ which is contained in $L_{β + 1} ∖ L_{β}$ . Since $β > β (α)$ by assumption, we have in particular $z \notin L_{β (α)}$ , so z is not α-ITRM-computable (not even with parameters). Thus, we also have that some parameter-freely β-ITRM-computable subset of $ω_{1}^{L}$ is not α-ITRM-computable.

Thus, the pair $(α, β)$ is as desired.27

²⁷

Again, countable examples can be obtained from this by condensation arguments.

This argument works for all finite values of μ. For infinite μ, we replace $ω_{1}^{L}$ with the cardinal L-successor of μ in the above argument. □

However, when one only considers real numbers, the ordinals indeed form a linear hierarchy with respect to parameter-free ITRM-computability strength. This was proved for parameter-free α-ITTMs in [15], Theorem 2.19; the argument for α-ITRMs is essentially the same, but the limitations of register models – such as the nonexistence of a universal machine – lead to a few extra subtleties.

Theorem 35.

[Cf. [ 15 ], Theorem 2.18] For each infinite ordinal α, there is an ordinal $ρ_{0} (α)$ such that ${COMP}_{α - ITRM}^{0} = L_{ρ_{0} (α)} \cap P (ω)$ . Consequently, the set ${{COMP}_{α}^{0} \cap P (ω) : α \in On}$ 28

²⁸

That this, in spite of being indexed with the class of ordinals, is a set rather than a proper class follows from the fact that it is clearly a subset of $P (P (ω))$ .

is linearly ordered by ⊆.

Proof.

It clearly suffices to prove the first claim. To this end, we will show that, for any α and any real number x, if x is α-ITRM-computable without parameters, then there is a parameter-freely α-ITRM-computable real number $l (x)$ that codes an L-level $L_{β} ∋ x$ . Once this is achieved, the proof finishes as follows: If $y \in L_{β} \cap P (ω)$ , then there is a natural number i that codes y in the sense of $l (x)$ . As a natural number, i is parameter-freely computable (by a program that applies the successor operation i many times). Now, to determine for an arbitrary $j \in ω$ whether $j \in y$ , we need to determine the natural number $n (k)$ that codes j in the sense of $l (x)$ and then check whether $p (j, i) \in y$ . Identifying $n (k)$ (uniformly in k) is easily seen to be possible already on an ITRM (for details, see [10]),29

²⁹

To give a brief sketch: $n (0)$ can be identified as the only natural number that has no predecessor in the sense of $l (x)$ (i.e., $l (x)$ contains no element of the form $p (m, n (0))$ ). Then, recursively, $n (m + 1)$ is the unique natural number which has $n (0), \dots, n (m)$ as its predecessors in the sense of c, and no others. In the same way, the natural number coding ω in the sense of $l (x)$ can also be identified.

and thus on a parameter-free α-ITRM for any

α ⩾ ω

Now for the claim. Let $x \subseteq ω$ be given, and let P be an α-ITRM-program that computes x without parameters. By successively running $P (i)$ for all $i \in ω$ , we see that the supremum ρ of the halting times of these computations is parameter-freely α-ITRM-clockable; hence, so is $ρ + 2$ . Since x is definable over $L_{ρ}$ as ${i \in ω : P (i) ↓ = 1}$ , we have $x \in L_{ρ + 1}$ . Moreover, $ρ + 1$ is minimal such that $L_{ρ + 1}$ believes in the existence of an ordinal ρ such that $L_{ρ} ⊧ \forall i \in ω P (i) ↓$ ; hence, $ρ + 1$ is an index and thus, by [2], Theorem 1, a real number c coding $L_{ρ + 1}$ is contained in $L_{ρ + 2}$ . The argument that α-ITRM-clockable ordinals are also α-ITRM-computable given in [8], Theorem 35, makes no use of parameters and thus in fact shows that there is a subset of α coding $ρ + 2$ which is α-ITRM-computable without parameters.

By Lemma 41 of [8], there is a parameter-freely α-ITRM-computable subset a of α that codes $L_{ρ + 2}$ (again, the argument makes no use of parameters). Now, given c, we can search through α for some ι which codes, in the sense of c, a subset r of ω that codes a transitive model of $V = L$ which contains x: Being a subset of ω can be established as sketched in the last footnote. Again using the footnote, one can then use c and ι to decide, for a given $i \in ω$ , whether $i \in r$ . Checking the other properties – coding a transitive model of $V = L$ that contains x – can then be done even on an ω-ITRM, since these can perform well-foundedness checks by section 3 of [34], evaluate truth predicates in coded structures and check whether coded structures contain a given real number by [10], and thus on an α-ITRM whenever $α ⩾ ω$ . □

As observed in [15], Theorem 2.18(a) for parameter-free α-Turing machines, it is not the case that greater ordinals also yield greater computability strength with respect to real numbers: Proposition 36 (Cf. [15], Theorem 2.18).

There are ordinals $ω < α < β$ such that ${COMP}_{α - ITRM}^{0} \cap P (ω) ⊋ {COMP}_{β - ITRM}^{0} \cap P (ω)$ .

Proof.
Whenever $α > ω$ , there is a parameter-free α-ITRM program that halts with ω in its first register $R_{1}$ : Using two auxiliary registers, increment $R_{1}$ by 1 in every step, while the auxiliary registers initially contain 1 and 0, respectively, and swap their contents in every step. Halt when both of these registers contain 0, which will happen at the first limit ordinal, i.e., ω, which will then be the content of $R_{1}$ . Using this, it is now easy to see that $P (ω)$ is α-ITRM-decidable for every $α ⩾ ω$ .

Now, whenever α is an index, i.e., such that $L_{α + 1} ∖ L_{α}$ contains a real number, then $L_{α}$ is not a model of ${ZF}^{-}$ , so α is ITRM-singular by [8], Lemma 24. Hence, the assumptions of Lemma 30 are satisfied, and it follows that $L_{α + 1} ∖ L_{α}$ contains a parameter-freely α-ITRM-computable real number. It is standard that index ordinals are unbounded in $ω_{1}^{L}$ . Given this, we cannot have ${COMP}_{α - ITRM}^{0} \subseteq {COMP}_{ω_{1}^{L} - ITRM}^{0}$ for all $α < ω_{1}^{L}$ , since the latter set is still countable.30
³⁰
Again, countable counterexamples can now be obtained via condensation arguments.

□

5. Cardinal-recognizing ITRMs

In [26], Habic considered a new way of conveying extra information to a transfinite computation by introducing “cardinal-recognizing Infinite Time Turing Machines” which assume a special inner state whenever the computation time reaches an infinite cardinal. This turned out to considerably increase the computational strength of ITTMs. The same is true for Ordinal Turing Machines: for example, [4], Exercise 4.4.6 shows that, if the set of real numbers in the universe is closed under the sharp operator, then so is the set of real numbers computable by cardinal-recognizing OTMs with ordinal parameters. The idea of cardinal recognition can easily be adapted to register models. In this section, we will show that, perhaps surprisingly, for ITRMs, the ability to recognize cardinals is sterile: It does not change the set of computable objects. For general values of α, we will see an increase in computational power due to the ability to recognize cardinals is equivalent to the solvability of the bounded halting problem and thus forms a further characterization in the BH-dichotomy.

Definition 37.
Let X be a class of ordinals. An X-recognizing α-ITRM works like an α-ITRM with an extra “detection” register $R_{D}$ that behaves as follows: Whenever the current computation time is contained in X, the content of $R_{D}$ is changed to 0.31
³¹
Note that this has the effect that $R_{D}$ contains 0 at all times that are limits of elements of X. For our purposes, this effect is welcome, as the cases of X relevant for us are closed under limits. If one wanted to avoid this, one could change 0 to 1 in the definition.

Let us write UCard for the class of uncountable cardinals. $UCard$ -recognizing α-ITRMs will be called “cardinal-recognizing α-ITRMs”, abbreviated α-cITRMs.

For an α-ITRM-program P, we denote by $^{X} P$ the program run as an X-recognizing α-ITRM, i.e., run with the modifications in the behaviour of $R_{D}$ just described.

Moreover, for $δ \in On$ , let us write $M_{δ} : = {δ ι : ι \in On}$ for the set of multiples of δ. We will abbreviate $M_{ω_{k}^{CK, x}}$ by $A_{k}^{x}$ for $x \subseteq ω$ and $k \in ω$ .
Remark 38.
That we use UCard rather than Card has technical reasons: Otherwise, the first ω many steps would all be registered as cardinals, which is an unwanted behaviour that would lead to inconvenient special cases. It is easy to see that UCard-computations can be carried out on $Card$ -recognizing α-ITRMs by simply running for ω many “empty” steps before starting the “actual” computation, so that the modification is insubstantial.

For ITTMs, it was observed Habic [26] that cardinal-recognizing ITTMs can solve the halting problem for ITTMs. This is not true in general for α-ITRMs. There is, however, a natural and useful variant for α-ITRMs, the proof of which, which we will now sketch, follows the same idea as in [26].
Proposition 39.
For any $x \subseteq α$ and any α-ITRM-program P, $P^{x}$ will either halt in less than $card {(α)}^{+}$ many steps or not halt at all.
Proof.
It is proved in [8], Theorem 37 that $β (α)$ is strictly smaller than the next $Π_{3}$ -reflecting ordinal after α; this result relativizes to oracles. Now, the next $Π_{3}$ -reflecting ordinals after α is clearly smaller than the cardinal successor of α.32
³²
This, of course, is an overkill. Alternatively, one can, assuming that $P^{x}$ halts in τ many steps, form the $Σ_{1}$ -elementary hull H of $α + 1 \cup {x}$ in $L_{τ + ω}$ ; H will contain the halting computation D of $P^{x}$ , and we will have $card (H) ⩽ card (α) \cdot ω$ , so the transitive collapse of H will only contain elements of cardinality less than $card {(α)}^{+}$ , which will include D.

□
Proposition 40.
For each $k \in ω$ , α-cITRMs can solve the halting problem for α-ITRMs using k registers, uniformly in the oracle.
Proof.
Let P be an α-ITRM-program using $k \in ω$ many registers, and let $x \subseteq α$ . We use an extra register C. Our α-cITRM-program now works as follows: Use k registers to run $P^{x}$ , while simultaneously incrementing C by 1 for each step in the computation of $P^{x}$ . Once C overflows (i.e., contains 0), set the content of $R_{D}$ to 1 and let $P^{x}$ run on until it either halts – in which case we return “yes” – or the next cardinal time is reached, in which case $P^{x}$ has run for at least $card {(α)}^{+}$ many steps without halting and thus will never halt, so that we can return “no”. □
Remark 41.
Note that this does not mean that α-cITRMs can solve the halting problem for α-ITRMs. In fact, as Theorem 47 shows, this fails already for $α = ω$ .

Recall from the folklore that a “strong loop” in an infinite computation is a partial computation in which the first and the last state agree, and all states in between were in all components (active program line and register contents) at least as large as at this state. It is easy to see (see, e.g., [34]) that the presence of a strong loop implies that the program is not halting. Again by [34], a non-halting program will always eventually run into a strong loop.

Moreover, recall from [8] that the “looping time” of an α-ITRM-program P (possibly in some parameter and some oracle) is the minimal time τ such that the computation of P up to τ contains a strong loop. It was shown in [8] that $β (α)$ , the supremum of the α-ITRM-clockable ordinals, is also the supremum of the α-ITRM-looping times.
Definition 42.
For an ordinal α, $k \in ω$ , denote by $δ_{α} (k)$ the supremum of the α-ITRM-halting and looping times (with parameters) for programs using at most k registers.
Proposition 43.
For all infinite ordinals α and all $k \in ω$ , $δ_{α} {(k)}^{ω}$ is a common multiple of all α-ITRM-halting and looping times for programs using at most k registers.
Proof.
Let μ be the halting or looping time of some program using at most k registers. Then $μ < δ_{α} (k)$ by definition of $δ_{α} (k)$ , and so $δ_{α} {(k)}^{ω} ⩽ μ \cdot δ_{α} {(k)}^{ω} ⩽ δ_{α} (k) \cdot δ_{α} {(k)}^{ω} = δ_{α} {(k)}^{ω}$ . □
Remark 44.
We do not know whether Proposition 43 is optimal; in particular, we do not know whether it holds with $δ_{α} (k)$ in place of $δ_{α} {(k)}^{ω}$ . In particular, although that we know that looping times are clockable ([8], Corollary 38), the strategy used in the proof adds registers, and we do not know whether looping times for programs with k registers are always clockable with k registers.

The following “pulldown” strategy, here adapted to register machines, is basic in the analysis of cardinal-recognizing ITTMs as conducted, e.g., in Habic [26].
Lemma 45.

Let P be an ITRM-program using $k \in ω$ many registers. Then, for all $i \in ω$ and all $x \subseteq ω$ , $^{UCard} P^{x} (i)$ halts if and only if $^{A_{k + 1}^{x}} P^{x} (i)$ halts and both computations will have the same output.

More generally, let α be an ordinal, $k \in ω$ , P an α-ITRM-program using k many registers. Then, for all $ι, ρ \in α$ and all $x \subseteq α$ , $^{UCard} P^{x} (ρ, ι)$ halts if and only if $^{M_{δ_{α} {(k)}^{ω}}} P^{x} (ρ, ι)$ halts and both computations will have the same output.

Proof.

We claim that, for all $ι, δ \in On$ with $ι > 1$ and each $ρ < ω_{k + 1}^{CK}$ , the state of $^{UCard} P^{x} (i)$ at time $ℵ_{ι} + ω_{k + 1}^{CK, x} \cdot δ + ρ$ agrees with that of $^{A_{k + 1}^{x}} P^{x} (i)$ at time $ω_{k + 1}^{CK, x} \cdot (ι + δ) + ρ$ , which implies the claim: For it follows in particular that, if $^{Card} P^{x} (i)$ is in the halting state at time $ℵ_{ι} + ω_{k + 1}^{CK, x} \cdot δ + ρ$ and has r in the output register, then the same will hold for $^{A_{k + 1}^{x}} P^{x} (i)$ at time $ω_{k + 1}^{CK, x} (ι + δ) + ρ$ , and vice versa.

To prove the claim, it suffices to see that the claim holds for $δ = ρ = 0$ ; for, if the states of the first computation at time $ℵ_{ι}$ agrees with that of the second at time $ω_{k + 1}^{CK, x} \cdot ι$ , then, as long as $τ < ℵ_{ι + 1}$ (so that no cardinal-recognizing steps take place in the meantime), the state of the first computation at time $ℵ_{ι} + τ$ will also agree with that of the second at time $ω_{k + 1}^{CK, x} \cdot ι + τ$ . However, we know from Koepke [33], Theorem 9 that an ITRM-computation in the oracle x using k registers either halts in $< ω_{k + 1}^{CK, x}$ many steps or runs into a strong loop of length $ω_{k + 1}^{CK, x}$ , so that the states at times of the form $ω_{k + 1}^{CK, x} \cdot ι$ will all be the same. Since $ℵ_{ι}$ is uncountable and $ω_{k + 1}^{CK, x}$ is countable, $ℵ_{ι} = ω_{k + 1}^{CK, x} \cdot ℵ_{ι}$ is a multiple of $ω_{k + 1}^{CK, x}$ , so our claim is established.

The general claim follows by an analogous argument.
□
Lemma 46.

For each ITRM-program P and each $k \in ω$ , there is an ITRM-program $\tilde{P}$ which, for every $x \subseteq ω$ , computes the same function as $^{A_{k}^{x}} P$ .

More generally, if α is exponentially closed 33
³³
We assume exponential closure to be able to rely on the results from [8] used in the proof below. The result likely holds up without this assumption, at the price of some extra complications in the proof.

and BH, then, for every α-ITRM-program P, each $k \in ω$ and each parameter $ρ < α$ , there is an α-ITRM-program $\tilde{P}$ such that $\tilde{P} (ρ)$ computes the same function as $^{M_{δ_{α} {(k)}^{ω}}} P (ρ)$ .

Proof.

It was shown in Koepke [33], Theorem 10, that the supremum of the ITRM-clockable ordinals is $ω_{ω}^{CK}$ , Moreover, it was shown in [10], Theorem 6 that the ITRM-clockable ordinals do not have gaps, so that they are exactly the elements of $ω_{ω}^{CK}$ . Consequently, $ω_{k}^{CK}$ is ITRM-clockable for every $k \in ω$ . For fixed k, pick an ITRM-program Q that clocks $ω_{k}^{CK}$ . Let the program P be given. Let us denote the “detection” register of P by $R_{D}$ and let it initially contain 1. The desired program $\tilde{P}$ now works as follows: Run P and $Q_{k}$ simultaneously, by alternately carrying out single steps. When $Q_{k}$ halts, set $R_{D}$ to 0, then reset the registers used by $Q_{k}$ to 0 and start $Q_{k}$ again in the initial state. It is clear that this will work as desired at times of the form $ω_{k}^{CK} \times (ι + 1)$ . However, at limit times, $R_{D}$ will also contain 0, simply by the liminf rule for the register contents.

If $L_{α} ⊧ {ZF}^{-}$ , we know from [8] that a program using at most k many registers halts or strongly loops in less than $α^{k + 1}$ many steps, so we can simply replace $ω_{k}^{CK}$ by $α^{k}$ in the case $α = ω$ .

The other case of the general claim (i.e., when $L_{α} ⊭ {ZF}^{-}$ ) follows by the same strategy, once we have demonstrated the existence of a program $Q_{k}$ that clocks $δ_{α} {(k)}^{ω}$ . By assumption, there is program $H_{2 k + r}$ that solves the halting problem for α-ITRM-programs using at most $2 k + r$ registers, where r will be specified below. We can use this to implement a program that clocks $δ_{α} (k)$ by running through all pairs $(i, ρ) \in ω \times α$ , using $H_{2 k + r}$ to decide whether the computation of the ith program $P_{i}$ using at most k registers in the parameter ρ will halt. If it does, we run it until it halts. If it does not, we use $k + 1$ additional registers to run through all k-tuples τ of elements of α and additionally all natural numbers t; for each such tuple τ and each such t, there is a program S that runs $P_{i} (ρ)$ and waits for a strong loop with initial (and final) configuration $(t, τ)$ (i.e., active program line t and register contents τ). It is easy to see that this can be done with a fixed extra number r of registers. If such a loop is found, S halts. Using $H_{2 k + r}$ , we can check whether S will halt. If it does not, we know that $(t, τ)$ does not start a strong loop in the computation in question, so we continue with the next configuration. This will eventually terminate and reveal the starting configuration $(t_{0}, τ_{0})$ of such a strong loop. Once this is found, we run $P_{i} (ρ)$ until the configuration $(t_{0}, τ_{0})$ appears for the second time.

The routine just described halts at a time after all programs using at most k many registers have either halted or run into a strong loop, i.e., after time $δ_{α} (k)$ . It follows that $δ_{α} (k)$ is α-ITRM-clockable. We still need to argue, though, that $δ_{α} {(k)}^{ω}$ is also clockable. To see this, note that, since $L_{α} ⊭ {ZF}^{-}$ , it now follows from [8] (Theorem 35) that $δ_{α} (k)$ is α-ITRM-computable. Moreover, it is easy to see that there is an α-ITRM-program $P_{multiply}$ such that, when b and c are α-codese of ordinals β, γ, then $P_{multiply} (a, b)$ computes a code for $β γ$ .34
³⁴
This can be done as follows: For $ι_{0}$ , $ι_{1}$ , $ξ_{0}$ , $ξ_{1}$ , let $p (p (ι_{0}, ι_{1}), p (ξ_{0}, ξ_{1})) = 1$ if and only if $p (ι_{0}, ξ_{0}) \in a$ or $ι_{0} = ξ_{0}$ and $p (ι_{1}, ξ_{1}) \in b$ . This is clearly α-ITRM-computable.

Combining these two observations, it is easy to obtain a program $P_{\exp}$ that, on input $n \in ω$ , computes an α-code for $δ_{α} {(k)}^{n}$ . Combining these codes into one to form a code for the sum of all these finite powers, we obtain that $δ_{α} {(k)}^{ω}$ is α-ITRM-computable. By Lemma 34 of [8], it finally follows that $δ_{α} {(k)}^{ω}$ is also α-ITRM-clockable.
□
Theorem 47.
The computational strength of cITRMs is equal to that of ITRMs, i.e. ${COMP}_{cITRM} = {COMP}_{ITRM} = P (ω) \cap L_{ω_{ω}^{CK}}$ . This relativizes to oracles.
Proof.
Clearly, the ITRM-computable subsets of ω are also cITRM-computable. The other direction is now an easy consequence of Lemma 45 and Lemma 46: Given a real number $x \subseteq ω$ computable by the cITRM-program P, suppose that P uses k registers. By Lemma 45, x is computable by $^{A_{k + 1}} P$ and so, by Lemma 46, by some ITRM-program. □

Similarly, we can extend the BH-dichotomy by a third criterion: Theorem 48.
For each exponentially closed 35
³⁵
Again, exponential closure is a technical convenience rather than a necessary assumption.

ordinal α, the following are equivalent:
There is no universal α-ITRM (in the sense of Definition 15 above)

α is BH (i.e., for any $k \in ω$ , the halting problem for α-ITRMs using k registers is solvable by an α-ITRM).

The computational strength of α-ITRMs is equal to that of α-cITRMs.

Proof.
The equivalence of (1) and (2) is Theorem 16. We show that (2) ⇔ (3).

Assume (3). By Proposition 40, the bounded halting problem for α-ITRMs can be solved on α-cITRMs, for any number k of registers. By assumption, the same is true on α-ITRMs. Hence, we have (2).

We now show that (2) ⇒ (3). Assume that α is BH, and let $x \subseteq α$ be α-cITRM-computable. Let P be an α-ITRM-program, k the number of its registers, $ρ < α$ a parameter such that $^{UCard} P (ρ)$ computes $x \subseteq α$ . By Lemma 45, x is also computed by $^{M_{δ_{α} (k)}^{ω}} P (ρ)$ . By Lemma 46 there is an α-ITRM-program $\tilde{P}$ such that $\tilde{P} (ρ)$ computes the same function as $^{M_{δ_{α} (k)}^{ω}} P (ρ)$ . Thus x is α-ITRM-computable. □
Remark 49.
Note again that the proof of Theorem 48 does not yield the relativization to oracles. Whether or not Theorem 48 holds relative to oracles is currently open.

6. Iterations of α-ITRM-computable operators36
³⁶
This section is taken from our CiE 2022-paper [7].

In [8], it was proved that, if $L_{α} ⊧ {ZF}^{-}$ , then the supremum of the α-ITRM-clockable ordinals is $α^{ω}$ . This situation, however, is rather special, and it was still consistent with the results obtained in [8] that the natural generalization of Koepke’s result on the computational strength of ITRMs (see [33]) holds, namely that, if α is exponentially closed, then, unless $L_{α} ⊧ {ZF}^{-}$ , we have $β (α) = α^{+ ω}$ .37

³⁷
This conjecture was contained in an earlier version of [8]. However, in the time between submitting [8] and its publication, the results in this section were obtained, so that the conjecture never made it to the published version. This is briefly discussed in [8], p, 29, footnote 12.

We will now show that this conjecture fails dramatically even for the first exponentially closed ordinal $ε_{0} = ω^{ω^{ω^{...}}}$ greater than ω. In fact, we will show that already $β (ω^{ω})$ is way bigger than $ω_{ω}^{CK}$ .

Definition 50.

Let α be an ordinal. We say that $F : P (α) \to P (α)$ is α-ITRM-computable if and only if there is an α-ITRM-program P (possibly using a parameter $γ < α$ ) such that, for all $x \subseteq α$ and all $ι < α$ , we have $P^{x} (ι) ↓ = 1$ if and only if $ι \in F (x)$ and otherwise $P^{x} (ι) ↓ = 0$ . In this situation, we also say that P computes F.

Definition 51.

For each infinite ordinal α, pick an α-ITRM-computable bijection $p_{α} : α \times α \to α$ .38

³⁸

Since the set of α-ITRM-computable subsets of $α \times α$ is a superset of $L_{α + 1}$ , so that such a bijection is guaranteed to exist.

Let α be an infinite ordinal, and let $F : P (α) \to P (α)$ , $x \subseteq α$ . We define the iteration of F along α as follows:

$F^{0} (x) = x$

$F^{ι + 1} (x) = F (F^{ι} (x))$ .

When $δ ⩽ α$ is a limit ordinal, then $F^{δ} (x) = {p_{α} (ι, ξ) : ι < δ, ξ < α, ξ \in F^{ι} (x)}$ .

In addition we also write $F^{β \cdot k}$ for ${(F^{β})}^{k}$ .

Lemma 52.

Let α be an ordinal, and let $F : P (α) \to P (α)$ be an α-ITRM-computable function and let $n \in ω$ . Then $F^{n}$ , the n-th iteration of F, is α-ITRM-computable.

Proof.

We prove this by induction. For $n = 1$ , there is nothing to show. Let Q be an α-ITRM-program that computes F and let $Q_{n}$ be an α-ITRM-program that computes $F^{n}$ . Then an α-ITRM-program $Q_{n + 1}$ for computing $F^{n + 1}$ works as follows: Run Q. Whenever Q makes an oracle call to ask whether $ι \in F^{n} (x)$ , run $Q_{n}$ to evaluate this claim. When Q uses $r_{0}$ many registers and $Q_{n}$ uses $r_{1}$ many registers, this can be implemented on an α-ITRM using $r_{0} + r_{1}$ many registers. □

The above iteration technique yields a new program for every iteration index n. The key for our main result is Lemma 55, a uniform version of Lemma 52, which is our next goal.

The following lemma is a standard application of ordinal arithmetic; as a coding device in infinite computability, it was already used by Koepke in [33].

Lemma 53.

Let α be an ordinal, δ be a limit ordinal, $(γ_{ι} : ι < δ)$ a sequence of ordinals such that $γ_{ι} < α$ for each $ι < δ$ , and let ρ, η be arbitrary ordinals. Then ${liminf}_{ι < δ} α^{η + 2} \cdot ρ + α^{η} \cdot γ_{ι} = α^{η + 2} \cdot ρ + α^{η} \cdot {liminf}_{ι < δ} γ_{ι}$ .

Definition 54.

Let α, β be ordinals. We say that α is exponentially closed up to β if and only if, for all $γ < α$ and all $ι < β$ , we have $γ^{ι} < α$ .

The following crucial observation is similar in spirit to the iteration lemma for infinite time Blum–Shub–Smale machines, see [11], Lemma 10.

Lemma 55.

Let α be closed under ordinal multiplication, and let $F : P (α) \to P (α)$ be α-ITRM-computable. Moreover, let $η \in On$ be closed under ordinal addition. Then there is an $α^{η}$ -ITRM-program $P_{iterate}$ such that, for all $ι < η$ , $P_{iterate}^{x} (ι)$ computes $F^{ι} (x)$ . More precisely, for all $ι < η$ , $ξ < α$ , we will have $P_{iterate}^{x} (ι, ξ) ↓ = 1$ if and only if $ξ \in F^{ι} (x)$ and $P_{iterate}^{x} (ι, ξ) ↓ = 0$ , otherwise.

Proof.

Let P be an α–ITRM-program that computes F. Suppose that P uses n registers $R_{1}, \dots, R_{n}$ . The program $P_{iterate}$ will use registers $R_{1}^{'}, \dots, R_{n}^{'}$ for simulating the register contents of P, a register L for storing active program lines and various auxiliary registers that will not be mentioned explictly.

The rough idea is this: When $δ < η$ is a limit ordinal, the question whether $ξ \in F^{δ} (x)$ can be decided by writing ξ as $ξ = p_{α} (ξ_{0}, ξ_{1})$ and then deciding whether $ξ_{1} \in F^{ξ_{0}} (x)$ ; we will have $ξ_{0} < ξ$ . To compute $F^{ι + 1} (x)$ for a given $ι < α$ , $P_{iterate}$ will run P in the oracle $F^{ι} (x)$ . This may again call P for a lower iterate etc. Since α is well-founded, however, the nesting depth will remain finite at all times. At any time of this computation, there will be a configuration $(l^{ι}, r_{1}^{ι}, \dots, r_{n}^{ι})$ corresponding to the outermost run of P, along with finitely many configuration $(l^{ξ_{1}}, r_{1}^{ξ_{1}}, \dots, r_{n}^{ξ_{1}})$ corresponding to the first iteration etc., up to $(l^{0}, r_{1}^{0}, \dots, r_{n}^{0})$ for the top iteration which works on input x directly. The program $P_{iterate}$ will store this by having $α^{ι \cdot 2} \cdot l^{ι} + α^{ξ_{1} \cdot 2} \cdot l^{1} + \dots + α^{0} \cdot l^{0}$ in L and $α^{ι \cdot 2} \cdot r_{i}^{ι} + \dots + α^{0} \cdot r_{i}^{0}$ in $R_{i}^{'}$ . When the topmost computation terminates, it is taken off the stack and the computation “below” it is continued.

We now do it precisely. Suppose that $x \subseteq α$ is given in the oracle, and that some ordinal $ι < η$ is given in the first register. Our goal is to compute $F^{ι} (x)$ .

The computation proceeds in $ι + 1$ many “levels”, where a computation step takes place at level $ξ ⩽ ι$ when it belongs to an evaluation of $F^{ξ}$ . When an oracle call of the form $O (ζ)$ is made in level $ξ + 1$ , the computation enters level ξ; when it takes place in level δ with δ a limit ordinal and ζ is of the form $p_{α} (ζ_{0}, ζ_{1})$ , the computation continues at level $ζ_{0}$ with the computation of $F^{ζ_{0}} (ζ_{1})$ . For the sake of convenience, we use a register S for storing the sequence $(ξ_{1}, \dots, ξ_{k})$ of currently relevant levels in the form $α^{2 ξ_{1}} + \dots + α^{2 ξ_{k}}$ , where, of course $ξ_{1} > ξ_{2} > \dots > ξ_{k}$ .

We now describe how to carry out instructions at level $δ ⩽ ι$ (all contents of registers other than the ones explicitly mentioned are left unchanged). Note that δ can be reconstructed from the content of the line register L, the content of which will be of the form $α^{γ \cdot 2} \cdot ρ + α^{δ \cdot 2} \cdot l$ with $γ > δ$ and $l > 0$ (since, as we recall from the introduction, we start the enumeration of program lines with 1). The l appearing as the coefficient in this representation will be the index of a program line of P; depending on the content of this program line, the following steps are carried out:

(Before carrying out the other steps:) When $R_{i}$ contains an ordinal of the form $α^{γ \cdot 2} \cdot ρ + α^{δ \cdot 2 + 1}$ for any $i ⩽ n$ , replace it with $α^{γ \cdot 2} \cdot ρ$ (this corresponds to a reset after a register overflow).

The active program line contains the command $R_{i} + 1$ (i.e., incrementation of $R_{i}$ by 1): Read out the content of $R_{i}^{'}$ . It will be an ordinal of the form $α^{γ \cdot 2} \cdot ρ + α^{δ \cdot 2} \cdot r_{i}$ with $γ > δ$ ; replace it with $α^{γ \cdot 2} \cdot ρ + α^{δ \cdot 2} \cdot (r_{i} + 1)$ . Moreover, the content of L will be an ordinal of the form $α^{γ \cdot 2} \cdot ρ^{'} + α^{δ \cdot 2} \cdot l$ ; replace it with $α^{γ \cdot 2} \cdot ρ^{'} + α^{δ \cdot 2} \cdot (l + 1)$ .

The active program line contains the command $COPY (i, j)$ : Read out the contents of $R_{i}$ and $R_{j}$ , which will be of the forms $α^{γ_{0} \cdot 2} \cdot ρ + α^{δ \cdot 2} \cdot r_{i}$ and $α^{γ_{1} \cdot 2} \cdot ρ^{'} + α^{δ \cdot 2} \cdot r_{j}$ , where $δ < γ_{0}, γ_{1}$ . Replace the content of $R_{i}$ with $α^{γ_{0} \cdot 2} \cdot ρ + α^{δ \cdot 2} \cdot r_{j}$ ; modify the content of L as in the incrementation operation.

The active program line contains the command IF $R_{i} = R_{j}$ GOTO l: Read out the contents of $R_{i}$ and $R_{j}$ , which will be of the forms $α^{γ_{0} \cdot 2} \cdot ρ + α^{δ \cdot 2} \cdot r_{i}$ and $α^{γ_{1} \cdot 2} \cdot ρ^{'} + α^{δ \cdot 2} \cdot r_{j}$ , where $γ_{0}, γ_{1} > δ$ ; moreover, let $α^{γ_{2} \cdot 2} \cdot ρ^{″} + α^{δ \cdot 2} \cdot l^{'}$ be the content of L, where $δ < γ_{2}$ . If $r_{i} = r_{j}$ , replace the content of L with $α^{γ_{2} \cdot 2} \cdot ρ^{″} + α^{δ \cdot 2} \cdot l$ ; if not, replace it with $α^{γ_{2} \cdot 2} \cdot ρ^{″} + α^{δ \cdot 2} \cdot (l^{'} + 1)$ .

The active program line contains the oracle call $O (ξ)$ and $δ = \bar{δ} + 1 < ι$ is a successor ordinal: Let $α^{γ_{0} \cdot 2} \cdot ρ + α^{δ \cdot 2} \cdot r$ be the content of $R_{1}$ , and let $α^{γ_{1} \cdot 2} \cdot ρ^{'} + α^{δ \cdot 2} \cdot l$ be the content of L, where $δ < γ_{0}, γ_{1}$ . Replace the content of $R_{1}$ by $α^{γ_{0} \cdot 2} \cdot ρ + α^{δ \cdot 2} \cdot r + α^{\bar{δ} \cdot 2} \cdot ξ$ and replace the content of L by $α^{γ_{1} \cdot 2} \cdot ρ^{″} + α^{δ \cdot 2} \cdot l + α^{\bar{δ} \cdot 2} \cdot 1$ . Also, we are now working at level $\bar{δ}$ , so we add $α^{\bar{δ} \cdot 2}$ to the content of S.

The active program line contains the oracle call $O (ξ)$ and $δ < ι$ is a limit ordinal: Calculate $ξ_{0}$ , $ξ_{1}$ with $ξ = p_{α} (ξ_{0}, ξ_{1})$ . If $ξ_{0} ⩾ δ$ , return 0 and modify the content of L as in the incrementation operation. (Note that this output will be right due to the definition of the iteration at limit levels). If $ξ_{0} < δ$ , we need to check whether $ξ_{1} \in F^{ξ_{0}} (x)$ . The computation will then enter level $ξ_{0}$ . Thus, we add $α^{ξ_{0} \cdot 2}$ to the content of S. Let $α^{γ_{0} \cdot 2} \cdot ρ + α^{δ \cdot 2} \cdot r$ be the content of $R_{1}$ , and let $α^{γ_{1} \cdot 2} \cdot ρ^{'} + α^{δ \cdot 2} \cdot l$ be the content of L, where $δ < γ_{0}, γ_{1}$ . Replace the content of $R_{1}$ by $α^{γ_{0} \cdot 2} \cdot ρ + α^{δ \cdot 2} \cdot r + α^{ξ_{0} \cdot 2} \cdot ξ_{1}$ and replace the content of L by $α^{γ_{1} \cdot 2} \cdot ρ^{″} + α^{δ \cdot 2} \cdot l + α^{ξ_{0} \cdot 2} \cdot 1$ .

The active program line contains the oracle call $O (ξ)$ and $δ = 0$ : This means that we are simply making a call to the given oracle, with no iterations of F applied to it. Let $α^{γ_{0} \cdot 2} \cdot ρ + α^{δ \cdot 2} \cdot r$ be the content of $R_{1}$ . Check whether $ξ \in x$ (recall that x is our oracle). If yes, replace the content of $R_{1}$ by $α^{γ_{0} \cdot 2} \cdot ρ + α^{δ \cdot 2} \cdot 1$ , otherwise, replace the content of $R_{1}$ by $α^{γ_{0} \cdot 2} \cdot ρ$ . Modify the content of L as in the incrementation operation.

When the coefficient of the minimal power of α in the Cantor normal form representation of the content of L is the index of a line of P that contains the “halt” command:39

³⁹

In line with the convention in [19], we can regard any line not occuring in the program as containing the halting command.

Let

R_{1}

contain

α^{γ_{0} \cdot 2} \cdot ρ^{'} + α^{γ_{1} \cdot 2} \cdot r + α^{δ \cdot 2} \cdot r^{'}

; replace it with

α^{γ_{0} \cdot 2} \cdot ρ^{'} + α^{γ_{1} \cdot 2} \cdot r^{'}

(the result of the oracle call is passed down to the level that made the call).

For $i \in {2, \dots, n}$ , let $R_{i}$ contain $α^{γ_{0, i} \cdot 2} \cdot ρ_{i} + α^{γ_{1, i} \cdot 2} \cdot r_{i} + α^{δ \cdot 2} \cdot r_{i}^{'}$ ; replace it with $α^{γ_{0, i} \cdot 2} \cdot ρ_{i} + α^{γ_{1, i} \cdot 2} \cdot r_{i}$ (the topmost layer corresponding to the now finished computation is deleted).

Also, if the content of S is $α^{ν} \cdot ρ + α^{δ \cdot 2}$ , replace it with $α^{ν} \cdot ρ$ (the last entry in the sequence of currently relevant levels is deleted).

Finally, let the content of L be $α^{γ_{0} \cdot 2} \cdot ρ^{″} + α^{γ_{1} \cdot 2} \cdot l + α^{δ \cdot 2} \cdot l^{'}$ ; replace it by $α^{γ_{0} \cdot 2} \cdot ρ^{″} + α^{γ_{1} \cdot 2} \cdot (l + 1)$ (the active program line is increased by 1, as the oracle command has been carried out).

$P_{iterate}$ now works on input $(ι, ξ) \in η \times α$ by first instantiating L with $α^{ι \cdot 2}$ , $R_{1}$ with $α^{ι \cdot 2} \cdot ξ$ and $R_{i}$ with 0 for $i \in {2, 3, \dots, n}$ and then carrying out the above instructions. By additive closure of η, we will have $γ \cdot 2 < η$ whenever $γ < η$ , so that all register contents generated in this procedure will be below $α^{η}$ . By induction on ι and using Lemma 53, the program works as desired. □

We note some important consequences of this result:

Corollary 56.

Let $α > ω$ be exponentially closed, and let $β < α$ . Moreover, let $F : P (β) \to P (β)$ be a β-ITRM-computable operator. Then:

There is an α-ITRM-program P such that, for each $x \subseteq β$ and each $ι < α$ , $P^{x} (ι)$ computes $F^{ι} (x)$ .

$F^{α}$ , the α-th iteration of F, is α-ITRM-computable.

$F^{α \cdot i}$ , the $α \cdot i$ -th iteration of F, is α-ITRM-computable, for every $i \in ω$ .

Proof.

Since $β^{ι + 1} < α$ by exponential closure of α, is a direct consequence of Lemma 55.

In order to decide whether $p_{α} (ξ_{0}, ξ_{1}) \in F^{α} (x)$ , use the algorithm P from (1) to decide whether or not $ξ_{1} \in F^{ξ_{0}} (x)$ .

This is a consequence of (2) and Lemma 52.

□

We now extract information on $β (α)$ , for various values of α, thus, in particular, refuting the conjecture mentioned above that $β (α) = α^{+ ω}$ unless $L_{α} ⊧ {ZF}^{-}$ .

Definition 57.

Let α be an ordinal. By recursion, we define, for $ι \in On$ : $^{0} α = α$ , $^{ι + 1} α = α^{ι α}$ , $^{ι} α = ⋃_{ξ < ι}^{ξ} α$ for ι a limit ordinal.

As usual, we denote $^{ω} ω$ by $ε_{0}$ .

Recall the following result from Koepke and Miller [34]:

Definition 58 (Cf., e.g., [43], p. 48).

Let $x \subseteq ω$ . The hyperjump of x is the set of all $i \in ω$ such that the i-th Turing program computes a well-ordering in the oracle x. For $ι < ε_{0}$ , denote by ${HJ}^{ι} (x)$ the ι-th hyperjump of x; ${HJ}^{ι}$ denotes the ι-th hyperjump of 0.

Theorem 59.
[See [ 34 ], Theorem 1] There is an ITRM-program $P_{HJ}$ such that, for each $x \subseteq ω$ , $P_{HJ}^{x}$ computes $HJ (x)$ .
Corollary 60.

For any $n \in ω$ , the function $F_{n} : x \mapsto {HJ}_{ω^{n}} (x)$ , defined on $P (ω)$ , is $ω^{ω^{n}}$ -ITRM-computable.

For $n \in ω$ , we have $β (ω^{ω^{n}}) ⩾ ω_{ω^{n + 1}}^{CK}$ . In particular, we have $β (ω^{ω}) ⩾ ω_{ω^{2}}^{CK}$ .

We have $β (ε_{0}) ⩾ ω_{ε_{0} \cdot ω}^{CK}$ .

Proof.

We prove this by induction. For $n = 0$ , this is Theorem 59. Now suppose that $x \mapsto {HJ}_{ω^{n}} (x)$ is $ω^{ω^{n}}$ -ITRM-computable, say by the program $P_{n}$ . By Lemma 55, there is an ${(ω^{ω^{n}})}^{ω}$ -ITRM-program Q that computes $F_{n}^{i} (x)$ on input $i \in ω$ ; note that ${(ω^{ω^{n}})}^{ω} = ω^{ω^{n + 1}}$ . By running $Q (i, j)$ on input $p_{ω} (i, j)$ , we obtain an $ω^{ω^{n + 1}}$ -ITRM-program $Q^{'}$ that computes $F_{n}^{ω} (x)$ in the oracle x. But $F_{n}^{ω}$ is just $F_{n + 1}$ .

From (1), we have that ${HJ}_{ω^{n}}$ is $ω^{ω^{n}}$ -ITRM-computable; using Lemma 52, we obtain that ${HJ}_{ω^{n} \cdot k}$ is $ω^{ω^{n}}$ -ITRM-computable for every $k \in ω$ . Therefore, a code for $ω_{ω^{n} \cdot k}^{CK}$ is $ω^{ω^{n}}$ -ITRM-computable for every $k \in ω$ . Consequently, the supremum $β (ω^{ω^{n}})$ of the ordinals with $ω^{ω^{n}}$ -ITRM-computable codes is at least $ω_{ω^{n + 1}}^{CK}$ .

By Theorem 59 and Corollary 56, ${HJ}_{ε_{0} \cdot k}$ is $ε_{0}$ -ITRM-computable for any $k \in ω$ . Thus, $β (ε_{0})$ is larger than $ω_{ε_{0} \cdot k}^{CK}$ for any $k \in ω$ , and thus $β (ε_{0}) ⩾ ω_{ε_{0} \cdot ω}^{CK}$ .
□

The same approach works in a much more general situation:
Definition 61.
Let us say that α is ITRM-countable if and only if there is an α-ITRM-computable bijection $f : ω \to α$ . More generally, let us say that α is ITRM-effectively β-codable if and only if there is an α-ITRM-computable bijection $f : β \to α$ .
Remark 62.
In particular, since subsets definable over $L_{α}$ can always be computed on an α-ITRM, α is ITRM-countable whenever α is an index (i.e., an ordinal α such that $(L_{α + 1} ∖ L_{α}) \cap P (ω) \neq \emptyset$ ). Note that ITRM-countability implies that there is an α-ITRM-computable real number that codes α.
Corollary 63.
Let $α > ω$ be exponentially closed and ITRM-countable. Then $β (α) ⩾ α^{+ α \cdot ω}$ .
Proof.
Let $x \subseteq ω$ be an α-ITRM-computable code for α. By applying Corollary 56(3) to x and the (ω-)ITRM-program that computes hyperjumps from Theorem 59, we see that ${HJ}^{α \cdot k} (x)$ is α-ITRM-computable for every $k \in ω$ . But then, we have $β (α) ⩾ α^{+ α \cdot k}$ for every $k \in ω$ , i.e., $β (α) ⩾ α^{+ α \cdot ω}$ . □
Remark 64.
We do not know whether lower bounds obtained in the above results are optimal for any particular value of α.

Besides raw size, one can also obtain some structural information on $β (α)$ from these considerations. It was shown in Proposition 40 of [8] that $β (α)$ is never admissible and that, if α is an index, then $β (α)$ is a limit of admissible ordinals. This can now be considerably strengthened.
Definition 65.
Let α be an ordinal. We say that α is a level 0 limit of admissible ordinals if and only if α is admissible. For $ι \in On$ , α is a level $ι + 1$ limit of admissible ordinals if and only if α is a limit of level ι limits of admissible ordinals. For $δ \in On$ a limit ordinal, α is a level δ limit of admissible ordinals if and only if α is a level ι admissible ordinal for all $ι \in (0, δ)$ .40
⁴⁰
Note that this not require ι-limits of admissible ordinals to be admissible for any $ι > 1$ .

We write $Lev (α, ξ)$ to express that α is a level ξ-limit of admissible ordinals.

Moreover, we write ${[α]}_{Adm}^{ξ}$ for the smallest level ξ limit of admissible ordinals that is strictly larger than α (thus, ${[α]}_{Adm}^{0} = α^{+}$ ) and ${[α]}_{Adm}^{ξ, ι}$ for the ι-th smallest such limit.
Lemma 66.
For each $ι \in On$ , there is an $ω^{ω^{ι}}$ -ITRM-program $P_{ι - limit}$ which, given a real number coding an ordinal α, computes a real number coding ${[α]}_{Adm}^{ι}$ .
Proof.
We prove the claim by induction on ι. The case $ι = 0$ is just the fact that (ω-)ITRMs can compute hyperjumps (and thus admissible successors). The limit case is trivial, since $ω^{ω^{δ}}$ -ITRMs can simulate $ω^{ω^{ι}}$ -ITRMs for all $ι < δ$ (uniformly on input ι). We are thus left with the successor case. So suppose that the $ω^{ω^{ι}}$ -ITRM-program $P_{ι - limit}$ is given, which computes a function F as in the lemma. By Lemma 55, we can compute the ω-th iterate of F on an ${(ω^{ω^{ι}})}^{ω}$ -ITRM, i.e., on an $ω^{ω^{ι + 1}}$ -ITRM. Given a real number c coding an ordinal γ, this yields a real number that encodes ${[γ]}_{Adm}^{ι, i}$ for all $i \in ω$ . From c, one recursively (in the classical sense, and uniformly in c) obtains a real number coding the ordinal sum $ρ : = Σ_{i \in ω} {[γ]}_{Adm}^{ι, i}$ , which is equal to ${[γ]}_{Adm}^{ι + 1}$ . □
Corollary 67.
Let $α > ω$ be exponentially closed and ITRM-countable. Then $β (α)$ is a level α limit of admissible ordinals.
Proof.
It follows from the ITRM-countability of α that in fact every ordinal smaller than $β (α)$ has an α-ITRM-computable real code: For, if $f : ω \to α$ is an α-ITRM-computable bijection, then so is $f^{- 1} : α \to ω$ and so, if $x \subseteq α$ is any α-ITRM-computable set coding an ordinal ρ, then ${f^{- 1} (ι) : ι \in x}$ is an ITRM-computable real number which also codes ρ.

Since α is exponentially closed, α is a limit ordinal. Let $ι < α$ . Hence, if $γ < β (α)$ , there is an α-ITRM-computable real number c that codes γ. By Lemma 66, $\hat{γ} : = {[γ]}_{Adm}^{ι}$ is $ω^{ω^{ι}}$ -computable from the input c; since $ω^{ω^{ι}} < α$ by exponential closure, $\hat{γ}$ has an α-ITRM-computable code, so $\hat{α} < β (α)$ and, by definition, $\hat{α}$ is a level ι limit of admissible ordinals. Since γ was arbitrary, $β (α)$ must be a limit of such ordinals. □

Analyzing the proof of Corollary 63 – and the auxiliary results leading there – one notes that the iteration technique just described never leads to a register overflow, so that the lower bounds just obtained in fact hold true already for the α-wITRMs as well:
Corollary 68.
Let $α > ω$ be exponentially closed and wITRM-countable. Then $β^{w} (α) ⩾ α^{+ α \cdot ω}$ .

In the case $α = ω$ , it is known that α-ITRMs are far stronger than α-wITRMs: Namely, the wITRM-computable subsets of ω are exactly those in $L_{ω_{1}^{CK}}$ , while the ITRM-computable ones are those in $L_{ω_{ω}^{CK}}$ . As we just noted, the techniques for obtaining lower bounds just described are insensitive to the distinction between resetting and unresetting machines. This leads to the following question:
Question 69.
Are there any exponentially closed 41
⁴¹
Note that the examples given in Proposition 2 above are far from being exponentially closed.

values of α such that $β (α) = β^{w} (α)$ , i.e. such that the computational strength of α-ITRMs is the same as that of α-wITRMs?
6.1. Uncountable α

The lower bounds obtained from the iteration lemma above can only work when α is countable. In this section, we indicate how Abramson’s and Sacks’ “lifting” of results of Gostanian [25] on Gandy ordinals to the uncountable in [1] can be exploited to yield information on α-ITRM-computability for certain uncountable values of α. For the sake of brevity, simplicity and surveyability, we restrict ourselves to the case $α = ℵ_{ω}^{+}$ treated in [1]; further generalizations are deferred to later work. (The argument would equally well work for ${(ℵ_{ω}^{L})}^{+}$ .)

In [1], the authors prove that $ℵ_{ω}^{+}$ is Gandy, i.e., that the supremum of the $ℵ_{ω}^{+}$ -recursive ordinals is ${(ℵ_{ω}^{+})}^{+}$ . Clearly, α-recursive sets are also α-ITRM-computable, and so this implies that $β (ℵ_{ω}^{+}) ⩾ {(ℵ_{ω}^{+})}^{+}$ ; indeed, this much was observed in [8]. However, in order to use the strength of the iteration lemma, this is not enough: rather than being able to go from $ℵ_{ω}^{+}$ to ${(ℵ_{ω}^{+})}^{+}$ , we would need a uniform way – i.e., an α-ITRM-program – that allows us to go from some $x \subseteq α$ that codes a well-ordering to $ω_{1}^{CK, x}$ , i.e., the smallest ordinal $β > α$ such that $L_{β} [x]$ is admissible.

Such a program can indeed be obtained from the proof of Theorem 5 of [1] by a relativization of the construction; we will offer a brief sketch of the general strategy and the necessary adaptations.

We use the following generalization of Theorem 1 of [34]:

Lemma 70.
[See [ 4 ], Theorem 2.3.25] If α is ITRM-singular, then there is an α-ITRM-program $P_{ifs}$ (“ill-founded sequence”) such that, for any $x \subseteq α$ that codes a tree $T$ on α, $P_{ifs}^{x}$ outputs ∅ when $T$ is well-founded and otherwise outputs an infinite branch of $T$ . 42
⁴²
More precisely, $P_{ifs}^{x} (i)$ will output the i-th element of an infinite branch of $T$ , for every $i \in ω$ .

Lemma 71.
If α is ITRM-singular, then there is an α-ITRM-program $P_{wfp}$ (“well-founded part”) such that, for any $x \subseteq α$ that encodes a structure $(X, E)$ , $P^{x}$ computes a subset of α that codes the well-founded part of X with respect to E.
Proof.
This follows from Lemma 70 by cutting off the given structure $(X, E)$ below any given x and applying the well-foundedness check to determine whether there is an infinite E-decreasing sequence that starts with x. □

The general strategy in [1] is the following: They define an $ℵ_{ω}^{+}$ -recursive tree $T$ , guaranteed to have an infinite branch, whose infinite branches encode – possibly ill-founded – models of KP for which $ℵ_{ω}^{+}$ belongs to the well-founded part. Since well-founded parts of admissible sets are known to be admissible, it follows that the height of the well-founded part of such a model must be of height at least ${(ℵ_{ω}^{+})}^{+}$ , from which one obtains the Gandyness of $ℵ_{ω}^{+}$ .

It is not hard to modify their construction to obtain, for a given $x \subseteq ℵ_{ω}^{+}$ , a tree $T_{x}$ that is uniformly $ℵ_{ω}^{+}$ -ITRM-computable in the oracle x, has at least one infinite branch and whose infinite branches encode models of KP whose well-founded part includes $ℵ_{ω}^{+}$ and x. All that is required is to add, in the proof of Theorem 5 of [1], a new variable χ to the language $L^{}$ and the statements ${d_{γ} \in χ : γ \in x} \cup {d_{γ} \notin χ : γ \notin χ}$ to the theory $T^{}$ and modify condition (viii) to demand that $(V, G) \in L_{ℵ_{ω}^{+}} [x]$ . The proof that the tree arising in this way has an infinite branch and that one obtains a model with the required properties from each infinite branch then works as in [1]. Now, by Lemma 70, we can uniformly compute a code $b \subseteq ℵ_{ω}^{+}$ for such a branch on an $ℵ_{ω}^{+}$ -ITRM in $T^{}$ . From b, one can then easily obtain a code $m \subseteq ℵ_{ω}^{+}$ that encodes a model of KP with $ℵ_{ω}^{+}$ and x in its well-founded part. We can then use Lemma 71 to compute a code $w \subseteq ℵ_{ω}^{+}$ for the well-founded part of m. Using bounded truth predicate evaluation (see, e.g., [4], Theorem 2.3.28) in m, this yields a code for the set of ordinals in m, which will be a code of an ordinal $⩾ ω_{1}^{CK, x}$ .

Since this works for any $x \subseteq ℵ_{ω}^{+}$ , it is now possible to proceed as above to obtain the following: Theorem 72.
We have* $β ({(ℵ_{ω}^{+})}^{+}) ⩾ {(ℵ_{ω}^{+})}^{+ (ℵ_{ω}^{+} \cdot ω)}$ .

7. Open questions

While the above refutes a natural conjecture on the computational strength of α-ITRMs by providing some lower bounds, the value of $β (α)$ is still unknown for all values of α unless $α = ω$ or $L_{α} ⊧ {ZF}^{-}$ . Some special cases that might be good starting points would be to determine $β (ω^{ω})$ , $β (ε_{0})$ , $β (ℵ_{ω})$ or $β (ω_{1}^{CK})$ .

A crucial feature of ω-ITRMs established by Koepke and Miller in [34], the generalization of which may well shed light on the computational power of α-ITRMs, is the solvability of the bounded halting problem. Although we are able to prove that, for each ordinal α, there is either a universal α-ITRM-program or the bounded halting problem for α-ITRMs is solvable, we are in a quite unsatisfying situation: We do not know which alternative holds for a single exponentially closed ordinal α except when $α = ω$ or when $L_{α} ⊧ {ZF}^{-}$ . A crucial step in further work on the computational strength of α-ITRMs might be to generalize the work on the cases $α = ω$ and $L_{α} ⊧ {ZF}^{-}$ by seeing whether the computational strength of α-ITRMs can be characterized by iterating some operator that is β-ITRM-computable for some $β ⩽ α$ . We also currently do not know whether there are values of α for which the lower bounds obtained in this paper are optimal. We expect that proof-theoretical considerations on iterated admissibility and inductive operators such as Jäger [30] and [3] will become relevant in further investigations.

For the time being, we thus restrict ourselves to the following rather modest questions:

Question 73.

Determine $β (α)$ or $β^{w} (α)$ for any value of α other than $α = ω$ or α a ${ZF}^{-}$ -ordinal.

Question 74.

Characterize the u-weak ordinals, i.e., those for which $β^{w} (α) = α$ (and thus, ${COMP}_{α - wITRM} = Δ_{1} (L_{α})$ ).

Footnotes

Acknowledgements

We thank the three anonymous referees of [] for their valuable feedback, in particular for pointing out several subtle typos and the two anonymous referees of this paper for providing extensive comments that helped to considerably improve the exposition.

References

Abramson and

Sacks, Uncountable Gandy ordinals, Journal of the London Mathematical Societys2-14(3) (1976).

Boolos and

Putnam, Degrees of unsolvability of constructible sets of integers, Journal of Symbolic Logic33 (1968).

Buchholz,

Feferman and

Pohlers, Iterated inductive definitions and subsystems of analysis: Recent proof-theoretical studies, Lecture Notes in Mathematics897 (1981).

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

Carl, Space and time complexity for Infinite Time Turing Machines, Journal of Logic and Compution30 (2020).

Carl, Effectivity and reducibility with ordinal Turing machines, Computability10(4) (2021). doi:10.3233/COM-210307.

Carl, Lower bounds on β(α), in: Revolutions and Revelations in Computability. CiE 2022, Lecture Notes in Computer Science, Vol. 13359, 2022.

Carl, Taming Koepke’s zoo II: Register machines, Annals of Pure and Applied Logic173(3) (2022). doi:10.1016/j.apal.2021.103041.

Carl, Space-bounded OTMs and

{REG}^{\infty}

, Computability11(1) (2022). doi:10.3233/COM-200327.

10.

Carl,

Fischbach,

K.P.R.

Miller,

Nasfi and

Weckbecker, The basic theory of Infinite Time Register Machines, Archive for Mathematical Logic49 (2010).

11.

Carl and

Galeotti, Resetting Infinite Time Blum–Shub–Smale-Machines, 2020.

12.

Carl,

Galeotti and

Passmann, Realisability for infinitary intuitionistic set theory, Annals of Pure and Applied Logic174(6) (2023). doi:10.1016/j.apal.2023.103259.

13.

Carl,

Ouazzani and

Welch, Taming Koepke’s zoo, in: Sailing Routes in the World of Computation, Lecture Notes in Computer Science, Vol. 10936, 2017.

14.

Carl and

Schlicht, Randomness via infinite computation and effective descriptive set theory, Journal of Symbolic Logic83(2) (2018). doi:10.1017/jsl.2018.3.

15.

Carl,

Schlicht and

Rin, Reachability for Infinite Time Turing Machines with long tapes, Logical Methods in Computer Science16(2) (2020).

16.

Carl,

Schlicht and

Welch, 2022, Countable ranks at the first and second projective levels.

17.

Carl,

Schlicht and

Welch, Decision times of infinite computations, Notre Dame Journal of Formal Logic63(2) (2022). doi:10.1215/00294527-2022-0012.

18.

Coskey and

Hamkins, Infinite time decidable equivalence relation theory, Notre Dame Journal of Formal Logic52(2) (2011). doi:10.1215/00294527-1306199.

19.

Cutland, Computability. An Introduction to Recursive Function Theory, Cambridge University Press, 1980.

20.

Deolalikar,

Hamkins and

Schindler, P ≠ NP ∩ co-NP for Infinite Time Turing Machines, Journal of Logic and Computation15 (2005).

21.

Fischbach, The Church–Turing thesis for ordinal computable functions, Master’s thesis, Rheinische Friedrich-Wilhelms-Universität, Bonn, 2010.

22.

Fischbach and

Seyfferth, On λ-definable functions on ordinals, in: The Nature of Computation. Logic, Algorithms, Applications. CiE 2013, Lecture Notes in Computer Science, Vol. 7921, 2013.

23.

Galeotti and

Nobrega, Towards computable analysis on the generalised real line, in: Unveiling Dynamics and Complexity, Lecture Notes in Computer Science, Vol. 10307, 2017.

24.

Gitman,

Johnstone and

Hamkins, What is the theory ZFC without power set?, Mathematical Logic Quarterly62(4) (2011).

25.

Gostanian, The next admissible ordinal, Annals of Mathematical Logic17(1–2) (1979). doi:10.1016/0003-4843(79)90025-1.

26.

Habic, Cardinal-recognizing Infinite Time Turing Machines, in: The Nature of Computation. Logic, Algorithms, Applications. CiE 2013, Lecture Notes in Computer Science, Vol. 7921, 2013.

27.

Hamkins and

Lewis, Infinite Time Turing Machines, Journal of Symbolic Logic65(2) (2000). doi:10.2307/2586556.

28.

Hamkins and

Lewis, Post’s problem for supertasks has both positive and negative solutions, Archive for Mathematical Logic41(6) (2002). doi:10.1007/s001530100112.

29.

Hamkins,

Miller,

Seabold and

Warner, Infinite time computable model theory, in: New Computational Paradigms: Changing Conceptions of What Is Computable, Springer, New York, 2008.

30.

Jäger, Iterating admissibility in proof theory, in: Proceedings of the Herbrand Symposium, Logic Colloquium 1981,

Stern, ed., 1982.

31.

Koepke, Turing computations on ordinals, The Bulletin of Symbolic Logic11(3) (2005). doi:10.2178/bsl/1122038993.

32.

Koepke, Infinite time register machines, in: Logical Approaches to Computational Barriers, Lecture Notes in Computer Science, Vol. 3988, 2006.

33.

Koepke, Ordinal computability, in: Mathematical Theory and Computational Practice, Lecture Notes in Computer Science, Vol. 5635, 2009.

34.

Koepke and

Miller, An enhanced theory of Infinite Time Register Machines, in: Logic and Theory of Algorithms, Lectures Notes in Computer Science, Vol. 5028, 2008.

35.

Koepke and

Seyfferth, Ordinal machines and admissible recursion theory, Annals of Pure and Applied Logic160 (2009). doi:10.1016/j.apal.2009.01.005.

36.

Koepke and

Seyfferth, Towards a theory of infinite time Blum–Shub–Smale machines, in: How the World Computes. Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, Lecture Notes in Computer Science, Vol. 7318, 2012.

37.

Koepke and

Siders, Computing the recursive truth predicate on ordinal register machines, in: Logical Approaches to Computational Barriers, Computer Science Report Series, Vol. 7, 2006.

38.

Koepke and

Siders, Register computations on ordinals, Archive for Mathematical Logic47 (2008).

39.

Madore, A Zoo of Ordinals, 2017.

40.

Monin and

P.A.

d’Auriac, Genericity and randomness with Ittms, Journal of Symbolic Logic84(4) (2019). doi:10.1017/jsl.2019.62.

41.

Passmann, The first-order logic of CZF is intuitionistic first-order logic, Journal of Symbolic Logic (2022).

42.

Rin, The computational strengths of α-tape Infinite Time Turing Machines, Annals of Pure and Applied Logic165(9) (2014). doi:10.1016/j.apal.2014.04.016.

43.

Sacks, Higher Recursion Theory, Cambridge University Press, 2017.

44.

P.K.R.

Siders, Minimality considerations for ordinal computers modeling constructibility, Theoretical Computer Science394 (2008). doi:10.1016/j.tcs.2007.12.012.

45.

Welch, Eventually Infinite Time Turing Degrees: Infinite time decidable reals, Journal of Symbolic Logic65(3) (2000).

46.

Welch, Characteristics of discrete transfinite time Turing machine models: Halting times, stabilization times, and normal form theorems, Theoretical Computer Science410 (2009).

Lower bounds on β ( α ) and other properties of α -register machines

Abstract

Keywords

1. Introduction

1 But also in other ways, for example, by stipulating that the content of a tape cell may only change finitely often.

4 That we allow the simultaneous comparison of two finite sequences, rather than just two, registers, has again technical advantages explained in [8], p. 2

16 In [4], Exercise 2.3.10, it is shown how the proof can be generalized to ordinals of the form ω · k for k ∈ ω .

18 We point out that, for ordinal register machines (ORMs), which have no bound on their register contents, there is indeed a universal machine with 10 registers, see Koepke and Siders [44]. However, since overflows are ruled out for these machines, this seems to bear little analogy to α-ITRMs.

37 This conjecture was contained in an earlier version of [8]. However, in the time between submitting [8] and its publication, the results in this section were obtained, so that the conjecture never made it to the published version. This is briefly discussed in [8], p, 29, footnote 12.

Footnotes

Acknowledgements

References

¹
But also in other ways, for example, by stipulating that the content of a tape cell may only change finitely often.

⁴
That we allow the simultaneous comparison of two finite sequences, rather than just two, registers, has again technical advantages explained in [8], p. 2

¹⁶
In [4], Exercise 2.3.10, it is shown how the proof can be generalized to ordinals of the form $ω \cdot k$ for $k \in ω$ .

¹⁸
We point out that, for ordinal register machines (ORMs), which have no bound on their register contents, there is indeed a universal machine with 10 registers, see Koepke and Siders [44]. However, since overflows are ruled out for these machines, this seems to bear little analogy to α-ITRMs.

³⁷
This conjecture was contained in an earlier version of [8]. However, in the time between submitting [8] and its publication, the results in this section were obtained, so that the conjecture never made it to the published version. This is briefly discussed in [8], p, 29, footnote 12.