ECCC-Report TR10-150https://eccc.weizmann.ac.il/report/2010/150Comments and Revisions published for TR10-150en-usFri, 01 Oct 2010 11:06:25 +0200
Paper TR10-150
| A strong law of computationally weak subsets |
Bjørn Kjos-Hanssen
https://eccc.weizmann.ac.il/report/2010/150We 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$. Fri, 01 Oct 2010 11:06:25 +0200https://eccc.weizmann.ac.il/report/2010/150