Characterizing the strongly jump-traceable sets via randomness

DOI10.1016/J.AIM.2012.06.005zbMATH Open1257.03068arXiv1109.6749OpenAlexW1970189970MaRDI QIDQ456804FDOQ456804

Authors: Noam Greenberg, Denis R. Hirschfeldt, André Nies 

Publication date: 16 October 2012

Published in: Advances in Mathematics (Search for Journal in Brave)

Abstract: We show that if a set $A$ is computable from every superlow 1-random set, then $A$ is strongly jump-traceable. This theorem shows that the computably enumerable (c.e.) strongly jump-traceable sets are exactly the c.e. sets computable from every superlow 1-random set. We also prove the analogous result for superhighness: a c.e. set is strongly jump-traceable if and only if it is computable from every superhigh 1-random set. Finally, we show that for each cost function $c$ with the limit condition there is a 1-random $Delt{a}_2^0$ set $Y$ such that every c.e. set $Al{e}_{T}Y$ obeys $c$. To do so, we connect cost function strength and the strength of randomness notions. This result gives a full correspondence between obedience of cost functions and being computable from $Delt{a}_2^0$ 1-random sets.

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

Recommendations

• A random set which only computes strongly jump-traceable c.e. sets
• Strong jump-traceability and Demuth randomness
• Inherent enumerability of strong jump-traceability
• Strong jump-traceability. II: \(K\)-triviality
• Strong jump-traceability. I: The computably enumerable case
• On strongly jump traceable reals
• Jump inversions inside effectively closed sets and applications to randomness
• Asymptotic density, computable traceability, and 1-randomness
• On strongly equivalent nonrandomized transition probabilities
• A random set characterization of possibility measures

zbMATH Keywords

randomnessstrongly jump-traceable setssuperlowness

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Recursively (computably) enumerable sets and degrees (03D25) Applications of computability and recursion theory (03D80) Other degrees and reducibilities in computability and recursion theory (03D30) Constructive and recursive analysis (03F60)

Cites Work

• Algorithmic randomness and complexity.
• Computability and randomness
• A Theory of Program Size Formally Identical to Information Theory
• Lowness properties and randomness
• Computability and Randomness
• ∏ 0 1 Classes and Degrees of Theories
• MASS PROBLEMS AND HYPERARITHMETICITY
• Title not available (Why is that?)
• Every sequence is reducible to a random one
• Strong jump-traceability. I: The computably enumerable case
• Lowness properties and approximations of the jump
• Benign cost functions and lowness properties
• Randomness and Computability: Open Questions
• Calibrating Randomness
• Strong jump-traceability. II: \(K\)-triviality
• Title not available (Why is that?)
• Lowness for the class of random sets
• Almost everywhere domination and superhighness
• Demuth randomness and computational complexity
• On strongly jump traceable reals
• Kolmogorov complexity and the Recursion Theorem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A random set which only computes strongly jump-traceable c.e. sets
• Interactions of computability and randomness
• Title not available (Why is that?)
• Computably enumerable sets below random sets
• Title not available (Why is that?)
• Using random sets as oracles
• Reals which compute little
• A Refinement of Lown and Highn for the R.E. Degrees
• Turing degrees and the Ershov hierarchy
• 𝐾-trivial degrees and the jump-traceability hierarchy
• Superhighness and Strong Jump Traceability
• The axiomatization of randomness
• Strong jump-traceability and Demuth randomness
• Inherent enumerability of strong jump-traceability
• Superhighness

Cited In (18)

• On strongly jump traceable reals
• Martin-Löf reducibility and cost functions
• Calculus of cost functions
• Superhighness and Strong Jump Traceability
• Computing from projections of random points
• Beyond strong jump traceability
• Strong jump-traceability. I: The computably enumerable case
• Computably enumerable sets below random sets
• On arithmetical level of the class of superhigh sets
• Benign cost functions and lowness properties
• Inherent enumerability of strong jump-traceability
• Superhighness
• Upper bounds on ideals in the computably enumerable Turing degrees
• Strong jump-traceability
• Strong jump-traceability. II: \(K\)-triviality
• Coarse reducibility and algorithmic randomness
• Demuth randomness and computational complexity
• A random set which only computes strongly jump-traceable c.e. sets

This page was built for publication: Characterizing the strongly jump-traceable sets via randomness

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