Search

In this survey we discuss work of Levin and V’yugin on collections of sequences that are non-negligible in the sense that they can be computed by a probabilistic algorithm with positive probability. More precisely, Levin and V’yugin introduced an ordering on collections of sequences that are closed under Turing equivalence. Roughly speaking, given two such collections $\mathcal {A}$ and $\mathcal {B}$ , $\mathcal {A}$ is below $\mathcal {B}$ in this ordering if $\mathcal {A}\setminus \mathcal {B}$ is negligible. The degree structure associated with this ordering, the Levin–V’yugin degrees (or $\mathrm {LV}$ -degrees), can be shown to be a Boolean algebra, and in fact a measure algebra. We demonstrate the interactions of this work with recent results in computability theory and algorithmic randomness: First, we recall the definition of the Levin–V’yugin algebra and identify connections between its properties and classical properties from computability theory. In particular, we apply results on the interactions between notions of randomness and Turing reducibility to establish new facts about specific LV-degrees, such as the LV-degree of the collection of 1-generic sequences, that of the collection of sequences of hyperimmune degree, and those collections corresponding to various notions of effective randomness. Next, we provide a detailed explanation of a complex technique developed by V’yugin that allows the construction of semi-measures into which computability-theoretic properties can be encoded. We provide two examples of the use of this technique by explicating a result of V’yugin’s about the LV-degree of the collection of Martin-Löf random sequences and extending the result to the LV-degree of the collection of sequences of DNC degree.

In the mid-1970s, Gregory Chaitin proved a novel incompleteness theorem, formulated in terms of Kolmogorov complexity, a measure of complexity that features prominently in algorithmic information theory. Chaitin further claimed that his theorem provides insight into both the source and scope of incompleteness, a claim that has been subject to much criticism. In this article, I consider a new strategy for vindicating Chaitin’s claims, one informed by recent work of Bienvenu, Romashchenko, Shen, Taveneaux, and Vermeeren that extends and refines Chaitin’s incompleteness theorem. As I argue, this strategy, though more promising than previous attempts, fails to vindicate Chaitin’s claims. Lastly, I will suggest an alternative interpretation of Chaitin’s theorem, according to which the theorem indicates a trade-off that comes from working with a sufficiently strong definition of randomness—namely, that we lose the ability to certify randomness.

We examine several notions of randomness for elements in a given ${\Pi }_{1}^{0}$ class $\mathcal {P}$ . Such an effectively closed subset $\mathcal {P}$ of 2 ω may be viewed as the set of infinite paths through the tree $T_{\mathcal {P}}$ of extendible nodes of $\mathcal {P}$ , i.e., those finite strings that extend to a member of $\mathcal {P}$ , so one approach to defining a random member of $\mathcal {P}$ is to randomly produce a path through $T_{\mathcal {P}}$ using a sufficiently random oracle for advice. In addition, this notion of randomness for elements of $\mathcal {P}$ may be induced by a map from 2 ω onto $\mathcal {P}$ that is computable relative to $T_{\mathcal {P}}$ , and the notion even has a characterization in term of Kolmogorov complexity. Another approach is to define a relative measure on $\mathcal {P}$ by conditionalizing the Lebesgue measure on $\mathcal {P}$ , which becomes interesting if $\mathcal {P}$ has Lebesgue measure 0. Lastly, one can alternatively define a notion of incompressibility for members of $\mathcal {P}$ in terms of the amount of branching at levels of $T_{\mathcal {P}}$ . We explore some notions of homogeneity for ${\Pi }_{1}^{0}$ classes, inspired by work of van Lambalgen. A key finding is that in a specific class of sufficiently homogeneous ${\Pi }_{1}^{0}$ classes $\mathcal {P}$ , all of these approaches coincide. We conclude with a discussion of random members of ${\Pi }_{1}^{0}$ classes of positive measure.

A fruitful way of obtaining meaningful, possibly concrete, algorithmically random numbers is to consider a potential behavior of a Turing machine and its probability with respect to a measure (or semi-measure) on the input space of binary codes. In this work we obtain characterizations of the algorithmically random reals in higher randomness classes, as probabilities of certain events that can happen when an oracle universal machine runs probabilistically on a random oracle. Moreover we apply our analysis to several machine models, including oracle Turing machines, prefix-free machines, and models for infinite online computation. We find that in many cases the arithmetical complexity of a property is directly reflected in the strength of the algorithmic randomness of the probability with which it occurs, on any given universal machine. On the other hand, we point to many examples where this does not happen and the probability is a number whose algorithmic randomness is not the maximum possible (with respect to its arithmetical complexity). Finally we find that, unlike the halting probability of a universal machine, the probabilities of more complex properties like totality, cofinality, computability or completeness do not necessarily have the same Turing degree when they are defined with respect to different universal machines.

In this article, I consider the status of several statements analogous to the Church–Turing thesis that assert that some definition of algorithmic randomness captures the intuitive conception of randomness. I argue that we should not only reject the theses that have appeared in the algorithmic randomness literature, but more generally that we ought not evaluate the adequacy of a definition of randomness on the basis of whether it captures the so-called intuitive conception of randomness to begin with. Instead, I argue that a more promising alternative is to evaluate the adequacy of a definition of randomness on the basis of whether it captures what I refer to as a “notion of almost everywhere typicality.” In support of my main claims, I will appeal to recent work in showing the connection between of algorithmic randomness and certain “almost everywhere” theorems from classical mathematics.

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.

Osvald Demuth (1936–1988) studied constructive analysis from the viewpoint of the Russian school of constructive mathematics. In the course of his work he introduced various notions of effective null set which, when phrased in classical language, yield a number of major algorithmic randomness notions. In addition, he proved several results connecting constructive analysis and randomness that were rediscovered only much later.In this paper, we trace the path that took Demuth from his constructivist roots to his deep and innovative work on the interactions between constructive analysis, algorithmic randomness, and computability theory. We will focus specifically on (i) Demuth’s work on the differentiability of Markov computable functions and his study of constructive versions of the Denjoy alternative, (ii) Demuth’s independent discovery of the main notions of algorithmic randomness, as well as the development of Demuth randomness, and (iii) the interactions of truth-table reducibility, algorithmic randomness, and semigenericity in Demuth’s work.

We study algorithmically random closed subsets of $2^\omega$, algorithmically random continuous functions from $2^\omega$ to $2^\omega$, and algorithmically random Borel probability measures on $2^\omega$, especially the interplay between these three classes of objects. Our main tools are preservation of randomness and its converse, the no randomness ex nihilo principle, which say together that given an almost-everywhere defined computable map between an effectively compact probability space and an effective Polish space, a real is Martin-L\"of random for the pushforward measure if and only if its preimage is random with respect to the measure on the domain. These tools allow us to prove new facts, some of which answer previously open questions, and reprove some known results more simply. Our main results are the following. First we answer an open question of Barmapalias, Brodhead, Cenzer, Remmel, and Weber by showing that $\mathcal{X}\subseteq2^\omega$ is a random closed set if and only if it is the set of zeros of a random continuous function on $2^\omega$. As a corollary we obtain the result that the collection of random continuous functions on $2^\omega$ is not closed under composition. Next, we construct a computable measure $Q$ on the space of measures on $2^\omega$ such that $\mathcal{X}\subseteq2^\omega$ is a random closed set if and only if $\mathcal{X}$ is the support of a $Q$-random measure. We also establish a correspondence between random closed sets and the random measures studied by Culver in previous work. Lastly, we study the ranges of random continuous functions, showing that the Lebesgue measure of the range of a random continuous function is always contained in $(0,1)$.

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.

A semi-measure is a generalization of a probability measure obtained by relaxing the additivity requirement to super-additivity. We introduce and study several randomness notions for left-c.e. semi-measures, a natural class of effectively approximable semi-measures induced by Turing functionals. Among the randomness notions we consider, the generalization of weak 2-randomness to left-c.e. semi-measures is the most compelling, as it best reflects Martin-L\"of 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. semi-measures. Unfortunately though, we find a negative answer, except for some special cases.

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.

In this paper, I discuss the extent to which Kolmogorov drew upon von Mises' work in addressing the problem of why probability is applicable to events in the real world, which I refer to as the problem of the applicability of probability, or the applicability problem for short. In particular, I highlight the role of randomness in Kolmogorov's account, and I argue that this role differs significantly from the role that randomness plays in von Mises' account.

We study generalizations of Demuth’s Theorem, which states that the image of a Martin-Löf random real under a tt-reduction is either computable or Turing equivalent to a Martin-Löf random real. We show that Demuth’s Theorem holds for Schnorr randomness and computable randomness (answering a question of Franklin), but that it cannot be strengthened by replacing the Turing equivalence in the statement of the theorem with wtt-equivalence. We also provide some additional results about the Turing and tt-degrees of reals that are random with respect to some computable measure.