Christopher Porter

In this paper, I evaluate the claim that the equivalence of multiple intensionally distinct definitions of random sequence provides evidence for the claim that these definitions capture the intuitive conception of randomness, concluding that the former claim is false. I then develop an alternative account of the significance of randomness-theoretic equivalence results, arguing that they are instances of a phenomenon I refer to as schematic equivalence. On my account, this alternative approach has the virtue of providing the plurality of definitions of randomness with conceptual unity and a rationale for certain investigations that are carried out in the field.

Osvald Demuth 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 Demuth’s work on the differentiability of Markov computable functions and his study of constructive versions of the Denjoy alternative, Demuth’s independent discovery of the main notions of algorithmic randomness, as well as the development of Demuth randomness, and the interactions of truth-table reducibility, algorithmic randomness, and semigenericity in Demuth’s work.

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.

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.

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 Ω.

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, 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.