Propagation of partial randomness

58 mins 32 secs, 216.97 MB, iPod Video 480x270, 29.97 fps, 44100 Hz, 506.08 kbits/sec

Share this media item:

Embed this media item:

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

Choose size:

About this item

Available Formats

About this item

Description:	Simpson, S (Pennsylvania State University) Tuesday 03 July 2012, 09:00-10:00


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


Abstract:	Let X be an infinite sequence of 0's and 1's, i.e., X∈{0,1}N. Even if X is not Martin-Löf random, we can nevertheless quantify the amount of partial randomness which is inherent in X. Many researchers including Calude, Hudelson, Kjos-Hanssen, Merkle, Miller, Reimann, Staiger, Tadaki, and Terwijn have studied partial randomness. We now present some new results due to Higuchi, Hudelson, Simpson and Yokoyama concerning propagation of partial randomness. Our results say that if X has a specific amount of partial randomness, then X has an equal amount of partial randomness relative to certain Turing oracles. More precisely, let KA denote a priori Kolmogorov complexity, i.e., KA(σ)=−log2m(σ) where m is Levin's universal left-r.e. semimeasure. Note that KA is similar but not identical to the more familiar prefix-free Kolmogorov complexity. Given a computable function f:{0,1}∗→[0,∞), we say that X∈{0,1}N is strongly f-random if ∃c∀n(KA(X↾{1,…,n})>f(X↾{1,…,n})−c). Two of our results read as follows. Theorem 1. Assume that X is strongly f-random and Turing reducible to Y where Y is Martin-Löf random relative to Z. Then X is strongly f-random relative to Z. Theorem 2. Assume that ∀i(Xi is strongly fi-random). Then, we can find a PA-oracle Z such that ∀i(Xi is strongly fi-random relative to Z). We also show that Theorems 1 and 2 fail badly with KA replaced by KP= prefix-free complexity.

Abstract:

Let X be an infinite sequence of 0's and 1's, i.e., X∈{0,1}N. Even if X is not Martin-Löf random, we can nevertheless quantify the amount of partial randomness which is inherent in X. Many researchers including Calude, Hudelson, Kjos-Hanssen, Merkle, Miller, Reimann, Staiger, Tadaki, and Terwijn have studied partial randomness. We now present some new results due to Higuchi, Hudelson, Simpson and Yokoyama concerning propagation of partial randomness. Our results say that if X has a specific amount of partial randomness, then X has an equal amount of partial randomness relative to certain Turing oracles. More precisely, let KA denote a priori Kolmogorov complexity, i.e., KA(σ)=−log2m(σ) where m is Levin's universal left-r.e. semimeasure. Note that KA is similar but not identical to the more familiar prefix-free Kolmogorov complexity. Given a computable function f:{0,1}∗→[0,∞), we say that X∈{0,1}N is strongly f-random if ∃c∀n(KA(X↾{1,…,n})>f(X↾{1,…,n})−c). Two of our results read as follows.
Theorem 1. Assume that X is strongly f-random and Turing reducible to Y where Y is Martin-Löf random relative to Z. Then X is strongly f-random relative to Z.

Theorem 2. Assume that ∀i(Xi is strongly fi-random). Then, we can find a PA-oracle Z such that ∀i(Xi is strongly fi-random relative to Z).

We also show that Theorems 1 and 2 fail badly with KA replaced by KP= prefix-free complexity.

Available Formats

Format	Quality	Bitrate	Size
MPEG-4 Video	640x360	1.84 Mbits/sec	811.84 MB	View	Download
WebM	640x360	1.33 Mbits/sec	587.28 MB	View	Download
Flash Video	484x272	568.65 kbits/sec	243.72 MB	View	Download
iPod Video *	480x270	506.08 kbits/sec	216.97 MB	View	Download
MP3	44100 Hz	125.01 kbits/sec	53.46 MB	Listen	Download
Auto	(Allows browser to choose a format it supports)