A strong law of computationally weak subsets

A strong law of computationally weak subsets

Journal of Mathematical Logic 11 (2011) no. 1, 1—10.
DOI: 10.1142/S0219061311000980
Electronic Colloquium on Computational Complexity, Report No. 150 (2010).

This paper establishes a new statistical law, namely that for each random sequence
$$0111011101101101101\ldots$$
it is possible to replace some of the 1s by 0s (in other words, form a subset of 1s) in such a way that no random sequence can be recovered by computational means.

To illustrate, imagine that the new sequence looks like
$$0111010101101000101\ldots$$

Technically the result is that each 2-random set has an infinite subset computing no 1-random set. It is perhaps the main result obtained under Prof. Kjos-Hanssen’s grant NSF DMS-0901020 (2009-2013).
Joseph S. Miller at U. of Wisconsin has established a strengthening of this result replacing 2-random by 1-random, but that result is so far unpublished.

Dr. Bjørn Kjos-Hanssen is a professor at the University of Hawai‘i at Manoa in the Department of Mathematics. His research deals with the abstract theory of computation, computability, randomness and compression algorithms.

Kjos-Hanssen is the author of more than 20 papers in journals including the prestigious Mathematical Research Letters and Transactions of the American Mathematical Society, and has a PhD from UC Berkeley in the subject Logic and the Methodology of Science.