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

Abstract

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

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

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

Keywords

Ordinal computability Infinite Time Register Machines Gandy ordinals

Get full access to this article

View all access options for this article.

References

Abramson and

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

Boolos and

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

Buchholz,

Feferman and

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

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

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

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

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

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

Carl, Space-bounded OTMs and

{REG}^{\infty}

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

10.

Carl,

Fischbach,

K.P.R.

Miller,

Nasfi and

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

11.

Carl and

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

12.

Carl,

Galeotti and

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

13.

Carl,

Ouazzani and

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

14.

Carl and

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

15.

Carl,

Schlicht and

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

16.

Carl,

Schlicht and

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

17.

Carl,

Schlicht and

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

18.

Coskey and

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

19.

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

20.

Deolalikar,

Hamkins and

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

21.

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

22.

Fischbach and

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

23.

Galeotti and

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

24.

Gitman,

Johnstone and

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

25.

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

26.

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

27.

Hamkins and

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

28.

Hamkins and

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

29.

Hamkins,

Miller,

Seabold and

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

30.

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

Stern, ed., 1982.

31.

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

32.

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

33.

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

34.

Koepke and

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

35.

Koepke and

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

36.

Koepke and

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

37.

Koepke and

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

38.

Koepke and

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

39.

Madore, A Zoo of Ordinals, 2017.

40.

Monin and

P.A.

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

41.

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

42.

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

43.

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

44.

P.K.R.

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

45.

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

46.

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