Low upper bounds of ideals

DOI10.2178/JSL/1243948325MaRDI QIDQ3630577zbMATH OpenOpenAlexFDO

Authors Antonín Kučera, Theodore A. Slaman

Publication date 4 June 2009

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

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

zbMATH Keywords

K-triviallow for randomTuring degree

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Abstract: We show that there is a low T-upper bound for the class of K-trivial sets, namely those which are weak from the point of view of algorithmic randomness. This result is a special case of a more general characterization of ideals in the T-degrees below 0' for which there is a low T-upper bound.

Recommendations

• Low upper bounds in the Turing degrees revisited
• Lowness properties and randomness
• Upper bounds on ideals in the computably enumerable Turing degrees
• scientific article; zbMATH DE number 7204368
• Low upper bounds in the LR degrees

Cites work

• Algorithmic Information Theory
• Calibrating Randomness
• Class groups of integral group rings
• Classical recursion theory. Vol. II
• Interpolation and embedding in the recursively enumerable degrees
• Lowness properties and randomness
• Randomness and Computability: Open Questions
• Reducibility orderings: Theories, definability and automorphisms
• Using random sets as oracles

Cited in

(8)

• The computability, definability, and proof theory of Artinian rings
• Inductive limits of ideals
• Low upper bounds in the Turing degrees revisited
• Computuing K-trivial sets by incomplete random sets
• choice classes
• MAXIMAL TOWERS AND ULTRAFILTER BASES IN COMPUTABILITY THEORY
• Upper bounds on ideals in the computably enumerable Turing degrees
• Calculus of cost functions

This page was built for publication: Low upper bounds of ideals

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