The Complexity of Recursive Splittings of Random Sets

Article type: Research Article

Authors: Ng, Keng Meng | Nies, André | Stephan, Frank

Affiliations: School of Physical & Mathematical Sciences Nanyang Technological University 21 Nanyang Link Singapore kmng@ntu.edu.sg | Department of Computer Science University of Auckland Private Bag 92019 Auckland New Zealand andre@cs.auckland.ac.nz | Department of Mathematics and Department of Computer Science National University of Singapore Lower Kent Ridge Road Singapore fstephan@comp.nus.edu.sg

Abstract: It is investigated how much information of a random set can be preserved if one splits the random set into two halves or, more generally, cuts out an infinite portion with an infinite recursive set. The two main results are the following ones: 1. Every high Turing degree contains a Schnorr random set Z such that Z ≡T Z ∩ R for every infinite recursive set R. 2. For each set X there is a Martin-Löof random set Z ≥T X such that for all recursive sets R, either X ≤T Z ∩ R or X ≤T Z ∩ <![CDATA[$\overline{R}$]].

Keywords: Computability, Algorithmic randomness, Splitting

DOI: 10.3233/COM-14023

Journal: Computability, vol. 3, no. 1, pp. 1-8, 2014