Randomness and degree theory for infinite time register machines 1

Abstract

A concept of randomness for infinite time register machines (ITRMs) is defined and studied. In particular, we show that for this notion of randomness, computability from mutually random reals implies computability and that an analogue of van Lambalgen’s theorem holds. This is then applied to obtain results on the structure of ITRM-degrees. Finally, we consider autoreducibility for ITRMs and show that randomness implies non-autoreducibility.

Keywords

Infinite time register machines ordinal computability algorithmic randomness degree theory forcing

Get full access to this article

View all access options for this article.

References

Carl, The distribution of ITRM-recognizable reals, in: Turing Centenary Conference: How the World Computes,

S.B.

Cooper,

Dawar,

Hyland and

Löwe, eds, Annals of Pure and Applied Logic, Vol. 165, 2014, pp. 1353–1532.

Carl, Algorithmic randomness for infinite time register machines, in: Language, Life and Limits. 10th Conference on Computability in Europe,

Beckmann,

Csuhaj-Varju and

Meer, eds, Lecture Notes in Computer Science, Vol. 8493, 2014, pp. 84–92.

Carl, Optimal results on ITRM-recognizability, Journal of Symbolic Logic 80(4) (2015), 1116–1130.

Carl,

Fischbach,

Koepke,

Miller,

Nasfi and

Weckbecker, The basic theory of infinite time register machines, Archive for Mathematical Logic 49(4) (2010), 249–273.

Carl and

Schlicht, Infinite computations with random oracles, Notre Dame Journal of Formal Logic (2016), to appear, available at: arXiv:1307.0160.

N.J.

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

R.G.

Downey and

Hirschfeldt, Algorithmic Randomness and Complexity. Theory and Applications of Computability, Springer, Berlin, 2010.

Hamkins and

Lewis, Infinite time Turing machines, Journal of Symbolic Logic 65(2) (2000), 567–604.

Hjorth and

Nies, Randomness via effective descriptive set theory, Journal of the London Mathematical Society (2) 75 (2007), 495–508.

10.

Jensen and

Karp, Primitive recursive set functions. Axiomatic set theory, in: Proceedings of Symposia in Pure Mathematics, Vol. XIII, Part I, American Mathematical Society, Providence, RI, 1971, pp. 143–176.

11.

Kanamori, The Higher Infinite. Large Cardinals in Set Theory from Their Beginnings, Springer Monographs in Mathematics, Springer, 2005.

12.

Koepke, Turing computations on ordinals, Bulletin of Symbolic Logic 11 (2005), 377–397.

13.

Koepke, Ordinal computability, in: Mathematical Theory and Computational Practice,

Ambos-Spies et al., eds, Lecture Notes in Computer Science, Vol. 5635, 2009, pp. 280–289.

14.

Koepke and

Miller, An enhanced theory of infinite time register machines, in: Logic and Theory of Algorithms,

Beckmann et al., eds, Lecture Notes in Computer Science, Vol. 5028, 2008, pp. 306–315.

15.

A.R.D.

Mathias, Provident sets and rudimentary set forcing, Fundamenta Mathematicae (2016), to appear, available at: https://www.dpmms.cam.ac.uk/~ardm/fifofields3.pdf.

16.

Y.N.

Moschovakis, Descriptive Set Theory. Studies in Logic and the Foundations of Mathematics, Vol. 100, North-Holland Publishing Company, New York, 1980.

17.

Sacks, Higher Recursion Theory, Perspectives in Mathematical Logic, Vol. 2, Springer, Berlin, 1990.

18.

Simpson, An extension of the recursively enumerable Turing degrees, Journal of the London Mathematical Society. Second Series 75 (2007), 287–297.

19.

Simpson and

Weitkamp, High and low Kleene degrees of coanalytic sets, Journal of Symbolic Logic 48(2) (1983), 356–368.

20.

R.I.

Soare, Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets, Perspectives in Mathematical Logic, Springer, Heidelberg, 1987.