skip to content
 

Trivial measures are not so trivial

Presented by: 
C Porter University of Notre Dame
Date: 
Tuesday 3rd July 2012 - 12:00 to 12:30
Venue: 
INI Seminar Room 1
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}$.

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
Presentation Material: 
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons