Trivial measures are not so trivial

32 mins 26 secs, 29.70 MB, MP3 44100 Hz, 125.0 kbits/sec

Share this media item:

Embed this media item:

<iframe width="_width_" height="_height_" src="https://sms.cam.ac.uk/media/1273636/embed" frameborder="0" scrolling="no" allowfullscreen></iframe>

Choose size:

About this item

Available Formats

About this item

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


Created:	2012-07-10 16:42
Collection:	Semantics and Syntax: A Legacy of Alan Turing
Publisher:	Isaac Newton Institute
Copyright:	Porter, C
Language:	eng (English)


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 μ on 2ω is trivial if the support of μ 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 a trivial measure μ such that every sequence that is Martin-Löf random with respect to μ is an atom of μ (i.e., μ assigns positive probability to such a sequence), while there are sequences that are Schnorr random with respect to μ that are not atoms of μ (thus yielding a counterexample to a result claimed by Schnorr), and a trivial measure μ such that (a) the collection of sequences that are Martin-Löf random with respect to μ are not all atoms of μ and (b) every sequence that is Martin-Löf random with respect to μ and is not an atom of μ is also not weakly 2-random with respect to μ. Lastly, I will show that, if we consider the class of LR-degrees associated with a trivial measure μ (generalizing the standard definition of the LR-degrees), then for every finite distributive lattice L=(L,≤), there is a trivial measure μ such that the the collection of LR-degrees with respect to μ is a finite distributive lattice that is isomorphic to L.

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 μ on 2ω is trivial if the support of μ 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

a trivial measure μ such that every sequence that is Martin-Löf random with respect to μ is an atom of μ (i.e., μ assigns positive probability to such a sequence), while there are sequences that are Schnorr random with respect to μ that are not atoms of μ (thus yielding a counterexample to a result claimed by Schnorr), and

a trivial measure μ such that (a) the collection of sequences that are Martin-Löf random with respect to μ are not all atoms of μ and (b) every sequence that is Martin-Löf random with respect to μ and is not an atom of μ is also not weakly 2-random with respect to μ.

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

Available Formats

Format	Quality	Bitrate	Size
MPEG-4 Video	640x360	1.84 Mbits/sec	451.55 MB	View	Download
WebM	640x360	801.54 kbits/sec	191.29 MB	View	Download
Flash Video	484x272	568.55 kbits/sec	135.61 MB	View	Download
iPod Video	480x270	505.95 kbits/sec	120.74 MB	View	Download
MP3 *	44100 Hz	125.0 kbits/sec	29.70 MB	Listen	Download
Auto	(Allows browser to choose a format it supports)