Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR10-150 | 19th September 2010 03:21

A strong law of computationally weak subsets

RSS-Feed




TR10-150
Authors: Bjørn Kjos-Hanssen
Publication: 1st October 2010 11:06
Downloads: 1797
Keywords: 


Abstract:

We show that in the setting of fair-coin measure on the power set of the natural numbers, each sufficiently random set has an infinite subset that computes no random set. That is, there is an almost sure event $\mathcal A$ such that if $X\in\mathcal A$ then $X$ has an infinite subset $Y$ such that no element of $\mathcal A$ is Turing computable from $Y$.



ISSN 1433-8092 | Imprint