Lowness for bounded randomness

DOI10.1016/J.TCS.2012.06.004MaRDI QIDQ690469zbMATH OpenOpenAlexFDO

Authors Keng Meng Ng, Rodney G. Downey

Publication date 27 November 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2012.06.004

zbMATH Keywords

algorithmic randomness\(K\)-trivialityfinite randomnesslow for random

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Bounded randomness
• Lowness properties and randomness
• Randomness and lowness notions via open covers
• Lowness of higher randomness notions
• Relative randomness and cardinality

Cites work

• scientific article; zbMATH DE number 5064956 (Why is no real title available?)
• A hierarchy of computably enumerable degrees
• Algorithmic randomness and complexity.
• Bounded randomness
• Characterizing lowness for Demuth randomness
• Computability and Randomness
• Low for random reals and positive-measure domination
• MASS PROBLEMS AND HYPERARITHMETICITY
• Recursive computational depth.
• TOTALLY ω-COMPUTABLY ENUMERABLE DEGREES AND BOUNDING CRITICAL TRIPLES
• Turing degrees of reals of positive effective packing dimension
• Working with strong reducibilities above totally \(\omega \)-c.e. and array computable degrees

Cited in

(6)

• Bounded randomness
• New lower bounds for the Randić spread
• Randomness and lowness notions via open covers
• Lowness, Randomness, and Computable Analysis
• Lowness for Kurtz randomness
• Characterizing lowness for Demuth randomness

This page was built for publication: Lowness for bounded randomness

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