Turing incomparability in Scott sets

DOI10.1090/S0002-9939-07-08871-5zbMath1123.03039arXivmath/0602439OpenAlexW1996754808MaRDI QIDQ5308142

Antonín Kučera, Theodore A. Slaman

Publication date: 27 September 2007

Published in: Proceedings of the American Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

Scott setalgorithmic randomnessTuring degreelow for randomnonrecursive setTuring incomparable

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Other Turing degree structures (03D28)

Related Items (6)

COMPUTINGK-TRIVIAL SETS BY INCOMPLETE RANDOM SETS ⋮ On the gap between trivial and nontrivial initial segment prefix-free complexity ⋮ A measure-theoretic proof of Turing incomparability ⋮ WEAKLY 2-RANDOMS AND 1-GENERICS IN SCOTT SETS ⋮ \(\Pi_1^0 \) classes, LR degrees and Turing degrees ⋮ DNR AND INCOMPARABLE TURING DEGREES

Cites Work

• On relative randomness
• Classical recursion theory. The theory of functions and sets of natural numbers
• \(\Pi_1^0\) classes and minimal degrees
• Initial segments of the degrees of unsolvability
• Lowness properties and randomness
• On the degrees less than 0'
• Algorithmic Randomness and Complexity
• Calibrating Randomness
• Algorithmic Information Theory
• Using random sets as oracles
• A unified approach to the definition of random sequences
• ∏ 0 1 Classes and Degrees of Theories
• On Suborderings of Degrees of Recursive Unsolvability
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Turing incomparability in Scott sets