An important theorem in classical complexity theory is that , 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 ; the other direction, however, is easily seen to fail.
D.Bovet and P.Crescenzi, Introduction to the Theory of Complexity, Vol. 46, 1994. ISBN 978-0-13-915380-8. doi:10.2307/2584070.
2.
J.Büchi, Decision methods in the theory of ordinals, Bulletin of The American Mathematical Society71 (1965). ISBN 978-1-4613-8930-9. doi:10.1090/S0002-9904-1965-11384-2.
3.
M.Carl, Ordinal Computability: An Introduction to Infinitary Machines, 2019. ISBN 9783110496154.
4.
M.Carl, B.Löwe and B.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.
5.
B.Dawson, Ordinal time Turing computation, PhD thesis, University of Bristol, 2009.
6.
J.Hamkins and A.Lewis, Infinite time Turing machines, Journal of Symbolic Logic65 (1998).
7.
J.Hopcroft, R.Motwani and J.Ullman, Introduction to Automata Theory, Languages, and Computation, 2006.
8.
J.Hromkovic, Theoretische Informatik, 2014. ISBN 978-3-658-06432-7. doi:10.1007/978-3-658-06433-4.
9.
M.Huschenbett, A.Kartzow and P.Schlicht, Pumping for ordinal-automatic structures, Computability6 (2017), 125–164. doi:10.3233/COM-160057.
10.
P.Koepke, Turing computations on ordinals, Bulletin of Symbolic Logic11 (2005). doi:10.2178/bsl/1122038993.
11.
E.Lewis, Computing with infinite programs, Master’s thesis, Universiteit van Amsterdam, 2018.
12.
B.Löwe, Space bounds for infinitary computation, 2006, pp. 319–329. ISBN 978-3-540-35466-6. doi:10.1007/11780342_34.
13.
G.Mealy, A method for synthesizing sequential circuits, Bell System Technical Journal34 (1955), 1045–1079. doi:10.1002/j.1538-7305.1955.tb03788.x.
14.
E.Moore, Gedanken-experiments on sequential machines, 1956, pp. 129–153. ISBN 9781400882618. doi:10.1515/9781400882618-006.
15.
P.Schlicht and F.Stephan, Automata on ordinals and automaticity of linear orders, Annals of Pure and Applied Logic164 (2013), 523–527. doi:10.1016/j.apal.2012.11.007.
16.
R.Stearns, J.Hartmanis and P.Lewis, Hierarchies of memory limited computations, 1965, pp. 179–190. doi:10.1109/FOCS.1965.11.
