Search

In this paper, we study the power and limitations of computing effectively generic sequences using effectively random oracles. Previously, it was known that every 2-random sequence computes a 1-generic sequence (as shown by Kautz) and every 2-random sequence forms a minimal pair in the Turing degrees with every 2-generic sequence (as shown by Nies, Stephan, and Terwijn). We strengthen these results by showing that every Demuth random sequence computes a 1-generic sequence and that every Demuth random sequence forms a minimal pair with every pb-generic sequence (where pb-genericity is an effective notion of genericity that is strictly between 1-genericity and 2-genericity). Moreover, we prove that for every comeager${\cal G} \subseteq {2^\omega }$, there is some weakly 2-random sequenceXthat computes some$Y \in {\cal G}$, a result that allows us to provide a fairly complete classification as to how various notions of effective randomness interact in the Turing degrees with various notions of effective genericity.

We show that for each computable ordinal $\alpha > 0$ it is possible to find in each Martin-Löf random ${\rm{\Delta }}_2^0 $ degree a sequence R of Cantor-Bendixson rank α, while ensuring that the sequences that inductively witness R’s rank are all Martin-Löf random with respect to a single countably supported and computable measure. This is a strengthening for random degrees of a recent result of Downey, Wu, and Yang, and can be understood as a randomized version of it.

Consider a universal oracle Turing machine that prints a finite or an infinite binary sequence, based on the answers to the binary queries that it makes during the computation. We study the probability that this output is infinite and computable when the machine is given a random (in the probabilistic sense) stream of bits as the answers to its queries during an infinitary computation. Surprisingly, we find that these probabilities are the entire class of real numbers in (0,1) that can be written as the difference of two halting probabilities relative to the halting problem. In particular, there are universal Turing machines that produce a computable infinite output with probability exactly 1/2. Our results contrast a large array of facts (the most well-known being the randomness of Chaitin’s halting probability) that witness maximal initial segment complexity of probabilities associated with universal machines. Our proof uses recent advances in algorithmic randomness.

We study the possible growth rates of the Kolmogorov complexity of initial segments of sequences that are random with respect to some computable measure on 2 ω , the so-called proper sequences. Our main results are as follows: (1) We show that the initial segment complexity of a proper sequence X is bounded from below by a computable function (that is, X is complex) if and only if X is random with respect to some computable, continuous measure. (2) We prove that a uniform version of the previous result fails to hold: there is a family of complex sequences that are random with respect to a single computable measure such that for every computable, continuous measure μ , some sequence in this family fails to be random with respect to μ . (3) We show that there are proper sequences with extremely slow-growing initial segment complexity, that is, there is a proper sequence the initial segment complexity of which is infinitely often below every computable function, and even a proper sequence the initial segment complexity of which is dominated by all computable functions. (4) We prove various facts about the Turing degrees of such sequences and show that they are useful in the study of certain classes of pathological measures on 2 ω , namely diminutive measures and trivial measures.