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**.