×

The distribution of ITRM-recognizable reals. (English) Zbl 1321.03055

This paper explores the distribution of ITRM-recognizable reals in the hierarchy of the constructible reals. Infinite time register machines (ITRM) are a model for infinite computation introduced by P. Koepke and R. Miller [Lect. Notes Comput. Sci. 5028, 306–315 (2008; Zbl 1142.03347)]. They differ from other register machines in allowing arbitrary ordinals as running times. A real \(x\) is ITRM-recognizable if there is an ITRM program \(P\) such that \(P\) halts with output 1 if the input equals \(x\), and halts with output 0 otherwise. The ITRM-recognizable reals properly contain the ITRM-computable reals and are a proper subset of the constructible reals. The author proves that the ITRM-recognizable reals have gaps relative to the canonical well-ordering on Gödel’s constructible sets.

MSC:

03D65 Higher-type and set recursion theory
03D60 Computability and recursion theory on ordinals, admissible sets, etc.
03E45 Inner models, including constructibility, ordinal definability, and core models

Citations:

Zbl 1142.03347
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[2] Boolos, G., On the semantics of the constructible levels, Z. Math. Log. Grundl. Math., 16, 139-148 (1970) · Zbl 0164.31502
[3] Carl, M., Alternative finestructural and computational approaches to constructibility (2010), University of Bonn: University of Bonn Bonn, PhD thesis · Zbl 1280.03002
[4] Carl, M.; Fischbach, T.; Koepke, P.; Miller, R.; Nasfi, M.; Weckbecker, G., The basic theory of infinite time register machines, Arch. Math. Logic, 49, 2, 249-273 (2010) · Zbl 1184.03044
[5] Cutland, N. J., Computability: An Introduction to Recursive Function Theory (1980), Cambridge University Press · Zbl 0448.03029
[6] Gitman, V.; Hamkins, J. D.; Johnstone, Th. A., What is the theory ZFC without power set? · Zbl 1375.03059
[7] Hamkins, J.; Lewis, A., Infinite time Turing machines, J. Symbolic Logic, 65, 2, 567-604 (2000) · Zbl 0963.03064
[8] Jech, T., Set Theory (2002), Springer
[9] Jensen, R. B., The fine structure of the constructible hierarchy, Ann. Math. Logic (1972) · Zbl 0257.02035
[10] Jensen, R.; Karp, C., Primitive recursive set functions, (Proceedings of the UCLA Set Theory Institute (1967))
[11] Koepke, P., Infinite time register machines, (Beckmann, A.; etal., Logical Approaches to Computational Barriers. Logical Approaches to Computational Barriers, Lecture Notes in Comput. Sci., vol. 3988 (2006), Springer: Springer Heidelberg), 257-266 · Zbl 1143.03357
[12] Koepke, P.; Miller, R., An enhanced theory of infinite time register machines, (Beckmann, A.; etal., Logic and Theory of Algorithms. Logic and Theory of Algorithms, Lecture Notes in Comput. Sci., vol. 5028 (2008)), 306-315 · Zbl 1142.03347
[13] Koepke, P., Ordinal computability, (Ambos-Spies, K.; etal., Mathematical Theory and Computational Practice. Mathematical Theory and Computational Practice, Lecture Notes in Comput. Sci., vol. 5635 (2009)), 280-289 · Zbl 1268.03060
[14] Koepke, P.; Welch, P., A generalized dynamical system, infinite time register machines, and \(\Pi_1^1 - C A_0\), (Löwe, B.; etal., CiE 2011. CiE 2011, Lecture Notes in Comput. Sci., vol. 6735 (2011)), 152-159 · Zbl 1345.03111
[15] Miller, A. W., Descriptive set theory and forcing: how to prove theorems about the Borel sets the hard way, Available online · Zbl 0835.03012
[16] Moschovakis, Y. N., Descriptive Set Theory (1980), North-Holland Publishing Company · Zbl 0433.03025
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.