Space-Bounded OTMs and REG$^{\infty}$

An important theorem in classical complexity theory is that LOGLOGSPACE=REG, 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), 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.


Introduction
Ordinal Turing machines (OTMs), introduced by P. Koepke in [Ko] and independently by B. Dawson in [Da], 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. One attractive feature of OTMs when compared with Infinite Time Turing Machines (ITTMs), introduced in 2000 by J. Hamkins and A. Lewis ([HaLe]), 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 [L] and then continued by B. Löwe, B. Rin and the author in [CLR].
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. [H]). 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 ( [Bu]) 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 [StSc] and [HKS]. A common feature of all these models is that the transition relation is given by a set. In contrast, we allow class-sized transition relation 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.
In the following, Σ denotes an alphabet (i.e. a finite set), Σ * * denotes Σ <On , i.e. the set of sequences of ordinal length over Σ.

REG ∞
We consider ordinal analogues of regular languages. In particular, we introduce notions parallelizing in the ordinal realm deterministic finite automata, nondeterministic finite automata, induced congruence relation and prove analogues of classical theorems like simulation of determinism by nondeterminism and Myhill-Nerode. 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 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 Q is a set q 0 ∈ Q, F ⊆ Q and D : Q × Σ * * → Q is a class function with the following property: For all w, w 1 , w 2 ∈ Σ * * , 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 0 , w 1 ), w 2 ) = D(q, w).
A DOA A is complete if and only if D(q, w) is defined for all q ∈ Q and all w ∈ Σ * * .
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 [Hro].
We now consider analogues of non-deterministic finite automata. Definition 4. An NOA is a quintuple A = (Q, q 0 , F, D, Σ) and D ⊆ Q × Σ * * × Q is a relation such that we have for all q ∈ Q and all w, w 1 , w 2 ∈ Σ * * with w = w 1 w 2 that D[D(q, w 1 ), w 2 ] = D(q, w). Here, for X ⊆ Q and w ∈ Σ * * , D[X, w] denotes q∈X D(q, w).
If A is an NOA, then S(A) = {w ∈ Σ * * : D(q 0 , w) ∩ F = ∅} is the language accepted by A.
We now imitate the classical power-set construction for simulating nondeterminism by determinism in our setting.
Theorem 5. The languages accepted by some NOA are exactly the languages in REG ∞ .
Proof. Clearly, all REG ∞ languages are accepted by some NOA, as every DOA is an NOA.
Hence A ′ is indeed a DOA. We finish by showing that S(A ′ ) = S(A): We turn to an analogue of Myhill-Nerode.
Definition 6. Let L ⊆ Σ * * . The congruence relation on Σ * * induced by L is defined as follows: For w 1 , w 2 ∈ Σ * * , we have w 1 ≡ L w 2 if and only if, for all w ∈ Σ * * , we have w 1 w ∈ L ↔ w 2 w ∈ L.
If the class of ≡ L -equivalence classes is a set (more formally: if there is a set X such that every w ∈ Σ * * is L-equivalent to some element of X), we say that L satisfies the 'ordinal Myhill-Nerode condition' (MH for short).
Proof. Suppose first that L is REG ∞ , and let, by Thus, all the Z A (q) are subclasses of ≡ L -equivalence classes and, as A is complete, every w ∈ Σ * * belongs to one of the Z A (q). Thus every ≡ Lequivalence class is a union of some (at least one) Z A (q), hence there are at most as many ≡ L -equivalence classes as there are elements in Q, i.e. only set-sized many. Now let L ⊆ Σ * * be such that ≡ L has only set-sized many equivalence classes on Σ * * . Pick a representative from each equivalence class and denote by C their collection; for w ∈ Σ * * , denote by [w] L the element of C equivalent to w. We construct a DOA A with S(A) = S as follows: Let Note that, for all w ∈ Σ * * , we either have It is easy to check that A = (Q, q 0 , F, D, Σ) is as desired.
Corollary 8. REG ∞ is closed under complementation, union and intersection.
For complementation, consider a complete DOA A = (Q, q 0 , D, F, Σ) for Closure under intersection follows by de Morgan's rules from closure under complementation and union.
Corollary 9. For w ∈ {0, 1} * * , let w 0 , w 1 denote the subsequences consisting of the 0s and 1s in w, respectively. Furthermore, let |w| 0 and |w| 1 denote the cardinality of the set of places in w taken by 0 or 1. Then the following two languages are not REG ∞ : ( It is easy to see that the language L ′′ := {0 α 1 β : α, β ∈ On} is REG ∞ : The corresponding DOA has two states s 0 and s 1 , both of which are accepting and of which s 0 is the starting state. The transition relation is given by (1) By Corollary 8, if L was REG ∞ , then so was L∩L ′′ = {0 α 1 α : α ∈ On}; but we saw above that this is not the case. ( 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: Let w ∈ Σ * * be sufficiently long, more specifically |w| > card(Q). Then there are α, β < |w| such that, for all Proof. By the pigeonhole-principle and the fact that 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 γ ∈ On: For example, a DOA with to states s 0 , s 1 may satisfy D(s 0 , 1 i ) = s 0 for any i ∈ ω but also D(s 0 , 1 ω ) = s 1 . We do not know whether this stronger version holds, but we conjecture that it does not. We consider ∞-regularity for unary languages, i.e. languages over an alphabet with only one element.
Proof. The appropriate DOA has one state for each initial segment of an element of S and connects them in the obvious manner.
Definition 13. For X ⊆ On and s a symbol, s X abbreviates {s α : α ∈ X}.
Lemma 14. Neither of the following unary languages is REG ∞ : (1) Proof. All three proofs work by contradiction. For i ∈ {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.
For the main result of this paper in the next section, we will also need an ordinal version of λ-NFAs: Definition 16. Fix a special symbol λ. From now on, we will assume that Σ never contains λ. If w ∈ Σ * * , a λ-enrichment of w is defined as a sequence in (Σ ∪ {λ}) * * in which the subsequence of elements of Σ is exactly w.
A λ-NOA with alphabet Σ is simply an NOA with the alphabet Σ ∪ {λ}.
Proof. Clearly, if L is REG ∞ , it is also λ-REG ∞ , as every DOA is also a λ-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 a λ-NOA. Then we define an NOA A ′ = (Q, q 0 , F, D ′ , Σ) as follows: For w ∈ Σ * * and q ∈ 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 L(A) = L(A ′ ).

Remark:
We also haven't considered ordinal versions of Mealy or Moore automata, but we encourage the interested reader to do so.

Space-Bounded OTMs
We now work towards our main result. To this end, we define the space complexity of an OTM-program. This concept was introduced by Löwe in [L].
Definition 18. Let f : On → On be a function and P an OTM-program. P belongs to SPACE ∞ (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 β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 2 2 s(n) ≤ c · n for some c ∈ N, then T in fact has a constant bound on its space usage and hence decides a regular language.
(See e.g. [H] for a proof of this.) We work towards an infinitary version of this. In the following, let f : On → 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 ∞ (f ) for such an f , then P in fact belongs to SPACE ∞ (1), i.e. there is a uniform constant bound on the amount of cells P uses on the scratch tape.
Theorem 19. Let P be an OTM-program, κ a cardinal, and let w be a 0-1word of minimal length such that P w uses κ many scratch tape cells. Then card(|w|) ≤ κ.
Proof. Let |w| = δ. Moreover, let σ denote the order type of the set of scratch tape cells used in the computation of P w (thus card(σ) = κ). Form the elementary hull H of σ + 1 ∪ {w} in H δ ++ (the set of sets heriditarily of cardinality ≤ δ ++ , where α + denotes the cardinal successor of α). Note that H will in particular contain the computation of P w . Form the transitive collapse M of H, and denote byw the image of w under the collapsing map. Then σ + 1 ⊆ M and M |='Pw uses a set of scratch tape cells or order type σ'. Furthermore, we have |M| = ℵ 0 κ = κ, so the length ofw has cardinality at most κ. Since M is transitive, the computation of Pw in M is the same as that in V . Thus Pw uses already a set of scratch tape cells of order type σ and hence of cardinality κ.
Remark: It is easy to see and well-known that a halting OTM-computation on an input of length α can only have a length of cardinality ≤ card(α). Thus, we can in fact replace card(|w|) ≤ κ with card(|w|) = κ in the theorem statement.
Definition 20. Call an OTM-program P 'strictly space-bounded' if and only if there is a function f : On → On such that card(f (α)) < card(α) for all sufficiently large α and P belongs to SPACE ∞ (f ).
Corollary 21. If P is strictly space-bounded, then P belongs to SPACE ∞ (1).
Proof. Assume otherwise. This means that, for each κ ∈ Card, there is a word w such that P w uses at least κ many scratch tape cells. By Theorem 19, |w| ≤ κ. But, by the definition of f , if κ is sufficiently large, then card(f (κ)) < κ, so since P belongs to SPACE ∞ (f ), P w uses less than κ many scratch tape cells, a contradiction.
Our final goal is to show that, for each OTM-program P with a constant use of scratch tape, there is a λ-NOA accepting exactly those words for which P halts. The proof will use an ordinal version of crossing sequences.
Definition 22. Let P be an OTM-program, and let w = (w ι : ι < α) ∈ {0, 1} * * . Consider the computation of P w and let β < α be an ordinal.The interval [β, β + ω) is called the β-block of w. The block-crossing sequence bcs(β) associated with β is the sequence of quintuples (s, t, ρ, i, f ), called P -snippets, where in the ιth tuple (s ι , t ι , i ι ), s ι is the inner state of P when the reading head is in the β-block of w for the ιth time in the course of the computation, and likewise t ι is the content of the scratch tape, ρ is the position of the read/write-head on the scratch tape, i ∈ ω is the relative position of the reading head in the block at this time and f is the content of the first i many bits of the ω-block in which the reading head is currently located.
For the sake of simplicity, we will from now on regard ρ and s as 'absorbed' into t (e.g. via a special mark on the tape) and work with triples (s, i, f ) instead of quintuples as P -snippets.
We will eventually construct the desired NOA whose states will be the possible candidates for the block-crossing sequences. We begin by showing that the possible block-crossing sequences for such a program P as above form a set. (Note that this is not trivial, since the possible inputs are a proper class.) If P has constant scratch tape use bounded by γ, then the second components of the triples (s, i, f ) will belong to the set γ 2; the first component is an element of a finite set and the last component is an element of ω. Thus, there is a set T of triples that can possibly occur in a block crossing sequence. It remains to control the length of such a sequence. This is our next goal.
We start by recalling the following looping criterion for infinitary machines, which can e.g. be found in [?] for the case of ITTMs: Proposition 23. Let P be an OTM-program. Suppose 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 24. Let w = (w ι : ι < α) ∈ {0, 1} * * . In the course of a halting computation P w with scratch tape use bounded by γ, the reading head will be positioned on w 0 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 w 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 at w 0 for the (2 card(γ) ) + th time.
If every configuration occurs 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(γ) ) + .
Thus, 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 at w 0 . 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 that the computation is strongly looping after the first two such occurences of c λ , which contradicts the assumption that P w halts.
Corollary 25. Let β < α. In the course of the computation of P w , 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, a block other than the 0th 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 0th block, it must have been on w 0 before without leaving the 0th block in the meantime. Thus, the 0th block can only be visited < 2 card γ ) + , i.e. ≤ 2 card(γ) many times by Lemma 24.
As any other block can only be entered from the left, the reading head must have been in the 0th block before entering such a block anew, thus the same holds for all other blocks.
It remains to control how long the reading head can remain in a block.
Lemma 26. 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, (2 card(γ) ) + would have cofinality ω, 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 24 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 ≤ 2 card(γ) , a contradiction.
Corollary 27. For each block, the reading head position is inside this block at most 2 card(γ) many times during the computation of P w .
Proof. By Corollary 25, the reading head enters each block at most 2 card(γ) many times and by Lemma 26 remains there for at most 2 card(γ) many steps, thus the reading head is inside the block at most 2 card(γ) 2 card(γ) = 2 card(γ) many times.
Corollary 28. There are at most 2 2 card(γ) many possible block crossing sequences.
We will now construct an NOA that accepts exactly those words w ∈ {0, 1} * * for which P w halts. As announced above, the states of this NOA will be the possible block crossing sequences.
We assume that the input word w has a mark lh on its left side and another mark rh to its right and that P notices (via special states) when rh reached. Furthermore, we assume that P starts with the reading head on lh and never goes back there in the course of the computation.
We change the definition of a block-crossing sequence slightly: We don't need the whole sequence of machine configurations while the reading head is on the block, it suffices to have the sequence of machine configurations for the time points when the reading head enters the block anew (i.e. after having been in another block in the meantime). (Clearly, as such sequences are obtained from the others by deleting some elements, they are not longer and hence the estimates above remain valid.) Theorem 29. Let P be an OTM-program such that the scratch space usage of the computation of P w for every w ∈ {0, 1} * * is bounded by a constant γ. Then there is a λ-NOA A P such that S(A P ) = {w ∈ {0, 1} * * : P w ↓} =: S(P ).
Proof. Assume without loss of generality that, if P w halts, then it halts with the reading head on rh. This can easily be arranged by changing P slightly to P ′ which works like P , but when P assumes a halting state, moves the reading head to the right until it reaches rh and stops then.
We pick a starting state q 0 . Now let S P be the set of all P -snippets in which the scratch tape is empty, the inner state of P is the initial state and the reading and read/write heads are on position 0. Furthermore, let Seq P be the set of all sequences of P -snippets of length ≤ 2 card(γ) whose first elements belongs to S P . The λ-NOA we are about to build will have disjoint deterministic components A z , one for each z ∈ Seq P . The idea is that z is a guess for the sequence of snippets when P has the reading head at the start of the input tape. Thus the first step of A is a λ-transition to some element of Seq P . Hence, for each z ∈ Seq P , we introduce a state q z to the states of A and add λ-transitions D(q 0 , λ) = {q z : z ∈ Seq P } to the class of transitions of A.
We now define the components A z separately. Let z ∈ Seq P be given. The states of A z are all sequences of P -snippets of length ≤ 2 card(γ) . We proceed to define the transition relation D z of A z .
First, let q = (s, i, f ) be a P -snippet, w ∈ {0, 1} * * . Then d z (q, w), the local w-successor of q, is determined as follows: Add w to the right of f . Then simulate P from this situation on, with the input given by f w. If the reading head is set back to 0 before every bit of w has been read, we let d z (q, w) = ∅. Otherwise, we consider the P -snippet c describing the situation in which the reading head arrives at a cell to the right of w for the first time and let d z (q, w) = c.
Next, we define D z (s, w), for s ∈ Seq P . Let s = (s ι : ι ≤ 2 card(γ) ). Then D z (s, w) = (d z (s ι , w) : ι ≤ 2 card(γ) ), if it holds for all s ι with d z (s ι , w) = ∅ that the (ι + 1)th entry of z is the P -snippet after the reading head is set back to 0; otherwise, we leave D z (s, w) undefined. This condition enforces that the P -snippets 'match' the initial situation z.
The set F z of accepting states of A z is the set of sequences that have a final entry t in which the inner state is an accepting state of P . This defines A z , and thus A.
Let A P = (Q, q 0 , F, D, {0, 1}). We show that A P is indeed a λ-NOA. But this is easy to see, as the indeterminism in fact only happens in the first step of the form D(q 0 , λ), while for q = q 0 , D(q, w) has only one element.
Finally, we show that S(A P ) = S(P ). First, if P w halts, then D(q 0 , w) contains the sequences describing the actual behaviour of P w on w (ω) , the sequence of the first ω many bits of w. Now, ifw denotes the rest of w, then D(s,w) will be the crossing sequence describing the actual behaviour of P w on rh, which, by the assumption that P w halts, has as its last element a triple whose first component is a halting state and all of whose other entries must have an rh-state as their first component.
On the other hand, if w ∈ S(A P ), this means that D(q 0 , w) contains an element of F , which by definition of D means that there is a computation of P w that halts.
Putting Corollary 30 and our negative results on REG ∞ together, we obtain: Corollary 31. None of the following languages is semi-decidable by a strictly space-bounded OTM: