A measure-theoretic proof of Turing incomparability

DOI10.1016/J.APAL.2010.07.004zbMath1227.03056OpenAlexW2027737305MaRDI QIDQ638476

Chris J. Conidis

Publication date: 12 September 2011

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2010.07.004

zbMATH Keywords

forcingcomputability theoryreverse mathematicsmeasure theorygenericityrandomnessweak König's lemmaWKLBaire category theoremTuring degrees\(\omega\)-modelWWKL

Mathematics Subject Classification ID

Constructive and recursive analysis (03F60) Foundations of classical theories (including reverse mathematics) (03B30) Second- and higher-order arithmetic and fragments (03F35) Other Turing degree structures (03D28)

Related Items (2)

WEAKLY 2-RANDOMS AND 1-GENERICS IN SCOTT SETS ⋮ DNR AND INCOMPARABLE TURING DEGREES

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On relative randomness
• Information-theoretic characterizations of recursive infinite strings
• Lowness properties and randomness
• Measure theory and weak König's lemma
• Lowness notions, measure and domination
• The Baire category theorem in weak subsystems of second-order arithmetic
• Turing incomparability in Scott sets
• Using random sets as oracles
• Degrees of Unsolvability. (AM-55)
• A unified approach to the definition of random sequences

This page was built for publication: A measure-theoretic proof of Turing incomparability