Turing incomparability in Scott sets

DOI10.1090/S0002-9939-07-08871-5zbMATH Open1123.03039arXivmath/0602439OpenAlexW1996754808MaRDI QIDQ5308142FDOQ5308142

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)

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.

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

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

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)

Cites Work

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

Cited In (9)

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

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)