Cone avoidance and randomness preservation

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

May 29, 2014

This is my abstract for a talk at the 9th International Conference on Computability, Complexity and Randomness, held at the Institute for Mathematical Sciences, National University of Singapore, June 9–13, 2014.

This is joint work with Frank Stephan. Our paper “Cone avoidance and randomness preservation” has been conditionally accepted for publication in Annals of Pure and Applied Logic.

Let X be an infinite sequence of 0’s and 1’s. Let f be a computable function. Recall that X is strongly f-random if and only if the a priori Kolmogorov complexity of each finite initial segment σ of X is bounded below by f(σ) minus a constant. We study the problem of finding a PA-complete Turing oracle which preserves the strong f-randomness of X while avoiding a Turing cone. In the context of this problem, we prove that the cones which cannot always be avoided are precisely the K-trivial ones. We also prove: (1) If f is convex and X is strongly f-random and Y is Martin-Löf random relative to X, then X is strongly f-random relative to Y. (2) X is complex relative to some oracle if and only if X is μ-random for some continuous probability measure μ.