Propagation of partial randomness

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

June 25, 2012

This is my abstract for the 7th International Conference on Computability, Complexity and Randomness, to be held at the Isaac Newton Institute for Mathematical Sciences in Cambridge, England, July 2–6, 2012.

Let X be an infinite sequence of 0’s and 1’s. 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. To be precise, let KA denote \underline{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 = \underline{prefix-free Kolmogorov complexity}. Let ℕ = {1, 2, 3, …}. Given a computable function f : {0, 1}^{∗} → ℕ, we say that X ∈ \{0, 1\}^{ℕ} is \underline{strongly f-random} if ∃c ∀n (KA(X↾\{1, …, n\}) > f(X↾\{1, …, n\})−c). We show that X is \underline{autocomplex} in the sense of Kjos-Hanssen/Merkle/Stephan if and only if X is strongly f-random for some f such that {f(X↾{1, …, n}) | n ∈ ℕ} is unbounded. Thus the concept of strong f-randomness provides a fine hierarchy of autocomplexity. Two of our propagation 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 (X_{i} is strongly f_{i}-random). Then, we can find a PA-oracle Z such that ∀i (X_{i} is strongly f_{i}-random relative to Z). We also show that Theorems 1 and 2 fail if KA is replaced by KP.