Propagation of partial randomness

Stephen G. Simpson Department of Mathematics Pennsylvania State University http://www.math.psu.edu/simpson/

January 31, 2012

This is my abstract for the Workshop on Proof Theory and Computability, Philosophical Frontiers in Reverse Mathematics, to be held in Tokyo, February 20–23, 2012.

Let x be an infinite sequence of 0’s and 1’s, i.e., x ∈ {0, 1}^{ℕ}. Even if x is not Martin-Löf random, we can nevertheless quantify the amount of partial randomness which is inherent in x. Several researchers including Tadaki 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. Let KA denote a priori Kolmogorov complexity, i.e., KA(σ) = − log_{2} m(σ) where m is Levin’s universal left-r.e. semimeasure. Note that KA is similar but not identical to the more familiar KP = prefix-free Kolmogorov complexity. Given a computable function f : {0, 1}^{∗} → (−∞, ∞), we say that x ∈ {0, 1}^{ℕ} 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 frandom relative to z. Theorem 2. Assume that ∀n (x_{n} is strongly f_{n}-random). Then, we can find a PA-oracle z such that ∀n (x_{n} is strongly f_{n}-random relative to z). We also show that Theorems 1 and 2 fail with KA replaced by KP.