Randomness and degree theory for infinite time register machines¹

Article type: Research Article

Authors: Carl, Merlin

Affiliations: Fachbereich für Mathematik und Statistik, Universität Konstanz, D-78457 Konstanz, Deutschland. [email protected]. http://www.math.uni-konstanz.de/~carl/

Note: [1] This is an expanded and amended version of [2].

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

DOI: 10.3233/COM-160055

Journal: Computability, vol. 5, no. 2, pp. 181-196, 2016