The Complexity of Recursive Splittings of Random Sets

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 ≡_TZ ∩ R for every infinite recursive set R.

2. For each set X there is a Martin-Löof random set Z ≥_TX such that for all recursive sets R, either X ≤_TZ ∩ R or X ≤_TZ ∩ $<![CDATA[$\overline{R}$]]$ .