The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content

SAS

Seminar

Trivial measures are not so trivial

Porter, C (University of Notre Dame)
Tuesday 03 July 2012, 12:00-12:30

Seminar Room 1, Newton Institute

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}$.

Presentation

[pdf ]

Video

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.

Back to top ∧