Inherent enumerability of strong jump-traceability

DOI10.1090/S0002-9947-2014-06089-3MaRDI QIDQ5496646zbMATH OpenOpenAlexFDO

Authors Noam Greenberg, David Diamondstone, Daniel Turetsky

Publication date 2 February 2015

Published in Transactions of the American Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

computabilityDemuth randomnessstrong jump-tracebilitysuperlowness

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Other Turing degree structures (03D28) Algorithmic randomness and dimension (03D32)

Abstract: We show that every strongly jump-traceable set obeys every benign cost function. Moreover, we show that every strongly jump-traceable set is computable from a computably enumerable strongly jump-traceable set. This allows us to generalise properties of c.e. strongly jump-traceable sets to all such sets. For example, the strongly jump-traceable sets induce an ideal in the Turing degrees; the strongly jump-traceable sets are precisely those that are computable from all superlow Martin-L"{o}f random sets; the strongly jump-traceable sets are precisely those that are a base for $ext{Demuth}_{extBLR}$-randomness; and strong jump-traceability is equivalent to strong superlowness.

Recommendations

• Benign cost functions and lowness properties
• On strongly jump traceable reals
• Strong jump-traceability
• A random set which only computes strongly jump-traceable c.e. sets
• Strong jump-traceability and Demuth randomness

Cites work

• A mathematical proof of S. Shelah's theorem on the measure problem and related results
• Algorithmic Information Theory
• Algorithmic randomness and complexity.
• Benign cost functions and lowness properties
• Calibrating Randomness
• Characterizing lowness for Demuth randomness
• Characterizing the strongly jump-traceable sets via randomness
• Computability and Randomness
• Computably enumerable sets below random sets
• Computational randomness and lowness
• Computuing K-trivial sets by incomplete random sets
• Demuth randomness and computational complexity
• scientific article; zbMATH DE number 5354051 (Why is no real title available?)
• scientific article; zbMATH DE number 2063218 (Why is no real title available?)
• Information-theoretic characterizations of recursive infinite strings
• Lowness properties and approximations of the jump
• Lowness properties and randomness
• On strongly jump traceable reals
• Randomness and Computability: Open Questions
• Strong jump-traceability and Demuth randomness
• Strong jump-traceability. I: The computably enumerable case
• Strong jump-traceability. II: K-triviality
• The Degrees of Hyperimmune Sets
• Time-Bounded Kolmogorov Complexity and Solovay Functions
• Using random sets as oracles
• 𝐾-trivial degrees and the jump-traceability hierarchy

Cited in

(15)

• Computability theory. Abstracts from the workshop held January 7--13, 2018
• Pseudo-jump inversion, upper cone avoidance, and strong jump-traceability
• Strong jump-traceability. I: The computably enumerable case
• Lowness properties and approximations of the jump
• A random set which only computes strongly jump-traceable c.e. sets
• Benign cost functions and lowness properties
• Beyond strong jump traceability
• Superhighness and Strong Jump Traceability
• Traces, traceability, and lattices of traces under the set theoretic inclusion
• Characterizing the strongly jump-traceable sets via randomness
• Strong jump-traceability
• Computing from projections of random points
• Families of permutations and ideals of Turing degrees
• Martin-Löf reducibility and cost functions
• On strongly jump traceable reals

This page was built for publication: Inherent enumerability of strong jump-traceability

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