We compare various notions of algorithmic randomness. First we consider relativized randomness. A set is n-random if it is Martin-Löf random relative to ∅. We show that a set is 2-random if and only if there is a constant c such that infinitely many initial segments x of the set are c-incompressible: C ≥ |x|-c. The ‘only if' direction was obtained independently by Joseph Miller. This characterization can be extended to the case of time-bounded C-complexity. Next we prove some results (...) on lowness. Among other things, we characterize the 2-random sets as those 1-random sets that are low for Chaitin's Ω. Also, 2-random sets form minimal pairs with 2-generic sets. The r.e. low for Ω sets coincide with the r.e. K-trivial ones. Finally we show that the notions of Martin-Löf randomness, recursive randomness, and Schnorr randomness can be separated in every high degree while the same notions coincide in every non-high degree. We make some remarks about hyperimmune-free and PA-complete degrees. (shrink)

An infinite binary sequence is complex if the Kolmogorov complexity of its initial segments is bounded below by a computable function. We prove that a $\Pi _{1}^{0}$ class P contains a complex element if and only if it contains a wtt-cover for the Cantor set. That is, if and only if for every Y ⊆ ω there is an X in P such that X ⩾wtt Y. We show that this is also equivalent to the $\Pi _{1}^{0}$ class's being large (...) in some sense. We give an example of how this result can be used in the study of scattered linear orders. (shrink)

We consider two axioms of second-order arithmetic. These axioms assert, in two different ways, that infinite but narrow binary trees always have infinite paths. We show that both axioms are strictly weaker than Weak König's Lemma, and incomparable in strength to the dual statement (WWKL) that wide binary trees have paths.

We investigate the notion of hyperimmunity with respect to how it can be applied to Π{\sp 0}{\sb 1} classes and their Muchnik degrees. We show that hyperimmunity is a strong enough concept to prove the existence of Π{\sp 0}{\sb 1} classes with intermediate Muchnik degree—in contrast to Post's attempts to construct intermediate c.e. degrees.

Schnorr randomness is a notion of algorithmic randomness for real numbers closely related to Martin-Löf randomness. After its initial development in the 1970s the notion received considerably less attention than Martin-Löf randomness, but recently interest has increased in a range of randomness concepts. In this article, we explore the properties of Schnorr random reals, and in particular the c.e. Schnorr random reals. We show that there are c.e. reals that are Schnorr random but not Martin-Löf random, and provide a new (...) characterization of Schnorr random real numbers in terms of prefix-free machines. We prove that unlike Martin-Löf random c.e. reals, not all Schnorr random c.e. reals are Turing complete, though all are in high Turing degrees. We use the machine characterization to define a notion of "Schnorr reducibility" which allows us to calibrate the Schnorr complexity of reals. We define the class of "Schnorr trivial" reals, which are ones whose initial segment complexity is identical with the computable reals, and demonstrate that this class has non-computable members. (shrink)

A positive answer to a question of M. van Lambalgen and D. Zambella whether there exist nonrecursive sets that are low for the class of random sets is obtained. Here a set A is low for the class RAND of random sets if RAND = RAND A.

Schnorr randomness and computable randomness are natural concepts of random sequences. However van Lambalgen’s Theorem fails for both randomnesses. In this paper we define truth-table Schnorr randomness and truth-table reducible randomness, for which we prove that van Lambalgen's Theorem holds. We also show that the classes of truth-table Schnorr random reals relative to a high set contain reals Turing equivalent to the high set. It follows that each high Schnorr random real is half of a real for which van Lambalgen's (...) Theorem fails. Moreover we establish the coincidence between triviality and lowness notions for truth-table Schnorr randomness. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim. (shrink)

A real is Martin-Löf (Schnorr) random if it does not belong to any effectively presented null ${\Sigma^0_1}$ (recursive) class of reals. Although these randomness notions are very closely related, the set of Turing degrees containing reals that are K-trivial has very different properties from the set of Turing degrees that are Schnorr trivial. Nies proved in (Adv Math 197(1):274–305, 2005) that all K-trivial reals are low. In this paper, we prove that if ${{\bf h'} \geq_T {\bf 0''}}$ , then h (...) contains a Schnorr trivial real. Since this concept appears to separate computational complexity from computational strength, it suggests that Schnorr trivial reals should be considered in a structure other than the Turing degrees. (shrink)

We study inversions of the jump operator on ${\mathrm{\Pi }}_{1}^{0}$ classes, combined with certain basis theorems. These jump inversions have implications for the study of the jump operator on the random degrees—for various notions of randomness. For example, we characterize the jumps of the weakly 2-random sets which are not 2-random, and the jumps of the weakly 1-random relative to 0′ sets which are not 2-random. Both of the classes coincide with the degrees above 0′ which are not 0′-dominated. A (...) further application is the complete solution of [24, Problem 3.6.9]: one direction of van Lambalgen's theorem holds for weak 2-randomness, while the other fails. Finally we discuss various techniques for coding information into incomplete randoms. Using these techniques we give a negative answer to [24, Problem 8.2.14]: not all weakly 2-random sets are array computable. In fact, given any oracle X, there is a weakly 2-random which is not array computable relative to X. This contrasts with the fact that all 2-random sets are array computable. (shrink)

We give several characterizations of Schnorr trivial sets, including a new lowness notion for Schnorr triviality based on truth-table reducibility. These characterizations allow us to see not only that some natural classes of sets, including maximal sets, are composed entirely of Schnorr trivials, but also that the Schnorr trivial sets form an ideal in the truth-table degrees but not the weak truth-table degrees. This answers a question of Downey, Griffiths and LaForte.

We prove that there exists a noncomputable c.e. real which is low for weak 2-randomness, a definition of randomness due to Kurtz, and that all reals which are low for weak 2-randomness are low for Martin-Löf randomness.

Covering the basics as well as recent research results, this book provides a very readable introduction to the exciting interface of computability and ...

We show that van Lambalgen's Theorem fails with respect to recursive randomness and Schnorr randomness for some real in every high degree and provide a full characterization of the Turing degrees for which van Lambalgen's Theorem can fail with respect to Kurtz randomness. However, we also show that there is a recursively random real that is not Martin-Löf random for which van Lambalgen's Theorem holds with respect to recursive randomness.

Intuitively, a sequence such as 101010101010101010… does not seem random, whereas 101101011101010100…, obtained using coin tosses, does. How can we reconcile this intuition with the fact that both are statistically equally likely? What does it mean to say that an individual mathematical object such as a real number is random, or to say that one real is more random than another? And what is the relationship between randomness and computational power. The theory of algorithmic randomness uses tools from computability theory (...) and algorithmic information theory to address questions such as these. Much of this theory can be seen as exploring the relationships between three fundamental concepts: relative computability, as measured by notions such as Turing reducibility; information content, as measured by notions such as Kolmogorov complexity; and randomness of individual objects, as first successfully defined by Martin-Löf. Although algorithmic randomness has been studied for several decades, a dramatic upsurge of interest in the area, starting in the late 1990s, has led to significant advances. This is the first comprehensive treatment of this important field, designed to be both a reference tool for experts and a guide for newcomers. It surveys a broad section of work in the area, and presents most of its major results and techniques in depth. Its organization is designed to guide the reader through this large body of work, providing context for its many concepts and theorems, discussing their significance, and highlighting their interactions. It includes a discussion of effective dimension, which allows us to assign concepts like Hausdorff dimension to individual reals, and a focused but detailed introduction to computability theory. It will be of interest to researchers and students in computability theory, algorithmic information theory, and theoretical computer science. (shrink)

The strong measure zero sets of reals have been widely studied in the context of set theory of the real line. The notion of strong measure zero is straightforwardly effectivized. A set of reals is said to be of effective strong measure zero if for any computable sequence {εn}n∈N{εn}n∈N of positive rationals, a sequence of intervals InIn of diameter εnεn covers the set. We observe that a set is of effective strong measure zero if and only if it is of (...) measure zero with respect to any outer measure constructed by Monroe's Method from a computable atomless outer premeasure defined on all open balls. This measure-theoretic restatement permits many characterizations of strong measure zero in terms of semimeasures as well as martingales. We show that for closed subsets of Cantor space, effective strong nullness is equivalent to another well-studied notion called diminutiveness , the property of not having a computably perfect subset. Further, we prove that if P is a nonempty effective strong measure zero Π01 set consisting only of noncomputable elements, then some Martin-Löf random reals compute no element in P , and P has an element that computes no autocomplex real. Finally, we construct two different special Π01 sets, one of which is not of effective strong measure zero, but consists only of infinitely-often K-trivial reals, and the other is perfect and of effective strong measure zero, but contains no anti-complex reals. (shrink)

Kuera, A., On relative randomness, Annals of Pure and Applied Logic 63 61–67. It is the aim of the paper to answer a question raised by M. van Lambalgen and D. Zambella whether there can be a nonrecursive set A having the property that there is a set B such that B is 1-random relative to A and simultaneously A is recursive in B. We give apositive answer to this question as well as further information about relative randomness.

We prove that superhigh sets can be jump traceable, answering a question of Cole and Simpson. On the other hand, we show that such sets cannot be weakly 2-random. We also study the class $superhigh^\diamond$ and show that it contains some, but not all, of the noncomputable K-trivial sets.

An infinite binary sequence is complex if the Kolmogorov complexity of its initial segments is bounded below by a computable function. We prove that a Π₁⁰ class P contains a complex element if and only if it contains a wtt-cover for the Cantor set. That is, if and only if for every Y⊆ω there is an X in P such that X≥wtt Y. We show that this is also equivalent to the Π₁⁰ class's being large in some sense. We give (...) an example of how this result can be used in the study of scattered linear orders. (shrink)

We prove that degrees that are low for Kurtz randomness cannot be diagonally non-recursive. Together with the work of Stephan and Yu [16], this proves that they coincide with the hyperimmune-free non-DNR degrees, which are also exactly the degrees that are low for weak 1-genericity. We also consider Low(M, Kurtz), the class of degrees a such that every element of M is a-Kurtz random. These are characterised when M is the class of Martin-Löf random, computably random, or Schnorr random reals. (...) We show that Low(ML, Kurtz) coincides with the non-DNR degrees, while both Low(CR, Kurtz) and Low(Schnorr, Kurtz) are exactly the non-high, non-DNR degrees. (shrink)

We examine the randomness and triviality of reals using notions arising from martingales and prefix-free machines.

We investigate the relationship between lowness for Schnorr randomness and Schnorr triviality. We show that a real is low for Schnorr randomness if and only if it is Schnorr trivial and hyperimmune free.

We prove that there are uncountably many sets that are low for the class of Schnorr random reals. We give a purely recursion theoretic characterization of these sets and show that they all have Turing degree incomparable to 0'. This contrasts with a result of Kučera and Terwijn [5] on sets that are low for the class of Martin-Löf random reals.

We study the connection between Schnorr triviality and genericity. We show that while no 2-generic is Turing equivalent to a Schnorr trivial and no 1-generic is tt-equivalent to a Schnorr trivial, there is a 1-generic that is Turing equivalent to a Schnorr trivial. However, every such 1-generic must be high. As a corollary, we prove that not all K-trivials are Schnorr trivial. We also use these techniques to extend a previous result and show that the bases of cones of Schnorr (...) trivial Turing degrees are precisely those whose jumps are at least 0". (shrink)

The property of smallness for Π01 classes is introduced and is investigated with respect to Medvedev and Muchnik degree. It is shown that the property of containing a small Π01 class depends only on the Muchnik degree of a Π01 class. A comparison is made with the idea of thinness for Π01 classesmsthm.

The property of smallness for Π0 1 classes is introduced and is investigated with respect to Medvedev and Muchnik degree. It is shown that the property of containing a small Π0 1 class depends only on the Muchnik degree of a Π0 1 class. A comparison is made with the idea of thinness for Π0 1 classesmsthm.