Exact pairs for the ideal of the K-trivial sequences in the Turing degrees

DOI10.1017/JSL.2014.37MaRDI QIDQ2933669zbMATH OpenOpenAlexFDO

Authors George Barmpalias, Rodney G. Downey

Publication date 5 December 2014

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/jsl.2014.37

zbMATH Keywords

Kolmogorov complexityTuring degreescomputably enumerable\(K\)-trivial setsexact pairs

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Recursively (computably) enumerable sets and degrees (03D25)

Recommendations

• A minimal pair of 𝐾-degrees
• 𝐾-trivial degrees and the jump-traceability hierarchy
• K-Triviality of Closed Sets and Continuous Functions
• Low upper bounds in the Turing degrees revisited
• On the number of infinite sequences with trivial initial segment complexity

Cites work

• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• Algorithmic randomness and complexity.

Cited in

(6)

• Martin-Löf reducibility and cost functions
• 𝐾-trivial degrees and the jump-traceability hierarchy
• Computing from projections of random points
• A minimal pair of 𝐾-degrees
• On the number of infinite sequences with trivial initial segment complexity
• Low upper bounds in the Turing degrees revisited

This page was built for publication: Exact pairs for the ideal of the \(K\)-trivial sequences in the Turing degrees

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