A measure-theoretic proof of Turing incomparability
type: Item
instance of: scholarly article
title: A measure-theoretic proof of Turing incomparability
zbMATH Open document ID: 1227.03056
author: Chris J. Conidis
published in: Annals of Pure and Applied Logic
publication date: 2011-09-12T00:00:00Z
review text: The main result of this paper is that whenever \(A\) is a noncomputable set in an \(\omega\)-model of WWKL, there is another set \(B\) in the model which is Turing incomparable to \(A\). This theorem extends the similar result for \(\omega\)-models of WKL proved by \textit{A. Kučera} and \textit{T. A. Slaman} [``Turing incomparability in Scott sets'', Proc. Am. Math. Soc. 135, No. 11, 3723--3731 (2007; Zbl 1123.03039)], which answers a question of Friedman and McAllister; see [\textit{D. Cenzer} and \textit{C. G. Jockusch jun.}, ``\(\Pi^0_1\) classes -- structure and applications'', Contemp. Math. 257, 39--59 (2000; Zbl 0962.03040)]. The exposition includes a clear and concise discussion of genercity and randomness, relating these concepts to the main result.
reviewed by: Jeffry L. Hirst
Mathematics Subject Classification ID: 03D28
Mathematics Subject Classification ID: 03B30
Mathematics Subject Classification ID: 03F35
Mathematics Subject Classification ID: 03F60
zbMATH DE Number: 5947122
zbMATH Keywords: computability theory
zbMATH Keywords: reverse mathematics
zbMATH Keywords: measure theory
zbMATH Keywords: randomness
zbMATH Keywords: Baire category theorem
zbMATH Keywords: forcing
zbMATH Keywords: genericity
zbMATH Keywords: WKL
zbMATH Keywords: WWKL
zbMATH Keywords: \(\omega\)-model
zbMATH Keywords: weak König's lemma
zbMATH Keywords: Turing degrees
MaRDI profile type: Publication
full work available at URL: j.apal.2010.07.004
OpenAlex ID: W2027737305
cites work: The Baire category theorem in weak subsystems of second-order arithmetic
cites work: Information-theoretic characterizations of recursive infinite strings
cites work: Q4513963
cites work: Q4111536
cites work: Using random sets as oracles
cites work: Lowness notions, measure and domination
cites work: Turing incomparability in Scott sets
cites work: On relative randomness
cites work: Q3329452
cites work: Q3611832
cites work: Q5494235
cites work: Lowness properties and randomness
cites work: Degrees of Unsolvability. (AM-55)
cites work: A unified approach to the definition of random sequences
cites work: Q4220572
cites work: Q3819052
cites work: Measure theory and weak König's lemma
DOI: 10.1016/J.APAL.2010.07.004
Recommended article: Turing incomparability in Scott sets
Recommended article: Computable Measure Theory and Algorithmic Randomness
Recommended article: Computably enumerable Turing degrees and the meet property
Recommended article: Q4281689
Recommended article: A Simple and Unified Method of Proving Indistinguishability
Recommended article: ON ANALOGUES OF THE CHURCH–TURING THESIS IN ALGORITHMIC RANDOMNESS
Recommended article: A note on computational indistinguishability
Recommended article: A computability theoretic equivalent to Vaught's conjecture
Recommended article: Q5711939
description: scientific article; zbMATH DE number 5947122