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.
M.Carl, The distribution of ITRM-recognizable reals, in: Turing Centenary Conference: How the World Computes, S.B.Cooper, A.Dawar, M.Hyland and B.Löwe, eds, Annals of Pure and Applied Logic, Vol. 165, 2014, pp. 1353–1532.
2.
M.Carl, Algorithmic randomness for infinite time register machines, in: Language, Life and Limits. 10th Conference on Computability in Europe, A.Beckmann, E.Csuhaj-Varju and K.Meer, eds, Lecture Notes in Computer Science, Vol. 8493, 2014, pp. 84–92.
3.
M.Carl, Optimal results on ITRM-recognizability, Journal of Symbolic Logic80(4) (2015), 1116–1130.
4.
M.Carl, T.Fischbach, P.Koepke, R.Miller, M.Nasfi and G.Weckbecker, The basic theory of infinite time register machines, Archive for Mathematical Logic49(4) (2010), 249–273.
5.
M.Carl and P.Schlicht, Infinite computations with random oracles, Notre Dame Journal of Formal Logic (2016), to appear, available at: arXiv:1307.0160.
6.
N.J.Cutland, Computability – An Introduction to Recursive Function Theory, Cambridge Univ. Press, Cambridge, 1980.
7.
R.G.Downey and D.Hirschfeldt, Algorithmic Randomness and Complexity. Theory and Applications of Computability, Springer, Berlin, 2010.
8.
J.Hamkins and A.Lewis, Infinite time Turing machines, Journal of Symbolic Logic65(2) (2000), 567–604.
9.
G.Hjorth and A.Nies, Randomness via effective descriptive set theory, Journal of the London Mathematical Society (2)75 (2007), 495–508.
10.
R.Jensen and C.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.
A.Kanamori, The Higher Infinite. Large Cardinals in Set Theory from Their Beginnings, Springer Monographs in Mathematics, Springer, 2005.
12.
P.Koepke, Turing computations on ordinals, Bulletin of Symbolic Logic11 (2005), 377–397.
13.
P.Koepke, Ordinal computability, in: Mathematical Theory and Computational Practice, K.Ambos-Spieset al., eds, Lecture Notes in Computer Science, Vol. 5635, 2009, pp. 280–289.
14.
P.Koepke and R.Miller, An enhanced theory of infinite time register machines, in: Logic and Theory of Algorithms, A.Beckmannet 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.
S.Simpson, An extension of the recursively enumerable Turing degrees, Journal of the London Mathematical Society. Second Series75 (2007), 287–297.
19.
S.Simpson and G.Weitkamp, High and low Kleene degrees of coanalytic sets, Journal of Symbolic Logic48(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.
