SAS

Abstract

Although algorithmic randomness with respect to various biased computable measures is well-studied, little attention has been paid to algorithmic randomness with respect to computable trivial measures, where a measure $\mu$ on $2^\omega$ is trivial if the support of $\mu$ consists of a countable collection of sequences. In this talk, I will show that there is much more structure to trivial measures than has been previously suspected. In particular, I will outline the construction of

1. a trivial measure $\mu$ such that every sequence that is Martin-Löf random with respect to $\mu$ is an atom of $\mu$ (i.e., $\mu$ assigns positive probability to such a sequence), while there are sequences that are Schnorr random with respect to $\mu$ that are not atoms of $\mu$ (thus yielding a counterexample to a result claimed by Schnorr), and
2. a trivial measure $\mu$ such that (a) the collection of sequences that are Martin-Löf random with respect to $\mu$ are not all atoms of $\mu$ and (b) every sequence that is Martin-Löf random with respect to $\mu$ and is not an atom of $\mu$ is also not weakly 2-random with respect to $\mu$.

Lastly, I will show that, if we consider the class of $LR$-degrees associated with a trivial measure $\mu$ (generalizing the standard definition of the $LR$-degrees), then for every finite distributive lattice $\mathcal{L}=(L, \leq)$, there is a trivial measure $\mu$ such that the the collection of $LR$-degrees with respect to $\mu$ is a finite distributive lattice that is isomorphic to $\mathcal{L}$.