Turing incomparability in Scott sets

DOI10.1090/S0002-9939-07-08871-5MaRDI QIDQ5308142zbMATH OpenOpenAlexFDO

Authors 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

algorithmic randomnessTuring degreeScott setlow for randomnonrecursive setTuring incomparable

Mathematics Subject Classification ID

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

Abstract: For every Scott set F and every nonrecursive set X in F, there is a Y in F such that X and Y are Turing incomparable.

Recommendations

• A measure-theoretic proof of Turing incomparability
• WEAKLY 2-RANDOMS AND 1-GENERICS IN SCOTT SETS
• scientific article; zbMATH DE number 1747699
• Comparing incomparable kleene degrees
• scientific article; zbMATH DE number 2144532

Cites work

• scientific article; zbMATH DE number 3861137 (Why is no real title available?)
• scientific article; zbMATH DE number 4051596 (Why is no real title available?)
• scientific article; zbMATH DE number 4091484 (Why is no real title available?)
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• scientific article; zbMATH DE number 1531917 (Why is no real title available?)
• scientific article; zbMATH DE number 1531920 (Why is no real title available?)
• A unified approach to the definition of random sequences
• Algorithmic Information Theory
• Algorithmic randomness and complexity.
• Calibrating Randomness
• Classical recursion theory. The theory of functions and sets of natural numbers
• Initial segments of the degrees of unsolvability
• Lowness properties and randomness
• On Suborderings of Degrees of Recursive Unsolvability
• On relative randomness
• On the degrees less than 0'
• Using random sets as oracles
• \(\Pi_1^0\) classes and minimal degrees
• ∏ 0 1 Classes and Degrees of Theories

Cited in

(9)

• WEAKLY 2-RANDOMS AND 1-GENERICS IN SCOTT SETS
• scientific article; zbMATH DE number 2144532 (Why is no real title available?)
• Comparing incomparable kleene degrees
• Computuing \(K\)-trivial sets by incomplete random sets
• On the gap between trivial and nontrivial initial segment prefix-free complexity
• Kleene, Rabin, and Scott Are Available
• \(\Pi_1^0 \) classes, LR degrees and Turing degrees
• DNR and incomparable Turing degrees
• A measure-theoretic proof of Turing incomparability

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

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