A strong law of computationally weak subsets

DOI10.1142/S0219061311000980MaRDI QIDQ3094357zbMATH OpenFDO

Authors Bjørn Kjos-Hanssen

Publication date 24 October 2011

Published in Journal of Mathematical Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.1967

zbMATH Keywords

computational strengthextinction criterionGalton-Watson processinfinite subsetsrandom sets of integersstrong law

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Combinatorial probability (60C05)

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 $mathcalA$ such that if $XinmathcalA$ then $X$ has an infinite subset $Y$ such that no element of $mathcalA$ is Turing computable from $Y$.

Recommendations

• Infinite subsets of random sets of integers
• On the computability of perfect subsets of sets with positive measure
• Extracting randomness within a subset is hard
• Subclasses of the weakly random reals
• Logical Approaches to Computational Barriers

Cites work

• A fixed-point-free minimal degree
• An introduction to Kolmogorov complexity and its applications
• Comparing DNR and WWKL
• Computability and Randomness
• Infinite subsets of random sets of integers
• Lowness for Kurtz randomness
• Stable Ramsey's theorem and measure
• Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)

Cited in

(4)

• Infinite subsets of random sets of integers
• Extracting randomness within a subset is hard
• On the computability of perfect subsets of sets with positive measure
• Cone avoiding closed sets

This page was built for publication: A strong law of computationally weak subsets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3094357)