Benign cost functions and lowness properties

DOI10.2178/jsl/1294171001zbMath1221.03036OpenAlexW2128325320MaRDI QIDQ3083140

André Nies, Noam Greenberg

Publication date: 18 March 2011

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

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.153.3463

zbMATH Keywords

c.e. random setsjump-traceable c.e. sets

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items (11)

COMPUTINGK-TRIVIAL SETS BY INCOMPLETE RANDOM SETS ⋮ Strong jump-traceability. II: \(K\)-triviality ⋮ STRONG JUMP-TRACEABILITY ⋮ Computing from projections of random points ⋮ Upper bounds on ideals in the computably enumerable Turing degrees ⋮ Demuth randomness and computational complexity ⋮ Computably enumerable sets below random sets ⋮ Characterizing the strongly jump-traceable sets via randomness ⋮ A random set which only computes strongly jump-traceable c.e. sets ⋮ Inherent enumerability of strong jump-traceability ⋮ Reductions between types of numberings

Cites Work

• Unnamed Item
• Unnamed Item
• On strongly jump traceable reals
• Strong jump-traceability. I: The computably enumerable case
• Lowness properties and approximations of the jump
• Lowness properties and randomness
• Computational randomness and lowness
• Randomness and Computability: Open Questions
• Promptness does not imply superlow cuppability
• Lowness for the class of random sets
• Almost everywhere domination and superhighness
• Mass problems and almost everywhere domination
• Using random sets as oracles

This page was built for publication: Benign cost functions and lowness properties