Space-bounded OTMs and REG ∞

Abstract

An important theorem in classical complexity theory is that $REG = LOGLOGSPACE$ , i.e., that languages decidable with double-logarithmic space bound are regular. We consider a transfinite analogue of this theorem. To this end, we introduce deterministic ordinal automata (DOAs) and show that they satisfy many of the basic statements of the theory of deterministic finite automata and regular languages. We then consider languages decidable by an ordinal Turing machine (OTM), introduced by P. Koepke in 2005 and show that if the working space of an OTM is of strictly smaller cardinality than the input length for all sufficiently long inputs, the language so decided is also decidable by a DOA, which is a transfinite analogue of $LOGLOGSPACE \subseteq REG$ ; the other direction, however, is easily seen to fail.

Keywords

Regular language deterministic finite automaton complexity theory ordinal turing machine ordinal computability

1. Introduction

Ordinal Turing machines (OTMs), introduced by P. Koepke in [10] and independently by B. Dawson in [5], are a well-established and well-studied model of infinitary computability. Roughly, an OTM is a Turing machine with a tape of proper class size, whose cells are indexed with ordinals, and transfinite ordinal working time. When restricting the tape length of an OTM to ω, one obtains the Infinite Time Turing Machines (ITTMs), introduced in 2000 by J. Hamkins and A. Lewis ([6]) as the first machine model of infinitary computability. One attractive feature of OTMs when compared with ITTMs is that OTMs exhibit a symmetry between time and space. As a consequence, the complexity theory for OTMs resembles the classical theory much more than it does for ITTMs: For an ITTM, each input is of length ω, so that e.g. the ITTM-analogue of the class P of polynomial-time computable functions is just the class of functions computable with a constant time bound. The consideration of complexity theory for OTMs was taken up by B. Löwe in [12] and then continued by B. Löwe, B. Rin and the author in [4].

An important result in classical complexity theory is that the class of languages that are decidable by a Turing machine with double-logarithmic space bound coincides with the class of regular languages, see, e.g., [16]. A crucial point in the proof of this result is the characterization of regular languages in terms of deterministic finite automata (DFAs). In this paper, we consider an analogue of this theorem for OTMs. To this end, we introduce deterministic ordinal automata (DOAs) as a transfinite analogue of deterministic finite automata (DFAs). There are several transfinite variants of DFAs preceeding ours: Büchi introduced automata ([2]) that work like DFAs and process words of ordinal length by picking a certain element from the set of states that occured cofinally often during the processing at limit times. Similar models are considered in [15] and [9]. A common feature of all these models is that the set of states is finite, while the transition relation is given by a set. Moreover, Büchi automata work on languages consisting of words of a fixed maximal ordinal length (namely, ω). In contrast, we consider automata that operate on words of any ordinal length and allow class-sized transition relations that satisfy a certain mild coherence condition. It turns out that this condition suffices to carry over much of the theory of DFAs and regular languages (Section 2). To the best of our knowledge, this notion has not been considered before. We then proceed in Section 3 to define strictly space-bounded OTM-computations as those whose working space is of a strictly smaller cardinality than the input length and show that such OTMs in fact work with a constant space bound and that the languages so recognized can be recognized with DOAs. A brief account of DOAs based on this paper was given in [3], pp. 69 and pp. 256, where some of the below results, such as examples and counterexamples of ${REG}^{\infty}$ -languages, were included as exercises. The present paper contains full results and proofs for the first time.

The paper is structured as follows: In the second section, we define deterministic ordinal automata (DOAs) (Definition 1), along with their non-deterministic analogue, the NOAs (Definition 5). We then develop the basic theory of these automata, mimicking the classical development: We show that DOAs and NOAs accept the same languages (Theorem 6) and a weak version of the Myhill–Nerode theorem (Theorem 10). Concerning the pumping lemma, we show a version of this in Theorem 12, but provide a counterexample to the most obvious transfinite analogue in Lemma 15. In Section 3, we introduce strictly space-bounded OTMs and prove our main result, Theorem 37, namely that any language that is decidable by a strictly spaced-bounded OTM is decidable by a DOA.1

¹
We emphasize that, in contrast to the classical result, this is merely an inclusion, not an equality; in fact, we will see at the end of Section 3 that the reverse inclusion is false.

1.1. Notation

In the following, Σ denotes an alphabet, i.e., a finite set. We will denote by $Σ^{* *}$ the class $Σ^{< On}$ of sequences of ordinal length over Σ. When $w \in Σ^{* *}$ , we write $| w |$ for length of w, i.e., the order-type of w. Elements of $Σ^{* *}$ will also be called Σ-words, or simply “words”, when Σ is clear from the context. When $w_{0}$ , $w_{1}$ are words, we denote by $w_{0} w_{1}$ their concatenation; moreover, if $s : = (w_{ι} : ι < α)$ is a sequence of words, we denote by $\circ s$ the concatenation of all elements of the sequence in the order of appearance in s. When w is a word and P is an OTM-program, then $P^{w}$ denotes the computation of P with (an appropriate binary encoding of) w written to the input tape. As usual, we write $P^{w} ↓ = x$ when $P^{w}$ halts with output x and $P^{w} ↑$ when the computation diverges.

2. ${REG}^{\infty}$

We consider ordinal analogues of regular languages. In particular, we introduce notions parallelizing in the ordinal realm deterministic finite automata, nondeterministic finite automata and induced congruence relation. Though our generalization of a finite automaton may seem to be far too liberal at first, it preserves enough of the heart of the classical concept to make large parts of the classical theory go through, and in fact much for the same reasons.

We begin by introducing a notion DOA generalizing deterministic finite automata.

Definition 1.
A deterministic ordinal automaton (DOA) is a quintuple $(Q, q_{0}, F, D, Σ)$ where Σ is a finite alphabet, Q is a (possibly infinite) set, $q_{0} \in Q$ , $F \subseteq Q$ and $D : Q \times Σ^{* } \to Q$ is a class function with the following property: For all $w, w_{1}, w_{2} \in Σ^{ }$ , if $D (q, w)$ is defined and $w = w_{1} w_{2}$ , then $D (q, w_{1})$ is also defined and we have $D (D (q, w_{1}), w_{2}) = D (q, w)$ .

If $A = (Q, q_{0}, F, D, Σ)$ is a DOA, then $S (A) : = {w \in Σ^{ } : D (q_{0}, w) \in F}$ is the language accepted by $A$ .

If $L \subseteq Σ^{ }$ is such that $L = S (A)$ for some DOA $A$ , then $L$ is ${REG}^{\infty}$ .

A DOA $A$ is complete if and only if $D (q, w)$ is defined for all $q \in Q$ and all $w \in Σ^{ }$ .

Note that, by this definition, the transition relation D is an arbitrary class, only restricted by the ‘coherence’ or ‘forgetfulness’ condition in the definition; intuitively, by this condition, the automaton, when in a certain state, has no memory how it got there. It turns out that this rather weak condition seems to lie combinatorially at the heart of many results about regular languages. We demonstrate this by carrying over some of the main standard results in the theory of regular languages, along with their proofs. The classical counterparts can be found in any basic textbook on theoretical computer science, such as [8].
Example 2.
(i) The language $L_{0} = {0^{α} 1^{β} : α, β \in On}$ is ${REG}^{\infty}$ for the DOA with $Q = {z_{1}, z_{2}}$ , $q_{0} = z_{1}$ , $F = {z_{2}}$ , $Σ = {0, 1}$ , $D (z_{1}, 0^{α}) = z_{1}$ for $α \in On$ , $D (z_{1}, 1^{α}) = z_{2}$ for $0 < α \in On$ and $D (z_{2}, 1^{α}) = z_{2}$ .

(ii) The language $L_{1} = {0^{α} 1^{α} : α \in On}$ is not ${REG}^{\infty}$ . To see this, suppose for a contradiction that $A = (Q, q_{0}, F, D, Σ)$ is a DOA with $L_{1} = S (A)$ and consider the words $0^{α}$ for $α < card {(Q)}^{+}$ . Since $0^{α} 1^{α} \in S_{1}$ , $D (q_{0}, 0^{α})$ must be defined for all $α \in On$ . As $card {(Q)}^{+} > card (Q)$ , there must be $α < β < card {(Q)}^{+}$ such that $D (q_{0}, 0^{α}) = D (q_{0}, 0^{β})$ . It follows that $D (q_{0}, 0^{β} 1^{β})$ is defined, so that $D (q_{0}, 0^{β} 1^{α})$ must also be defined and in fact identical to $D (q_{0}, 0^{β} 1^{β})$ . But now, on the one hand, we have $D (q_{0}, 0^{α} 1^{α}) \in F$ , while on the other hand $D (q_{0}, 0^{α} 1^{α}) = D (D (q_{0}, 0^{α}), 1^{α}) = D (D (q_{0}, 0^{β}), 1^{α}) = D (q_{0}, 0^{β} 1^{α}) \notin F$ , a contradiction.

(iii) Whenever $S \subseteq Σ^{ }$ is a set (for an arbitrary finite alphabet Σ), then S is ${REG}^{\infty}$ . To see this, let $α : = \sup {| w | : w \in S}$ , and let $Q^{'}$ be the set of Σ-sequences of length at most α and $Q = Q^{'} \cup {r}$ , where $r \notin Q^{'}$ ; moreover, for all $w \in Σ^{ }$ , define $D (r, w) = r$ and, for all $q \in Q^{'}$ , let $\begin{matrix} D (q, w) = \{\begin{matrix} q w, & if | q w | ⩽ α \\ r, & otherwise . \end{matrix} \end{matrix}$ Then $(Q, \emptyset, S, D, Σ)$ is a DOA that accepts S.
Remark 3.
Note that there is a certain asymmetry between DOAs and OTMs: While OTMs have arbitrary transfinite resources available with respect to space and time, their programs are finite; in contrast, the transition function of a DOA – which roughly corresponds to the “program” of an OTM – can be a proper class. In particular, unless $V = L$ , it is not the case that all set-sized languages are OTM-decidable, in contrast to part (iii) of the preceding example.
Proposition 4.
For every DOA* $A$ , there is a complete DOA $A^{'}$ such that $S (A) = S (A^{'})$ .
Proof.
This works as in the classical (finitary) case by letting $Q^{'} = Q \cup {q^{'}}$ and letting $D^{'} (q, w) = q^{'}$ for all $q \in Q^{'}$ and all $w \in Σ^{* }$ for which $D (q, w)$ is not defined. □

We now consider analogues of non-deterministic finite automata.
Definition 5.
An NOA is a quintuple $A = (Q, q_{0}, F, D, Σ)$ with Q, $q_{0}$ , F, Σ as for DOAs and $D \subseteq Q \times Σ^{ } \times Q$ is a relation such that we have for all $q \in Q$ and all $w, w_{1}, w_{2} \in Σ^{ }$ with $w = w_{1} w_{2}$ that $D [D (q, w_{1}), w_{2}] = D (q, w)$ . Here, for $X \subseteq Q$ and $w \in Σ^{ }$ , $D [X, w]$ denotes $⋃_{q \in X} D (q, w)$ .

If $A$ is an NOA, then $S (A) = {w \in Σ^{ } : D (q_{0}, w) \cap F \neq \emptyset}$ is the language accepted by $A$ .

We now imitate the classical power-set construction for simulating non-determinism by determinism in our setting.
Theorem 6.
The languages accepted by some NOA are exactly the languages in* ${REG}^{\infty}$ .
Proof.
Clearly, all ${REG}^{\infty}$ languages are accepted by some NOA, as every DOA is an NOA.

On the other hand, let $S = S (A)$ where $A = (Q, q_{0}, F, D, Σ)$ is an NOA. We construct a DOA $A^{'} : = (Q^{'}, q_{0}^{'}, F^{'}, D^{'}, Σ)$ as follows: Let $Q^{'} = P (Q)$ , the power set of Q, $q_{0}^{'} = {q_{0}}$ , $F^{'} = {X \subseteq Q : X \cap F \neq \emptyset}$ and define $D^{'}$ by $D^{'} (X, w) = D [X, w]$ , which is simply $⋃ {D (x, w) : x \in X})$ .

We claim that $A^{'}$ is indeed a DOA. So let $X \subseteq Q$ , $w_{1}, w_{2} \in Σ^{* }$ . We want to show that $D^{'} (X, w_{1} w_{2}) = D^{'} (D^{'} (X, w_{1}), w_{2})$ .

“⊆”: Let $q \in D^{'} (X, w_{1} w_{2})$ . Then there is $x \in X$ such that $q \in D (x, w_{1} w_{2})$ . As $A$ is an NOA, we have $D (x, w_{1} w_{2}) = D [D (x, w_{1}), w_{2}]$ , so $q \in D [D (x, w_{1}), w_{2}]$ . Let $q^{'} \in D (x, w_{1})$ be such that $q \in D (q^{'}, w_{2})$ . By definition of $D^{'}$ , we certainly have $D^{'} (X, w) \subseteq D^{'} (Y, w)$ whenever $X \subseteq Y \subseteq Q$ . As ${x} \subseteq X$ and $D^{'} ({x}, w_{1}) = D (x, w_{1})$ , we have $q^{'} \in D^{'} (X, w_{1})$ . Now, since ${q^{'}} \subseteq D^{'} (X, w_{1})$ and $D^{'} ({q^{'}}, w_{2}) = D (q^{'}, w_{2})$ , we have $q \in D^{'} (D^{'} (X, w_{1}), w_{2})$ . Since q was arbitrary, this shows that $D^{'} (X, w_{1} w_{2}) \subseteq D^{'} (D^{'} (X, w_{1}), w_{2})$ .

“⊇”: Let $q \in D^{'} [D^{'} (X, w_{1}), w_{2}]$ . Then there is $q^{'} \in D^{'} (X, w_{1})$ such that $q \in D (q^{'}, w_{2})$ . Furthermore, there is $x \in X$ such that $q^{'} \in D (x, w_{1})$ . Thus $q \in D [D (x, w_{1}), w_{2}]$ . But now we have $D (x, w_{1}) \subseteq D^{'} (X, w_{1})$ and therefore $q \in D [D (x, w_{1}), w_{2}] \subseteq D [D^{'} (X, w_{1}), w_{2}] = D^{'} (X, w_{1} w_{2})$ . As q was arbitrary, this shows that $D^{'} (D^{'} (X, w_{1}), w_{2}) \subseteq D^{'} (X, w_{1} w_{2})$ .

Hence $A^{'}$ is indeed a DOA. We finish by showing that $S (A^{'}) = S (A)$ :

“⊆”: Let $w \in S (A^{'})$ . Hence $D^{'} ({q_{0}}, w) \in F^{'}$ , i.e. $D^{'} ({q_{0}}, w) \cap F \neq \emptyset$ . Since $D^{'} ({q_{0}}, w) = D [{q_{0}}, w] = D (q_{0}, w)$ , we have $D (q_{0}, w) \cap F \neq \emptyset$ , hence $w \in S (A)$ .

“⊇”: Let $w \in S (A)$ . Hence $D (q_{0}, w) \cap F \neq \emptyset$ . Thus $F \cap D^{'} ({q_{0}}, w) = D (q_{0}, w) \cap F \neq \emptyset$ , which implies $D^{'} ({q_{0}}, w) \in F^{'}$ , i.e. $w \in S (A^{'})$ . □
Corollary 7.
${REG}^{\infty}$ is closed under complementation, union and intersection.*
Proof.
Let $L_{1}$ , $L_{2}$ be ${REG}^{\infty}$ .

For complementation, consider by Proposition 4 a complete DOA $A = (Q, q_{0}, D, F, Σ)$ for $L_{1}$ and let $A^{'} = (Q, q_{0}, D, Q ∖ F, Σ)$ ; it is easy to see that $S (A^{'}) = L_{1}$ .

For unions, let $A_{1} = (Q_{1}, q_{0, 1}, D_{1}, F_{1}, Σ)$ , $A_{2} = (Q_{2}, q_{0, 2}, D_{2}, F_{2}, Σ)$ be DOAs such that $S (A_{1}) = L_{1}$ and $S (A_{2}) = L_{2}$ . Assume without loss of generality that $Q_{1}$ and $Q_{2}$ are disjoint. Form an NOA $A = (Q, q_{0}, D, F, Σ)$ by letting $Q = ((Q_{1} \cup Q_{2}) ∖ {q_{0, 1}, q_{0, 2}}) \cup {q_{0}}$ (where $q_{0}$ is neither contained in $Q_{1}$ nor in $Q_{2}$ ), $F = F_{1} \cup F_{2}$ and defining $D (q_{0}, w) = D_{1} (q_{0, 1}, w) \cup D_{2} (q_{0, 2}, w)$ and $D (q, w) = D_{i} (q, w)$ for $q \in Q_{i}$ ( $i \in {1, 2}$ ). If $q_{0, 1} \in F_{1}$ or $q_{0, 2} \in F_{2}$ , then we also put $q_{0}$ in F. It is easy to see that $S (A) = L_{1} \cup L_{2}$ . By Theorem 6, $L_{1} \cup L_{2}$ is ${REG}^{\infty}$ .

Closure under intersection follows by de Morgan’s rules from closure under complementation and union. □
Corollary 8.
For $w \in {0, 1}^{* }$ , let* $w_{0}$ , $w_{1}$ denote the subsequences consisting of the 0s and 1s in w, respectively. Then the following two languages are not ${REG}^{\infty}$ :
$L = {w \in Σ^{* } : | w_{0} | = | w_{1} |}$

$L^{'} = {w \in Σ^{ } : card (w_{0}) = card (w_{1})}$

Proof.
Recall from Example 2 that $L^{″} : = {0^{α} 1^{β} : α, β \in On}$ is ${REG}^{\infty}$ .

(1) By Corollary 7, if $L$ was ${REG}^{\infty}$ , then so was $L \cap L^{″} = {0^{α} 1^{α} : α \in On}$ ; but we saw above in Example 2 that this is not the case.

(2) If $L^{'}$ was ${REG}^{\infty}$ , then intersecting with $L^{″}$ would yield the ∞-regularity of $L_{c} : = {0^{α} 1^{β} : card (α) = card (β)}$ . But now, essentially the same argument as the one used in Example 2(ii) shows that this is impossible. □

We turn to an analogue of Myhill–Nerode.
Definition 9.
Let $L \subseteq Σ^{ }$ . The congruence relation on $Σ^{ }$ induced by $L$ is defined as follows: For $w_{1}, w_{2} \in Σ^{ }$ , we have $w_{1} \equiv_{L} w_{2}$ if and only if, for all $w \in Σ^{ }$ , we have $w_{1} w \in L \leftrightarrow w_{2} w \in L$ .

If there are only set many $\equiv_{L}$ -equivalence classes (more formally: if there is a set X such that every $w \in Σ^{ }$ is $L$ -equivalent to some element of X), we say that $L$ satisfies the ‘ordinal Myhill–Nerode condition’ (MN for short).
Theorem 10.
$L \subseteq Σ^{ }$ is ${REG}^{\infty}$ if and only if $L$ satisfies MN.
Proof.
Suppose first that $L$ is ${REG}^{\infty}$ , and let, by Proposition 4, $A = (Q, q_{0}, F, D, Σ)$ be a complete DOA such that $L = S (A)$ . For $q \in Q$ let $Z_{A} (q) : = {w \in Σ^{ } : D (q_{0}, w) = q}$ . Then, for each $q \in Q$ , the elements of $Z_{A} (q)$ are pairwise $\equiv_{L}$ -equivalent: For $w_{1}, w_{2} \in Z_{A} (q)$ and $w \in Σ^{ }$ , we have $D (D (q_{0}, w_{1}), w) = D (q, w) = D (D (q_{0}, w_{2}), w)$ , hence either both $D (D (q_{0}, w_{1}), w)$ and $D (D (q_{0}, w_{2}), w)$ belong to $L$ or neither does, i.e. $w_{1} w \in L \leftrightarrow w_{2} w \in L$ . Since w was arbitrary, we have $w_{1} \equiv_{L} w_{2}$ .

Thus, all the $Z_{A} (q)$ are subclasses of $\equiv_{L}$ -equivalence classes and, as $A$ is complete, every $w \in Σ^{ }$ belongs to one of the $Z_{A} (q)$ . Thus every $\equiv_{L}$ -equivalence class is a union of some (at least one) $Z_{A} (q)$ , hence there are at most as many $\equiv_{L}$ -equivalence classes as there are elements in Q, i.e. only set many.

Now let $L \subseteq Σ^{ }$ be such that $\equiv_{L}$ has only set many equivalence classes on $Σ^{ }$ . Pick a representative from each equivalence class and denote by $C$ their collection; for $w \in Σ^{ }$ , denote by ${[w]}_{L}$ the element of $C$ equivalent to w. We construct a DOA $A$ with $S (A) = S$ as follows:

Let $Q = C$ , $q_{0} = {[ε]}_{L}$ (where ε denotes the empty word), $F = {{[w]}_{L} : w \in L}$ .

Note that, for all $w \in Σ^{ }$ , we either have ${[w]}_{L} \subseteq L$ or ${[w]}_{L} \cap L = \emptyset$ : For if we have $w_{1}, w_{2} \in {[w]}_{L}$ , then $w_{1} \equiv_{L} w_{2}$ , so $L ∋ w_{1} = w_{1} ε \leftrightarrow L ∋ w_{2} ε = w_{2}$ .

Now define D by setting $D ({[w_{1}]}_{L}, w_{2}) = {[w_{1} w_{2}]}_{L}$ . It is easy to check that $A = (Q, q_{0}, F, D, Σ)$ is as desired. □

We also get a rather straightforward analogue of the pumping lemma. As the proof is the same, we prove something slightly stronger, which is closer to one direction of an analogue of Jaffe’s theorem:
Definition 11.
For $w \in Σ^{ }$ and $α, β < | w |$ , let $v = w ↾ [α, β]$ be the interval of w from index α to index β, with $w (α)$ and $w (β)$ included; similarly, define $w ↾ [α, β)$ as that interval with $w (β)$ excluded.

Moreover, let $w_{(α)} = w ↾ [0, α)$ and $w^{(α)} = w ↾ [α, | w |)$ .
Theorem 12.
Let S be ${REG}^{\infty}$ , $A = (Q, q_{0}, F, D, Σ)$ a DOA with $S (A) = S$ . Let $w \in Σ^{ }$ be sufficiently long, more specifically* $| w | > card (Q)$ . Then there are $α, β < | w |$ such that, for all $i \in ω$ , $w_{(α)} {(w ↾ [α, β])}^{i} w^{(α)} \equiv_{S} w$ .
Proof.
By the pigeonhole-principle and the fact that $| w | > card (Q)$ , there are $α, β < | w |$ such that $D (q_{0}, w_{(α)}) = D (q_{0}, w_{(β)})$ . Let $v = w ↾ [α, β]$ . Then $D (q_{0}, w_{(α)}) = D (q_{0}, w_{(α)} v^{i})$ for all $i \in ω$ , so $w_{(α)} \equiv_{S} w_{(α)} v^{i}$ , so $w_{(α)} (v w^{(β)}) \equiv_{S} w_{(α)} v^{i} w^{(β)}$ . □
Remark.
The proof clearly allows us to demand that v is ‘short’, i.e. that $β - α ⩽ card {(Q)}^{+}$ .

Note that the proof does not show that we can repeat $w ↾ [α, β]$ also γ many times for $γ \in On$ : For example, a DOA with to states $s_{0}$ , $s_{1}$ may satisfy $D (s_{0}, 1^{i}) = s_{0}$ for any $i \in ω$ but also $D (s_{0}, 1^{ω}) = s_{1}$ . In fact, this stronger version is false, as we will now show.
Definition 13.
Let $L_{ω -rep}$ be the language consisting of those elements of ${0, 1}^{* }$ that have a consecutive subsequence of the form $\underset{ω times}{\underset{︸}{w w w ...}}$ , where $w \in {0, 1}^{ }$ .
Proposition 14.
$L_{ω -rep}$ is ${REG}^{\infty}$ .
Proof.
The DOA for deciding $L_{ω -rep}$ has two states $q_{0}$ and $q_{1}$ . $q_{1}$ is the only accepting state, $q_{0}$ is the starting state. The transition function sends $D (q_{0}, w)$ to $q_{1}$ if and only if $w \in L_{ω -rep}$ and to $q_{0}$ , otherwise and it sends $D (q_{1}, w)$ to $q_{1}$ for any w. By noting that, whenever $w_{1} w_{2} \in L_{ω -rep}$ , we must have $w_{1} \in L_{ω -rep}$ or $w_{2} \in L_{ω -rep}$ , it is easy to see that this is a DOA that decides $L_{ω -rep}$ . □
Lemma 15.
There is a language $L \subseteq {0, 1}^{ }$ that is* ${REG}^{\infty}$ , and for all α, there is some $w \in {0, 1}^{* }$ of length* $> α$ such that there are no $w_{0}, w_{1}, w_{2} \in {0, 1}^{* }$ with* $| w_{1} | > 0$ , $w = w_{0} w_{1} w_{2}$ and $w_{0} w_{1}^{ω} w_{2} \in L$ .
Proof.
Let $L = \overline{L_{ω -rep}}$ be the complement of $L_{ω -rep}$ . Then $L$ is ${REG}^{\infty}$ as the complement of a language that is ${REG}^{\infty}$ . We claim that $L$ contains arbitrarily long words. This suffices, as by definition no word of the form $w_{0} w_{1}^{ω} w_{2} \in L$ can belong to $L$ .

It is easy to see that, if $w : α \to 2$ is generic over L for the forcing consisting of finite functions from α to 2 ordered by inclusion, then w will be as desired, as the set of conditions c that do not extend to any function $f : α \mapsto 2$ where the ιth position starts a repetition of a word of length δ is dense for all $ι, δ < α$ . To avoid the sledgehammer of forcing and also the extra assumptions necessary to guarantee the existence of generic objects, we offer the following more direct construction:

Let us define the transfinite Morse-Thue-sequence $(s_{ι} : ι \in On)$ as follows: $s_{0} = 0$ , $s_{ι + 1} = s_{ι} \overline{s_{ι}}$ (where $\overline{s}$ denotes the word that has 0s where s has 1s and vice versa) and for a limit ordinal λ, $s_{λ}$ is defined as the union of ${s_{ι} : ι < λ}$ , i.e., by letting $s_{λ} (ι) : = s_{ι + 1} (ι)$ for all $ι < λ$ . Now, let ${MT}_{\infty} : = ⋃_{ι \in On} s_{ι}$ . We claim that there is no ι such that $s_{ι}$ has a consecutive subsequence of the form $w w w$ , which is clearly much stronger than what we require.2
²
For the elements of finite index, this is well-known, see, e.g., the entry in the Online Encyclopedia of Integer Sequences https://oeis.org/A010060.

Let us denote by ${MT}_{\infty} ↾ [ι, ξ)$ the sequence restricted to the indices ι up to ξ, (i.e., $s_{ξ} ↾ [ι, ξ)$ ) for $ι, ξ \in On$ . Clearly, for each $ι \in On$ , ${MT}_{\infty} ↾ [ω \cdot ι, ω \cdot (ι + 1))$ will either be ${MT}_{\infty} ↾ [0, ω)$ (which is just the classical Morse-Thue sequence) or its “complement” $\overline{{MT}_{\infty} ↾ [0, ω)}$ . Thus, no finite subword of the form $w w w$ can appear in ${MT}_{\infty}$ .

It is easy to see from the definition of ${MT}_{\infty}$ that, for all $α, γ \in On$ , we have ${MT}_{\infty} (ω^{γ} \cdot α) \overset{()}{=} {MT}_{\infty} (α)$ . Now suppose for a contradiction that, for some infinite word w, the substring $w w w$ appears somewhere in ${MT}_{\infty}$ . Let $α : = | w |$ be the length of w, and let us write α in Cantor normal form to the base ω as $α = ω^{γ_{0}} \cdot k_{0} + ω^{γ_{1}} \cdot k_{1} + \dots + ω^{γ_{n}} \cdot k_{n}$ with $γ_{0} > γ_{1} > \dots > γ_{n}$ and $k_{0}, \dots, k_{n} \in ω$ . Moreover, let ρ be the index at which the subword $w w w$ starts in ${MT}_{\infty}$ for the first time and write ρ in the form $ω^{γ_{0}} \cdot β + \bar{ρ}$ with $β \in On$ and $\bar{ρ} < ω^{γ_{0}}$ . By elementary properties of ordinal addition, we have that $ρ + ω^{γ_{0}} \cdot k = ω^{γ_{0}} \cdot (β + k)$ for all $k \in ω$ .

Let $w^{'}$ be the word consisting of the elements of w with index of the form $ω^{γ_{0}} \cdot i$ , $0 ⩽ i < k_{0}$ . Then $w^{'} w^{'} w^{'}$ is also the sequence of elements of ${MT}_{\infty}$ with indices of the form $ρ + ω^{γ_{0}} \cdot i$ , with $0 < i ⩽ 3 k_{0}$ . Now $ρ + ω^{γ_{0}} \cdot i = ω^{γ^{0}} \cdot (β + i)$ for these i, so by observation (∗) above, this coincides with ${MT}_{\infty} ↾ [β + 1, β + 3 k_{0} + 1)$ , which is thus a finite subsequence of consecutive elements of ${MT}_{\infty}$ of the form $w^{'} w^{'} w^{'}$ , a contradiction. □

Thus, the transfinite analogue of the pumping lemma already fails for “ω-pumping”.

We now consider ∞-regularity for unary languages, i.e. languages over an alphabet with only one element.
Proposition 16.
For each* $α \in On$ and each $X \subseteq α$ , ${1^{β} : β \in X}$ is ${REG}^{\infty}$ .
Proof.
This is immediate from Example 2, part (iii). □
Definition 17.
For $X \subseteq On$ and s a symbol, $s^{X}$ abbreviates ${s^{α} : α \in X}$ .
Lemma 18.
Neither of the following unary languages is ${REG}^{\infty}$ :
$L_{1} = {1^{κ} : κ \in Card}$

$L_{2} = {1^{ω^{α}} : α \in On}$

$L_{3} = {1^{α^{2}} : α \in On}$

Proof.
All three proofs work by contradiction. For $i \in {1, 2, 3}$ , let $A_{i}$ be a DOA with $S (A_{i}) = L_{i}$ ; the start state is always denoted $q_{0}$ , the transition by D, the set of accepting states by F etc. In the following, + always denotes ordinal addition.

(1) As $A_{1}$ only has a set of states, but there is a proper class of cardinals, by the pigeonhole principle there must be $κ < λ \in Card$ such that $D (q_{0}, κ) = D (q_{0}, λ) \in F$ . Now we have $λ + λ = λ \cdot 2 \notin Card$ and $κ + λ = λ \in Card$ . It follows that $F ∋ D (q_{0}, 1^{λ}) = D (q_{0}, 1^{κ + λ}) = D (D (q_{0}, 1^{κ}), 1^{λ}) = D (D (q_{0}, 1^{λ}), 1^{λ}) = D (q_{0}, 1^{λ \cdot 2}) \notin F$ , a contradiction.

The proofs for (2) is similar, noting that $ω^{α} + ω^{β} = ω^{β}$ is a power of ω for $α < β$ , while $ω^{α} \cdot 2$ is never a power of ω.

For (3), consider the sequence given by $α_{0} = ω$ , $α_{ι + 1} = ω^{α_{ι}}$ , $α_{λ} = ⋃_{ι < λ} α_{ι}$ for λ a limit ordinal. It is easy to see that $α_{ι}^{2} + α_{ι^{'}}^{2} = α_{ι^{'}}^{2}$ for $ι < ι^{'}$ is always a square, while $γ^{2} \cdot 2$ is never a square of an ordinal for $γ \in On$ . □
Proposition 19.
The language $L_{count} : = {\circ (0^{ι} 1 : ι < α) : α \in On}$ consisting of words of the form 1, 101, 101001, ${1010010001...10}^{γ} 10^{γ + 1} 1...1$ is not ${REG}^{\infty}$ (here, ∘ denotes concatenation of words).
Proof.
This is an easy consequence of Theorem 10: It suffices to note that no word in $L_{count}$ is $L_{count}$ -equivalent to any word of strictly smaller length, so that there is no set-sized class of representatives for the $\equiv_{L_{count}}$ -equivalence classes.3
³
We thank our anonymous referee for pointing out this considerable shortening of our original proof.

□

For the main result of this paper in the next section, we will also need an ordinal version of ε-NFAs, see, e.g., [7], chapter 2.5.2. Definition 20.
Fix a special symbol ε. From now on, we will assume that Σ never contains ε. If $w \in Σ^{* }$ , an ε-enrichment of w is defined as a sequence in ${(Σ \cup {ε})}^{ }$ in which the subsequence of elements of Σ is exactly w.

An ε-NOA with alphabet Σ is simply an NOA with the alphabet $Σ \cup {ε}$ . If $A = (Q, q_{0}, D, F, Σ)$ is an ε-NOA, then $L (A)$ is the set of $w \in Σ^{ }$ such that $w^{'} \in S (A)$ for some ε-enrichment $w^{'}$ of w.

When $p \in D (q, ε)$ , we also say that there is an ε-transition from q to p.

A language $L \subseteq Σ^{ }$ is ε- ${REG}^{\infty}$ if and only if there is an ε-NOA $A$ with $L (A) = L$ .
Lemma 21.
A language $L \subseteq Σ^{ }$ is ε-* ${REG}^{\infty}$ if and only if it is ${REG}^{\infty}$ .
Proof.
Clearly, if $L$ is ${REG}^{\infty}$ , it is also ε- ${REG}^{\infty}$ , as every DOA is also an ε-NOA (where all transitions for words containing ε are undefined).

On the other hand, let $L = L (A)$ , where $A = (Q, q_{0}, F, D, Σ)$ is an ε-NOA. Then we define an NOA $A^{'} = (Q, q_{0}, F, D^{'}, Σ)$ as follows: For $w \in Σ^{* *}$ and $q \in Q$ , $D^{'} (q, w) = ⋃ {D (q, w^{'}) : w^{'} is a ε -enrichment of w}$ . It is easy to see that this defines an NOA and that $S (A) = S (A^{'})$ . □
Remark.
We also haven’t considered ordinal versions of Mealy [13] or Moore [14] automata, but we encourage the interested reader to do so.

3. Space-bounded OTMs

We now work towards our main result. To this end, we recall the definition of the space complexity of an OTM-program. This concept was introduced by Löwe in [12].

Definition 22.
Let $f : On \to On$ be a function and P an OTM-program. P belongs to ${SPACE}^{\infty} (f)$ if and only if there is an ordinal β such that, whenever w is a word of length $α > β$ , the computation of $P^{w}$ uses only the first $β \cdot f (α)$ many cells of the scratch tape.

A classical theorem in complexity theory is that, if the space usage s of a Turing machine T is such that, for any $n \in ω$ , we have $2^{2^{s (n)}} ⩽ c \cdot n$ on any input of length n for some $c \in N$ , then T in fact has a constant bound on its space usage and hence decides a regular language. (See, e.g., [16], Corollary 2.1 for a proof of this; our proof will follow the guiding ideas of the classical proof and in particular make use of a modified version of crossing sequences.)

We work towards an infinitary version of this. In the following, let $f : On \to On$ be a (class) function such that $card (f (α)) < card (α)$ for all sufficiently large α, i.e. f ‘lowers cardinalities’. We will begin by showing that, if P belongs to ${SPACE}^{\infty} (f)$ for such an f, then P in fact belongs to ${SPACE}^{\infty} (1)$ , i.e. there is a uniform constant bound on the amount of cells P uses on the scratch tape.
Theorem 23.
Let P be an OTM-program, κ a cardinal, and let w be a 0-1-word of minimal length such that $P^{w}$ uses at least κ many scratch tape cells. Then $card (| w |) ⩽ κ$ , and in fact $card (| w |) = κ$ .
Proof.
Let $| w | = δ$ . Let $θ = \max {κ, card (δ)}$ . Form the elementary hull4
⁴
Recall that the elementary hull of a set X in an ∈-structure M is the closure of X under Skolem function; in particular then, the cardinality of the elementary hull of X has cardinality $card (X) \cdot ℵ_{0}$ .

$H$ of $κ + 1 \cup {w}$ in $H_{θ^{+ +}}$ (the set of sets hereditarily of cardinality less than $θ^{+ +}$ , where $α^{+}$ denotes the cardinal successor of α). It is easy to see and well-known folklore (see, e.g., [3], p. 267) that a halting OTM-computation on an input of length α can only have a length of cardinality at most $card (α) + ω$ (∗). Thus, the computation of $P^{w}$ will take less than $δ^{+}$ many steps and hence be contained in $H$ . Form the transitive collapse M of $H$ , and denote by $\overline{w}$ the image of w under the collapsing map. Then $κ + 1 \subseteq M$ and $M ⊧$ ‘ $P^{\overline{w}}$ uses a set of scratch tape cells or cardinality at least κ’. Furthermore, we have $| M | = ℵ_{0} \cdot κ = κ$ , so the length of $\overline{w}$ has cardinality at most κ. Since M is transitive, the computation of $P^{\overline{w}}$ in M is the same as that in V. Thus $P^{\overline{w}}$ uses already a set of scratch tape cells of cardinality κ. By minimality of δ, it follows that $card (δ) ⩽ κ$ .

By (∗), we cannot have $card (δ) < κ$ , so $card (δ) = κ$ . □
Definition 24.
Call an OTM-program P ‘strictly space-bounded’ if and only if there is a function $f : On \to On$ such that $card (f (α)) < card (α)$ for all sufficiently large α and P belongs to ${SPACE}^{\infty} (f)$ .
Corollary 25.
If P is strictly space-bounded, then P belongs to ${SPACE}^{\infty} (1)$ .
Proof.
Assume otherwise, and let P be strictly space bounded, but not in ${SPACE}^{\infty} (1)$ . Pick f as in Definition 24, and let $β \in Card$ be such that $card (f (α)) < card (α)$ for $α > β$ . Since P is not in ${SPACE}^{\infty} (1)$ , there is a word w such that $P^{w}$ uses at least $β^{+}$ many tape cells. Pick w of minimal length with this property. By Theorem 23, we have $card (| w |) = β^{+}$ . By the choice of β, we have $card (f (β^{+})) < β^{+}$ ; thus, as P belongs to ${SPACE}^{\infty} (f)$ , $P^{w}$ uses at most $card (f (β^{+})) < β^{+}$ many tape cells, which contradicts the choice of w. □

Our final goal is to show that, for each OTM-program P with a constant use of scratch tape, there is an ε-NOA accepting exactly those words for which P halts. From now on, we will refer to the head on the input tape as the “reading head”, while “read-write head” will refer to the read-write head on the scratch tape.

The proof will use an ordinal version of crossing sequences, which are the main tool used in the proof of the classical result that $REG = LOGLOGSPACE$ , see, e.g., [16] for the proof or [1], pp. 185 for an introduction to crossing sequences. The guiding idea is the following: Let P an OTM-program such that $P^{w}$ halts and has constant space usage α for every word w over some alphabet Σ; moreover, P has two possible halting states, one of which we interpret as accepting, the other as rejecting w. For the sake of simplicity, we assume in the following overview that the length of w is a limit ordinal $δ = ω β$ . Then w can be decomposed into blocks of length ω, say $w = \circ {w_{ι} : ι < β}$ with $| w_{ι} | = ω$ , which we will call the ω-blocks of w. By slight abuse of notation, when w is stored on the input tape of an OTM, we will also use the term ω-block to refer to the tape portion on which the respective part of w is stored and say, e.g., that the reading head is inside a certain ω-block. Now, with respect to the input tape t containing w, the computation $P^{w}$ works as follows: The head starts on the first cell of t; it then moves through some initial portion of the ω-blocks from left to right; unless the computation halts during this procedure, the head will eventually be reset to position 0 again (the crucial observation is that the head can only move from left to right through the ω-blocks, as the only possibility to move left in the ω-blocks is a reset). Let us call the portion of the computation between the ιth and the $(ι + 1)$ th reset the ιth “run”, where we define the start of the computation as the 0th reset. We will see below (Lemma 28) that the number ρ of runs has an upper bound that depends only on the working tape length α. We can thus imagine (see Fig. 1 below) the computation of $P^{w}$ to be organized in a $(β \times ρ)$ -table, where the $(ι, ξ)$ -th entry $s_{ι, ξ}$ consists of the operations of P while the reading head was in the ι-th ω-block in the ξ-th run (or a special “blank” symbol ∗ if the computation does not reach the ι-th ω-block in the ξ-th run or if there is no ξ-th run). Thus, $s_{ι, ξ}$ will be a sequence of machine states in the execution of P, which means that we need to specify (i) the position of the reading head relative to the start of the ι-th ω-block (which can be represented by a single natural number), (ii) the position of the read-write head on the scratch tape, i.e., an ordinal strictly smaller than α, (iii) the content of the scratch type, which is an element of $^{α} 2$ , i.e. a 0-1-sequence of length α and (iv) the inner state of the computation, which can be encoded by another natural number. As we will see below in Corollary 29, the length of each $s_{ι, ξ}$ also has an upper bound θ that only depends on α; and consequently, there are only set many possible candidates c for sequences of the form $(s_{ι, ξ} : ξ < ρ)$ .

Roughly, then, the idea is to take these candidates, i.e., sequences of length ρ of sequences s of machine states of length smaller than θ, as the states of our NOA; such a sequence is accepting if and only if the accepting state is assumed in any of the machine states contained in the one of its elements.

How do we define the transition relation? Well, suppose we are given a sequence $s : = (s_{ι, ξ} : ξ < ρ)$ and a word v.

Figure 1.
A transition between the sequences $c_{0}$ and $c_{2}$ . Red lines indicate borders between the ω-blocks of w.

Thus, we assume that s is a sequence of partial computations while the reading head was in a certain ω-block, reading a word $w_{ι}$ ; and now we want to see how the computation would continue if $w_{ι}$ was supplemented to the right by v; more precisely, we are interested in the behavior of P when the reading head enters the final ω-block of v. That, however, is easily done: For every run, i.e., every $ξ < ρ$ , we consider $s_{ν, ξ}$ . From this sequence, it is easy to determine whether the head leaves $w_{ι}$ to the right or to the left due to a reset. Let us assume that the former is the case. Then $s_{ν, ξ}$ will not have a last element (clearly, the head can only leave an ω-block to the right at a limit time), but from $s_{ν, ξ}$ , we obtain the machine state right after leaving $w_{ι}$ by the liminf-rules. Now, knowing both the machine state and the relevant part of the input word (namely, the part to the right of $w_{ι}$ ) from v, we can just simulate the computation up to the point where the head enters the last ω-block of v. The partial computation taking place while the reading head is on this last ω-block is then the ν-th component of the state $s^{'}$ to which the transition from s via v should lead us; in particular, if a reset of the reading head on the input tape takes place during this run, we expect $s^{'}$ to be ∗ (and likewise when the computation stops before reaching this ω-block).

The above description should give the reader a fairly good idea of what is going on in the following construction; there are, however, various subtleties that need to be handled, making things somewhat more technical. First, there is the difference between leaving an ω-block due to a reset and to the right, which leads to special cases in the transition relation, forcing us to distinguish between the 0-th ω-block and the others. Second, v need not be of limit length, in which case the information given by v does not suffice to determine the behavior of P in the last ω-block of v, as only a finite initial amount of the necessary bits will be available. We solve this as follows: Let $v = v_{0} v_{1}$ , where $v_{0}$ is empty or of limit length and $v_{1}$ is finite. Associated with a state will be both $v_{1}$ and a function $g : ω \to {0, 1}$ , which will serve as a “guess” for the complete ω-block of w started by $v_{1}$ ; clearly, we require that $v_{1}$ is an initial segment of g and moreover that the associated partial P-computations are compatible with g being the relevant part of the oracle. Now, if a state s is given by a sequence c of partial computations, a finite 0-1-function f and an extension $g : ω \to {0, 1}$ of f, and we want to determine the transition from s via a word u, we first determine whether $(f u) ↾ [0, ω)$ is an initial segment of g; if not, we go to a special non-acceptance state, all of whose transitions lead back to itself. Otherwise, if u is finite, we leave s and g unchanged, but replace f with $f u$ ; but if $u = u_{0} u_{1}$ with $u_{0}$ of limit length and $u_{1}$ finite, the states that we can reach from s via u are given by those $s^{'}$ , $v^{'}$ and $g^{'} \in^{ω} 2$ for which (i) $s^{'}$ is a sequence of partial computations in the oracle $g^{'}$ (with the reading head never leaving $g^{'}$ ), (ii) $v^{'}$ is equal to $u_{1}$ and an initial segment of $g^{'}$ and (iii) when continuing the partial computations in s by using $f u$ as the input, we arrive at the initial configurations in the corresponding partial computations in $s^{'}$ when the no reset takes place before the reading head reaches the final ω-block of $f u$ , and if a reset takes place, then $s^{'}$ has an ∗ in the respective place.

This concludes our overview; we will now carry out the above plan in formal detail.
Definition 26.
Let P be an OTM-program with scratch tape use bounded above by γ, and let $w = (w_{ι} : ι < α) \in {0, 1}^{* }$ be a word. For $ι < | w |$ , the interval $w ↾ [ω ι, ω ι + ω)$ is called the ι-th ω-block of w. (Recall the abuse of notation introduced above.)

The 0-th run of $P^{w}$ is the partial computation of $P^{w}$ between the start of the computation and the first time that the reading head is moved to the left from a limit position, resulting in a reset to position 0. The ι-th run is then the partial computation between the ι-th and the $(ι + 1)$ -th such reset.

A P-snippet is a quintupel $(s_{ι}, t_{ι}, ρ, i, f)$ , where $s_{ι}$ is an inner state of P, $t_{ι} : γ \to {0, 1}$ is a candidate for a scratch tape content of P, $ρ < γ$ is a candidate for the position of the read-write head on the scratch tape, $i \in ω$ is a candidate for the relative position of the reading head in the current ω-block on the input tape (i.e., if that position is ν, then i is the unique element of ω such that $ν = ω ξ + i$ for some ordinal ξ) and $f : i \to {0, 1}$ is a candidate for the first i bits of the input word in that ω-block.

A P-guess is a sequence of P-snippets.

Let $β < α$ , and let δ be an ordinal. The interval $w ↾ [β, β + ω)$ is called the βth ω-block of w. The block-crossing sequence $bcs (P, w, β)$ of length δ for $P^{w}$ associated with β is the sequence $(g_{ξ} : ξ < δ)$ such that, if $P^{w}$ has a ξ-th run, then $g_{ξ}$ is the P-guess that describes the operations of P while the reading head is in the β-th ω-block during the ξ-th run; if the reading head does not enter the β-th ω-block during the ξ-th run or if there is no ξ-th run, then $g_{ξ} = $ . Intuitively, a block-crossing sequence consists of those parts of the computation of $P^{w}$ that occur while the reading head is in a certain ω-block.

A δ-state is a quadruple $t = (i, s, f, g)$ , where $i \in {0, 1}$ , s is a δ-sequence of P-guesses, f is a map from a finite ordinal to ${0, 1}$ and $g : ω \to {0, 1}$ is such that f is an initial segment of g and each P-guess $\overline{s}$ in s is a partial P-computation in the oracle g in which the reading head does not leave the portion on which g is written. When $i = 0$ , we call t an initial state, otherwise, t is a transitional state.5
⁵
The idea here is that initial states are guesses for block-crossing sequences associated with the first ω-block of the input word, while transitional states are guesses for block-crossing sequences associated with the other ω-blocks of the input word.

We will eventually construct the desired NOA whose states will be the δ-states, i.e., the possible candidates for the block-crossing sequences, amended with some extra information. We begin by showing that the possible block-crossing sequences for a halting OTM-program P with constant space usage form a set. (Note that this is not trivial, since the possible inputs are a proper class.) Fix a program P that has constant scratch tape use bounded by γ, and assume without loss of generality (by increasing γ if necessary) that $γ ⩾ ω$ . Then g each P-snippet is an element of $ω \times^{γ} 2 \times γ \times ω \times^{< ω} 2$ . Thus, there is only a set T of quintuples that can possibly occur in a P-guess. It remains to control the length of a P-guess, and the required number of P-guesses in a state, i.e., the number of runs of $P^{w}$ . These are our next goals.

We start by recalling the following looping criterion for infinitary machines, which can e.g. be found in [6] for the case of ITTMs:
Proposition 27.
Let P be an OTM-program. Suppose that, in the computation of P, a configuration c is repeated such that, for all times between the two occurences of c, every other configuration had all components (tape contents) at least as large as the corresponding component in c. Then P never halts.
Proof (Sketch).
After arriving at c for the second time, the same steps will be repeated, so c will occur a third, fourth etc. time. The only way to escape the loop would be at a limit time. However, the condition above ensures that the configuration at any limit time which is preceeded by cofinally many occurences of c will be c as well. □
Lemma 28.
Let $w \in {0, 1}^{* }$ be such that* $| w | = α$ . In the course of a halting computation $P^{w}$ with scratch tape use bounded by γ, the reading head on the scratch tape will be positioned on the 0-th cell less than ${(2^{card (γ)})}^{+}$ many times.
Proof.
First, note that the sequence $(c_{ι} : ι < δ)$ of machine configurations (i.e. the inner states and the scratch tape contents) occuring at times when the reading head is positioned at $w_{0}$ is continuous in the sense that $(q_{λ}, s_{λ}) = {liminf}_{ι < λ} (s_{ι}, t_{ι})$ for limit ordinals $λ < δ$ . This is due to the behaviour of OTMs at limit stages and in particular the fact that the reading head position at limit times is the inferior limit of the sequence of earlier reading head positions, i.e. at a limit of times at which the reading head was on $w_{0}$ , the reading head will again be at position 0.

Now assume otherwise and consider the sequence of the first ${(2^{card (γ)})}^{+}$ many such configurations. Let $ι^{}$ be the index in the computation of $P^{w}$ at which the reading head is on the 0-th cell for the ${(2^{card (γ)})}^{+}$ th time.

If every configuration occured only boundedly often before this time, then for each such configuration, the set of suprema of the indices of their occurences would be majorized by some $c_{ι}$ , and the set of these ι would be a cofinal subset of ${(2^{card (γ)})}^{+}$ of cardinality $2^{card (γ)}$ , contradicting the regularity of the successor cardinal ${(2^{card (γ)})}^{+}$ .

The same argument shows that there is some $α < ι^{}$ such that all configurations occuring after time α in the computation occur cofinally often before $ι^{}$ . Again by the regularity of ${(2^{card (γ)})}^{+}$ , there is $λ < ι^{}$ which is simultaneously for each of these configuration a limit of the indices at which these configurations occur and a time at which the reading head is on the 0-th cell. As $λ > α$ , $c_{λ}$ will occur cofinally often below $ι^{}$ . Also, by the liminf-rule, $c_{λ}$ will in each component be less than or equal to every other configuration occuring cofinally often before $ι^{}$ . But this implies by Proposition 27 that the computation is strongly looping after the first two such occurences of $c_{λ}$ , which contradicts the assumption that $P^{w}$ halts. □
Corollary 29.
In the course of the computation of a halting computation $P^{w}$ with scratch tape use bounded by γ, there will be at most $2^{card (γ)}$ many disjoint time intervals at which the reading head is in the β-th ω-block.
Proof.
Note that, by the rules for moving the reading head, an ω-block other than the 0-th ω-block can only be reached “from the left”, while the 0th block can only be entered when the reading head is moved to the left from some limit position. Therefore, whenever the reading head is in the 0-th ω-block, it must have been on $w_{0}$ before without leaving the 0-th ω-block in the meantime. Thus, the 0-th ω-block can only be visited less than ${(2^{card γ})}^{+} ⩽ 2^{card (γ)}$ many times by Lemma 28.

As any other ω-block can only be entered from the left, the reading head must have been in the 0-th ω-block before entering such an ω-block anew, thus the same holds for all other ω-blocks. □

It remains to control how long the reading head can remain in an ω-block.
Lemma 30.
In the course of a halting computation $P^{w}$ with scratch tape use bounded by γ, a time interval in which the reading head remains in the same ω-block can have no more than $2^{card (γ)}$ many elements.
Proof.
Suppose for a contradiction that the reading head remains in some ω-block for ${(2^{card (γ)})}^{+}$ many steps. Shifting the time interval if necessary, we assume that this starts at computation time 0. If every of the possible ω many reading head positions in this episode occured only boundedly often, then, by regularity of ${(2^{card (γ)})}^{+}$ , there would be a common upper bound for the suprema of the times at which any head position occured, a contradiction. Thus, there is $α < {(2^{card (γ)})}^{+}$ such that every reading head position occuring after time α occurs cofinally often before time ${(2^{card (γ)})}^{+}$ . Let k be the minimal element of the set of these positions. Then the same argument as for Lemma 28 shows that the reading head can be on position k at most $2^{card (γ)}$ many times during the interval. But this leads to a cofinal subset of ${(2^{card (γ)})}^{+}$ with cardinality at most $2^{card (γ)}$ , a contradiction. □

We now have the desired bound on the length of P-guesses that can actually occur as partial computations of P while the reading head is in a certain ω-block, as well as the number of visits to an ω-block:
Definition 31.
Let P be an OTM-program whose scratch tape use is bounded by γ on every input. A relevant P-guess is a P-guess of length less than $2^{card (γ)}$ . A relevant P-guess sequence is a sequence of relevant P-guesses of length less than $2^{card (γ)}$ .
Corollary 32.

There are at most $2^{2^{card (γ)}}$ many relevant P-guesses.

There are at most $2^{2^{card (γ)}}$ many relevant sequences of P-guesses.

There are at most $2^{2^{card (γ)}}$ many $2^{card (γ)}$ -states for P.

Proof.
(i) Since the set of P-snippet is a subset of $ω \times^{γ} 2 \times γ \times ω \times^{< ω}$ by definition, there are at most $2^{card (γ)}$ many P-snippets. Consequently, by Lemma 30, there are at most ${(2^{card (γ)})}^{2^{card (γ)}} = 2^{card (γ) 2^{card (γ)}} = 2^{2^{card (γ)}}$ relevant P-guesses.

(ii) Given (i), the number of relevant P-guess sequences is bounded above by ${(2^{2^{card (γ)}})}^{2^{card (γ)}} = 2^{2^{card (γ)} \cdot 2^{card (γ)}} = 2^{2^{card (γ)}}$

(iii) We have $γ ⩽ ω$ , so that the number of $2^{card (γ)}$ -states is bounded by $2^{2^{card (γ)}} \cdot 2^{ω} = 2^{2^{card (γ)}}$ . □

We will now construct an ε-NOA that accepts exactly those words $w \in {0, 1}^{* }$ for which $P^{w}$ halts in the accepting halting state. As announced above, in the definition of the states of this NOA, the $2^{card (γ)}$ -states, i.e., the possible candidates for block crossing sequences, amended by a candidate for an oracle portion of length at most ω, will play an important role.

We assume that the input word w has a mark rh to its right and that P notices (e.g., via special states) when rh is reached. Also, we assume without loss of generality that $P^{w}$ never moves the reading head to any position to the right of rh and only halts with the reading head on the cell containing rh; clearly, this can be arranged by changing P to move its head to the right up to rh once w has been accepted or rejected. Formally, this means that both our OTMs and our automata work over the three-element alphabet ${0, 1, rh}$ rather than merely over ${0, 1}$ ; but in order not to clutter the already somewhat technical proof with additional subtleties, we will ignore this point in the following.6
⁶
If one wanted to be strict here, one could, e.g., replace 0 by 01, 1 by 10 and then take 11 to represent rh, thus reducing everything to rh again; it is not hard to see that this has no influence on OTM-decidability with constant space bound or ordinal regularity.

We need to note, however, that adding rh at the end of each word does not influence the property of being ${REG}^{\infty}$ :
Lemma 33.
Let* Σ be an alphabet, $σ \notin Σ$ , $L \subseteq Σ^{* }$ , and let* $L_{σ} : = {w σ : w \in L}$ . Then $L$ is ${REG}^{\infty}$ if and only if $L_{σ}$ is ${REG}^{\infty}$ .
Proof.
Let $L$ be ${REG}^{\infty}$ , and let $A = (Q, q_{0}, F, D, Σ)$ be a DOA that accepts $L$ . Pick $q \notin Q$ and define $A_{σ}$ to be $(Q \cup {q}, q_{0}, {q}, D^{'}, Σ \cup {q})$ , where $D^{'} = D \cup {((s, w σ), q) : s \in Q \land D (s, w) \in F}$ . Then $A_{σ}$ is a DOA that accepts $L_{σ}$ .

Conversely, suppose that $L_{σ}$ is ${REG}^{\infty}$ and let $A_{σ} = (Q, q_{0}, F, D_{σ}, Σ \cup {σ})$ be a DOA that accepts $L_{σ}$ . Then we obtain an ε-NOA $A = (Q, q_{0}, F, D, Σ)$ accepting $L$ by replacing all σ-transitions in $A_{σ}$ by ε-transitions, i.e., by setting $D (s, w) = {D_{σ} (s, w), D_{σ} (s, w σ)}$ . □
Definition 34.
Let P be an OTM-program such that $P^{w}$ halts in one of two halting states $h_{accept}$ , $h_{reject}$ for every input w and has constant space usage bounded above by $γ ⩾ ω$ . The ε-NOA associated with P, denoted by $N (P)$ , is then defined as follows:

Let $\hat{I}$ be the set of initial $2^{card (γ)}$ -states for P, let T be the set of transitional $2^{card (γ)}$ -states for P, and let $q_{0}, r \notin I \cup T \times I$ . An initial $2^{card (γ)}$ -state $(0, s, f, g)$ is called proper if and only if the first element of s is the initial configuration of P in which P is in its starting state, both heads are on position 0 and the scratch tape is empty; let I be the set of proper initial $2^{card (γ)}$ -states. Then the set of states of $N (P)$ is given by $Q (P) : = {q_{0}, r} \cup I \cup T \times I$ . A state $s \in Q (P)$ is accepting if and only if $s \in I$ and the sequence of P-guesses in s contains a P-snippet in which the inner machine state is $h_{accept}$ or $s \in T \times I$ , $s = (s_{0}, s_{1})$ , and $s_{0}$ satisfies this condition. The initial state of $N (P)$ is $q_{0}$ . r is taken as a special rejection state.

Now we define the transition relation $D_{N (P)}$ . For any $s \in I$ , we will define a separate transition relation $D_{s}$ on the subset $Q_{s} : = {s} \cup T \times {s}$ . We have $D (r, w) = {w}$ for all words w. There will be no transitions between $T \times {s}$ and $T \times {t}$ unless $s = t$ . The transition relation $D_{N (P)}$ will then be given by taking the union $D_{U} : = ⋃_{s \in I} D_{s}$ and adding $D_{N (P)} (q_{0}, w) = ⋃_{s \in I} D_{s} (s, w)$ for $w \neq \emptyset$ and the ε-transitions $D_{N (P)} (q_{0}, ε) = I$ .

Now, for any $z \in I$ , any $s \in Q_{z}$ and any word $w \neq \emptyset$ , $D_{s}$ is defined as follows:
If $s = z = (0, \overline{z}, f, g)$ and w is finite, then $D_{z} (s, w) = {((1, \overline{z}, f w, g), s)}$ if $f w$ is an initial segment of g, and $D_{z} (s, w) = {r}$ , otherwise.

If $s = z = (0, \overline{z}, f, g)$ and $w = w_{0} w_{1}$ with $| w_{0} |$ limit and $| w_{1} | < ω$ and $\overline{z} = (z_{ι} : ι < 2^{card (γ)})$ :

If g is not an initial segment of w, then $D_{z} (s, w) = {r}$ .

Otherwise, for each $ι < 2^{card (γ)}$ such that $z_{ι} \neq $ , we run the computation $P^{f w}$ starting in the initial configuration of the first element of $z_{ι}$ until either the reading head enters the last ω-block of $f w$ or is reset due to moving left from a limit position.

If a reset takes place and the machine configuration after the reset is different from the first element of $z_{ι + 1}$ , then $D_{z} (s, w) = {r}$ . (This means that the guess of the initial state is incompatible with the input.)

Otherwise, $D_{z} (s, w)$ will be a pair $((1, {\overline{z}}^{'}, w_{1}, g^{'}), s)$ with $w_{1}$ an initial segment of $g^{'}$ and $z^{'}$ is a sequence of partial computations of P in the input $g^{'}$ such that the reading head does not visit any cells besides those containing $g^{'}$ in the course of its computation; it remains to determine ${\overline{z}}^{'} (ι)$ for all $ι < 2^{card (γ)}$ :

If $z_{ι} = $ , then ${\overline{z}}^{'} (ι) = $ .

If a reset takes place and the machine configuration after the reset is equal to the first element of $z_{ι + 1}$ , then ${\overline{z}}^{'} (ι) = $ .

If no reset takes place, then ${\overline{z}}^{'} (ι)$ is the partial $P^{g^{'}}$ -computation c that starts in the first configuration in which the reading head enters the last ω-block of $P^{f w}$ when starting in the first configuration of $z_{ι}$ and is maximal in the sense that continuing c would move the reading head out of this ω-block.

If $s = ((1, \overline{z}, f, g), t)$ and w is finite, then $D_{z} (s, w) = ((1, \overline{z}, f w, g), s)$ if $f w$ is an initial segment of g, and $D_{z} (s, w) = r$ , otherwise.

If $s = ((1, \overline{z}, f, g), t)$ and $w = w_{0} w_{1}$ with $| w_{0} |$ limit and $| w_{1} | < ω$ and $\overline{z} = (z_{ι} : ι < 2^{card (γ)})$ , $t = (0, \overline{t}, f_{0}, g_{0})$ and $\overline{t} = (t_{ι} : ι < 2^{card (γ)})$ :

If g is not an initial segment of w, then $D_{z} (s, w) = {r}$ .

Otherwise, for each $ι < 2^{card (γ)}$ such that $z_{ι} \neq $ , we again run the computation $P^{f w}$ starting in the initial configuration of the first element of $z_{ι}$ until either the reading head enters the last ω-block of $f w$ or is reset due to moving left from a limit position.

If a reset takes place and the machine configuration after the reset is different from the first element of $t_{ι + 1}$ , then $D_{z} (s, w) = {r}$ . (This again means that the guess of the initial state is incompatible with the input; note that, in order to determine this, it is necessary to store the initial configuration in the states.)

Otherwise, $D_{z} (s, w)$ is defined exactly as in (c)–(e) above.

Lemma 35.
Let P be an OTM-program P such that, for some* $γ \in On$ and all $w \in {0, 1}^{* }$ , $P^{w}$ halts and uses less than γ many scratch tape cells. Then* $N (P)$ is an ε-NOA.
Proof.
Let $N (P) = (Q, q_{0}, F, D, {0, 1})$ . All parts of the definition of an NOA except the coherence condition for D follow straightforwardly from the definition of $N (P)$ . So let $q \in Q$ , and let $w_{1}, w_{2} \in {0, 1}^{* }$ . We need to show that $D (q, w_{1} w_{2}) = D [D (q, w_{1}), w_{2}]$ . Let I denote the set of initial states and T the set of transitional states of $N (P)$ . We distinguish the following cases:

First, we shall assume that $q \neq q_{0}$ .

Case 1: At least one of $w_{1}$ , $w_{2}$ is finite. Let $q = (0, s^{'}, f^{'}, g^{'})$ when q is initial or $q = ((1, s^{'}, f^{'}, g^{'}), t)$ when q is transitional. For the sake of simplicity, we assume that q is transitional; the case that q is initial works analogous.

If $w_{1}$ is finite and $w_{2} = w_{2}^{0} w_{2}^{1}$ with $| w_{2}^{0} |$ either 0 or a limit ordinal and $| w_{2}^{1} |$ finite, then $D (q, w_{1}) = {((1, s^{'}, f^{'} w_{1}, g^{'}), t)}$ when $f^{'} w_{1}$ is an initial segment of $g^{'}$ and $D (q, w_{1}) = {r}$ , otherwise. In the first case, it is clear that the D-successors of $((1, s^{'}, f^{'} w_{1}, g^{'}), t)$ under $w_{2}$ will coincide with the D-successors of $((1, s^{'}, f^{'}, g^{'}), t)$ under $w_{1} w_{2}$ . In the second case, all further transitions will just lead back to ${r}$ ; moreover, $f^{'} w_{1} w_{2}$ will be incompatible with $g^{'}$ , so we will have $D (q, w_{1} w_{2}) = {r}$ , as desired.

If $w_{2}$ is finite and $w_{1} = w_{1}^{0} w_{1}^{1}$ with $| w_{1}^{0} |$ limit and $| w_{1}^{1} | < ω$ , then $D (q, w_{1})$ is a set of states of the form $((1, s^{″}, w_{1}^{1}, g^{″}), t)$ , where $g^{″} : ω \to {0, 1}$ . From these, one obtains the elements of $D (q, w_{1} w_{2})$ by taking the subset of those states satisfying that $w_{1}^{1} w_{2}$ is an initial segment of $g^{″}$ and replacing $w_{1}^{1}$ with $w_{1}^{1} w_{2}$ ; exactly the same will yield the elements of $D [D (q, w_{1}), w_{2}]$ .

From now on, we assume that both $w_{1}$ and $w_{2}$ are infinite.

Case 2: q is an initial state; let $q = (0, s, f, g)$ . We show that $D_{q} (q, w_{1} w_{2}) = D_{q} [D_{q} (q, w_{1}), w_{2}]$ . This suffices, since, by definition, $D_{q} (q, w_{1})$ will only consist of transitional states of the form $(\hat{q}, s)$ (and possible r). The r-state is easily dealt with, so let us consider only the transitional states $(\hat{q}, q)$ . On these elements, $D_{q}$ and D coincide, so that we will have $D (q, w_{1} w_{2}) = D_{q} [D_{q} (q, w_{1}), w_{2}]$ . Let $w_{1} = w_{1}^{0} w_{1}^{1}$ with $| w_{1}^{0} |$ limit and $| w_{1}^{1} | < ω$ and similarly $w_{2} = w_{2}^{0} w_{2}^{1}$ with $| w_{2}^{0} |$ limit and $| w_{2}^{1} | < ω$ .

⊆: Let $q^{'} \in D_{q} (q, w_{1} w_{2})$ , $q^{'} = ((1, s^{'}, f^{'}, g^{'}), q)$ ; this means that $s^{'}$ is a sequence of elements that are either ∗ or partial P-computations in the oracle $g^{'}$ starting in the configurations in which the reading head enters the last ω-block of $w_{1} w_{2}$ when starting $P^{w_{1} w_{2}}$ in the respective configurations in s. Let $s^{″}$ be the sequence of configurations occuring after the reading head had first read $w_{1}$ in such a computation, and let $g^{″}$ denote the ω-block of $w_{1} w_{2}$ in which the first element of $w_{2}$ occurs. Then $((1, s^{″}, w_{1}^{1}, g^{″}), q) \in D_{q} (q, w_{1})$ , and moreover, we have $q^{'} \in D_{q} (((1, s^{″}, w_{1}^{1}, g^{″}), q))$ . Hence $q^{'} \in D_{q} [D_{q} (q, w_{1}), w_{2}]$ .

⊇: Now let $q^{'} \in D_{q} [D_{q} (q, w_{1}), w_{2}]$ , and let $g^{″}$ denote the first ω-block of $w_{1}^{1} w_{2}$ . Now, $D (q, w_{1})$ will contain some element $q^{″}$ of the form $((1, s^{″}, w_{1}^{1}, g^{″}), q)$ , and for this element we will have $q^{'} \in D_{q} (q^{″}, w_{2})$ by the definition of $D_{q}$ , as $q^{″}$ correctly guesses how the computations of $P^{w_{1} w_{2}}$ will proceed with the reading head on the ω-block of $w_{1} w_{2}$ containing the first element of $w_{2}$ . But then, $s^{″}$ also correctly describes the actions of the computation $P^{w_{1} w_{2}}$ at these time intervals, and so $q^{'}$ is a candidate for how this computation might proceed after having read $w_{1} w_{2}$ , i.e., an element of $D_{q} [D_{q} (q, w_{1}), w_{2}]$ , as desired.

Case 3: q is a transitional state; let $q = ((1, s, f, g), t)$ .

This works similar to Case 2, with the extra observation that each reset of the reading head that takes place while $w_{1} w_{2}$ is processed either takes place while $w_{1}$ is processed or while $w_{2}$ is processed after $w_{1}$ has been processed, so that the extra clauses of Definition 34 taking care of resets are satisfied.

Finally, we consider $q = q_{0}$ .

Case 4: $q = q_{0}$ . In this case, by the Cases (1) and (2), we have $D (q, w_{1} w_{2}) = ⋃_{s \in I} D_{s} (s, w_{1} w_{2}) = D_{s} [D_{s} (s, w_{1}), w_{2}]$ .

Now, let $q^{'} \in Q$ . Then, by definition, we have $q^{'} \in D (q, w_{1} w_{2})$ if and only if there are $s \in I$ and $q^{″} \in D_{s} (s, w_{1})$ such that $q^{'} \in D_{s} (q^{″}, w_{2})$ . By definition of D, we have $D_{s} (s, w_{1}) = D (q, w_{1})$ ; it follows that $q^{″} \in D (q, w_{1})$ , so that the last claim is equivalent to $q^{'} \in D_{s} [D (q, w_{1}], w_{2}] = D [D (q, w_{1}], w_{2}]$ . Hence $D (q, w_{1} w_{2}) = D [D (q, w_{1}), w_{2}]$ . □
Lemma 36.
Let P be an OTM-program such that, for some* $γ \in On$ and all $w \in {0, 1}$ , $P^{w}$ halts in one of two halting states $h_{accept}$ and $h_{reject}$ and uses less than γ many scratch tape cells. Then $N (P)$ accepts exactly those words for which $P^{w}$ halts in the state $h_{accept}$ .
Proof.
Let $N (P) = (Q, q_{0}, F, D, {0, 1})$ .

Suppose first that $P^{w}$ terminates in the accepting state (with the reading head on rh, by definition). Let s be the state of $N (P)$ that correctly describes the actions of $P^{w}$ with the reading head in the ω-block containing rh. Then $s \in F$ and moreover, we have $s \in D (q_{0}, w)$ ; thus, $N (P)$ accepts w.

Conversely, suppose that $N (P)$ accepts w, so that $D (q_{0}, w)$ contains an accepting state s. Assume without loss of generality that s is a transitional state, the case that s is initial being similar; so $s = (\hat{q}, t)$ . Write $w rh = (w_{ι} : ι < δ + 1)$ , where all $w_{ι}$ with the possible exception of $w_{δ}$ have length ω. For each $ξ < δ + 1$ , $D (q_{0}, \circ (w_{ι} : ι ⩽ ξ))$ contains a unique element of the form $((1, s_{ξ}, \emptyset, w_{ξ}), t)$ . But now, by definition, the sequence $(s_{ξ} : ξ < δ + 1)$ describes a halting computation of $P^{w_{1} w_{2}}$ that terminates in the accepting state; thus, w is accepted by P. □

We now obtain our main result:
Theorem 37.
Let P be an OTM-program such that $P^{w}$ halts and the scratch space usage of the computation of $P^{w}$ is bounded by a constant γ for every $w \in {0, 1}^{* }$ . Then there is an ε-NOA* $A_{P}$ such that $S (A_{P}) = {w \in {0, 1}^{* } : P^{w} ↓} = : S (P)$ .
Proof.
A direct consequence of Lemma 36. □
Corollary 38.
Every language* $L \subseteq {0, 1}^{* }$ that is decidable by a strictly space-bounded OTM is* ${REG}^{\infty}$ .
Proof.
Combine Theorem 37 and Lemma 21. □

Putting Corollary 38 and our negative results on ${REG}^{\infty}$ together, we obtain:
Corollary 39.
None of the following languages is semi-decidable by a strictly space-bounded OTM:
$S_{1} : = {0^{α} 1^{α} : α \in On}$

$S_{2} : = {1^{ω^{α}} : α \in On}$

$S_{3} : = {1^{α^{2}} : α \in On}$

$S_{4} : = {\circ (0^{ι} 1 : ι < α) : α \in On}$

$S_{5} : = {w \in {0, 1}^{* } : | w_{0} | = | w_{1} |}$

This shows in particular that strictly-space bounded OTMs are strictly weaker than e.g. linearly space-bounded OTMs, as there is obviously an OTM-program in ${SPACE}^{\infty} (id)$ that decides ${0^{α} 1^{α} : α \in On}$ by simply writing the 0s to the scratch tape, then going back to the start of the scratch tape and replacing 0s by 1s.

We cannot expect to turn Corollary 38 into a strict equivalence, as Proposition 16 shows that any subset of ${0, 1}^{ *}$ is ${REG}^{\infty}$ , while not every such set will in general be OTM-computable.
4. Conclusion and further work

We have defined a transfinite version of regularity that generalizes the classical version in a rather straightforward manner. As it turns out, the theory is in large parts parallel to the classical theory, even though the relevant realm is considerably extended. As a by-product, our generalization allows us to see more clearly which structural features of regular languages play a role in proving their basic properties. A somewhat weak spot is the lack so far of a satisfying analogue of the pumping lemma that allows for “transfinite pumping”. Whether such an analogue exists and what the exact formulation should be is currently an open question.

Another question is whether there is any way to get an equivalence result from Corollary 38. One approach might be to strengthen the notion of an OTM: In his Master’s thesis [11], E. Lewis7

⁷

Not to be confused with A. Lewis, one of the authors of [6].

introduced OTMs with infinite programs, in which programs are (possibly infinite) sets of Turing commands and the states are indexed with ordinals; computations are then defined exactly as for OTMs with finite programs. One of the results of [11] is that these ‘Lewis machines’ are equivalent to OTMs with a (set-sized) oracle. The definitions of space complexity, strictly space-boundedness etc. clearly apply to Lewis-machines. Another approach might be to consider more restrictive versions of regularity, where the DOA is required to be OTM-computable within certain complexity restrictions. Whether these approaches will lead to a non-trivial result will be taken up in future work.

Given the fact that regular languages play an important role in computer science since there are many natural examples of regular languages, it will be interesting to see whether there are examples of ${REG}^{\infty}$ -classes corresponding to natural classes in mathematics. If so, ${REG}^{\infty}$ could serve as a complexity measure for such objects.

It is then natural to ask for transfinite generalizations of further stages of the Chomsky hierarchy, which we plan to take up in future work.

Footnotes

Acknowledgements

We thank our two anonymous referees for detailed and extensive comments that greatly helped to improve the presentation of the paper.

References

Bovet and

Crescenzi, Introduction to the Theory of Complexity, Vol. 46, 1994. ISBN 978-0-13-915380-8. doi:10.2307/2584070.

Büchi, Decision methods in the theory of ordinals, Bulletin of The American Mathematical Society 71 (1965). ISBN 978-1-4613-8930-9. doi:10.1090/S0002-9904-1965-11384-2.

Carl, Ordinal Computability: An Introduction to Infinitary Machines, 2019. ISBN 9783110496154.

Carl,

Löwe and

Rin, Koepke machines and satisfiability for infinitary propositional languages, 2017, pp. 187–197. ISBN 978-3-319-58740-0. doi:10.1007/978-3-319-58741-7_19.

Dawson, Ordinal time Turing computation, PhD thesis, University of Bristol, 2009.

Hamkins and

Lewis, Infinite time Turing machines, Journal of Symbolic Logic 65 (1998).

Hopcroft,

Motwani and

Ullman, Introduction to Automata Theory, Languages, and Computation, 2006.

Hromkovic, Theoretische Informatik, 2014. ISBN 978-3-658-06432-7. doi:10.1007/978-3-658-06433-4.

Huschenbett,

Kartzow and

Schlicht, Pumping for ordinal-automatic structures, Computability 6 (2017), 125–164. doi:10.3233/COM-160057.

10.

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

11.

Lewis, Computing with infinite programs, Master’s thesis, Universiteit van Amsterdam, 2018.

12.

Löwe, Space bounds for infinitary computation, 2006, pp. 319–329. ISBN 978-3-540-35466-6. doi:10.1007/11780342_34.

13.

Mealy, A method for synthesizing sequential circuits, Bell System Technical Journal 34 (1955), 1045–1079. doi:10.1002/j.1538-7305.1955.tb03788.x.

14.

Moore, Gedanken-experiments on sequential machines, 1956, pp. 129–153. ISBN 9781400882618. doi:10.1515/9781400882618-006.

15.

Schlicht and

Stephan, Automata on ordinals and automaticity of linear orders, Annals of Pure and Applied Logic 164 (2013), 523–527. doi:10.1016/j.apal.2012.11.007.

16.

Stearns,

Hartmanis and

Lewis, Hierarchies of memory limited computations, 1965, pp. 179–190. doi:10.1109/FOCS.1965.11.