EveryK-trivial set is computable from an incomplete Martin-Löf random set, i.e., a Martin-Löf random set that does not compute the halting problem.

We consider effective versions of two classical theorems, the Lebesgue density theorem and the Denjoy–Young–Saks theorem. For the first, we show that a Martin-Löf random real z ∈ [0, 1] is Turing incomplete if and only if every effectively closed class.

We investigate the role of continuous reductions and continuous relativization in the context of higher randomness. We define a higher analogue of Turing reducibility and show that it interacts well with higher randomness, for example with respect to van Lambalgen’s theorem and the Miller–Yu/Levin theorem. We study lowness for continuous relativization of randomness, and show the equivalence of the higher analogues of the different characterizations of lowness for Martin-Löf randomness. We also characterize computing higher [Formula: see text]-trivial sets by higher (...) random sequences. We give a separation between higher notions of randomness, in particular between higher weak 2-randomness and [Formula: see text]-randomness. To do so we investigate classes of functions computable from Kleene’s [Formula: see text] based on strong forms of the higher limit lemma. (shrink)

A central object of study in the field of algorithmic randomness are notions of randomness for sequences, i.e., infinite sequences of zeros and ones. These notions are usually defined with respect to the uniform measure on the set of all sequences, but extend canonically to other computable probability measures. This way each notion of randomness induces an equivalence relation on the computable probability measures where two measures are equivalent if they have the same set of random sequences. In what follows, (...) we study the equivalence relations induced by Martin-Löf randomness, computable randomness, Schnorr randomness and Kurtz randomness, together with the relations of equivalence and consistency from probability theory. We show that all these relations coincide when restricted to the class of computable strongly positive generalized Bernoulli measures. For the case of arbitrary computable measures, we obtain a complete and somewhat surprising picture of the implications between these relations that hold in general. (shrink)

We show the existence of noncomputable oracles which are low for Demuth randomness, answering a question in [15]. We fully characterize lowness for Demuth randomness using an appropriate notion of traceability. Central to this characterization is a partial relativization of Demuth randomness, which may be more natural than the fully relativized version. We also show that an oracle is low for weak Demuth randomness if and only if it is computable.

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 and every 2-random sequence forms a minimal pair in the Turing degrees with every 2-generic sequence. 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. 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. (shrink)

A semimeasure is a generalization of a probability measure obtained by relaxing the additivity requirement to superadditivity. We introduce and study several randomness notions for left-c.e. semimeasures, a natural class of effectively approximable semimeasures induced by Turing functionals. Among the randomness notions we consider, the generalization of weak 2-randomness to left-c.e. semimeasures is the most compelling, as it best reflects Martin-Löf randomness with respect to a computable measure. Additionally, we analyze a question of Shen, a positive answer to which would (...) also have yielded a reasonable randomness notion for left-c.e. semimeasures. Unfortunately, though, we find a negative answer, except for some special cases. (shrink)

A set of infinite binary sequences ${\cal C} \subseteq 2$ℕ is negligible if there is no partial probabilistic algorithm that produces an element of this set with positive probability. The study of negligibility is of particular interest in the context of ${\rm{\Pi }}_1^0 $ classes. In this paper, we introduce the notion of depth for ${\rm{\Pi }}_1^0 $ classes, which is a stronger form of negligibility. Whereas a negligible ${\rm{\Pi }}_1^0 $ class ${\cal C}$ has the property that one cannot (...) probabilistically compute a member of ${\cal C}$ with positive probability, a deep ${\rm{\Pi }}_1^0 $ class ${\cal C}$ has the property that one cannot probabilistically compute an initial segment of a member of ${\cal C}$ with high probability. That is, the probability of computing a length n initial segment of a deep ${\rm{\Pi }}_1^0 $ class converges to 0 effectively in n.We prove a number of basic results about depth, negligibility, and a variant of negligibility that we call tt-negligibility. We provide a number of examples of deep ${\rm{\Pi }}_1^0 $ classes that occur naturally in computability theory and algorithmic randomness. We also study deep classes in the context of mass problems, examine the relationship between deep classes and certain lowness notions in algorithmic randomness, and establish a relationship between members of deep classes and the amount of mutual information with Chaitin’s Ω. (shrink)

The $\Omega $ numbers—the halting probabilities of universal prefix-free machines—are known to be exactly the Martin-Löf random left-c.e. reals. We show that one cannot uniformly produce, from a Martin-Löf random left-c.e. real $\alpha $, a universal prefix-free machine U whose halting probability is $\alpha $. We also answer a question of Barmpalias and Lewis-Pye by showing that given a left-c.e. real $\alpha $, one cannot uniformly produce a left-c.e. real $\beta $ such that $\alpha - \beta $ is neither left-c.e. (...) nor right-c.e. (shrink)