COMPUTINGK-TRIVIAL SETS BY INCOMPLETE RANDOM SETS

DOI10.1017/bsl.2013.3zbMath1320.03074arXiv1305.5514OpenAlexW2154760327MaRDI QIDQ2925324

Antonín Kučera, Dan Turetsky, Adam R. Day, Noam Greenberg, Laurent Bienvenu, André Nies, Joseph S. Miller

Publication date: 21 October 2014

Published in: The Bulletin of Symbolic Logic (Search for Journal in Brave)

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

zbMATH Keywords

Kolmogorov complexityalgorithmic randomness\(K\)-trivialitycovering problemChaitin complexityMartin-Löf-randomnessOberwolfach randomness

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Recursively (computably) enumerable sets and degrees (03D25) Algorithmic randomness and dimension (03D32)

Related Items (12)

Lightface $$\mathop {\varPi }\nolimits _{3}^{0}$$ Π 3 0 -Completeness of Density Sets Under Effective Wadge Reducibility ⋮ STRONG JUMP-TRACEABILITY ⋮ USING ALMOST-EVERYWHERE THEOREMS FROM ANALYSIS TO STUDY RANDOMNESS ⋮ RANDOMNESS NOTIONS AND REVERSE MATHEMATICS ⋮ CHAITIN’S Ω AS A CONTINUOUS FUNCTION ⋮ Computing from projections of random points ⋮ Lowness, Randomness, and Computable Analysis ⋮ COARSE REDUCIBILITY AND ALGORITHMIC RANDOMNESS ⋮ Solovay functions and their applications in algorithmic randomness ⋮ LEBESGUE DENSITY AND CLASSES ⋮ Unnamed Item ⋮ Inherent enumerability of strong jump-traceability

Cites Work

• On relative randomness
• Information-theoretic characterizations of recursive infinite strings
• Benign cost functions and lowness properties
• Algorithmic Randomness and Complexity
• Low upper bounds of ideals
• Every sequence is reducible to a random one
• A Theory of Program Size Formally Identical to Information Theory
• Lowness for the class of random sets
• Turing incomparability in Scott sets
• Using random sets as oracles

This page was built for publication: COMPUTINGK-TRIVIAL SETS BY INCOMPLETE RANDOM SETS