Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > MARTIN-LÖF RANDOMNESS:
Reports tagged with Martin-Löf randomness:
TR10-150 | 19th September 2010
Bjørn Kjos-Hanssen

#### A strong law of computationally weak subsets

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

ISSN 1433-8092 | Imprint