Journal of Symbolic Logic 76 (1):289 - 312 (2011)

Abstract
We show that the class of strongly jump-traceable c.e. sets can be characterised as those which have sufficiently slow enumerations so they obey a class of well-behaved cost functions, called benign. This characterisation implies the containment of the class of strongly jump-traceable c.e. Turing degrees in a number of lowness classes, in particular the classes of the degrees which lie below incomplete random degrees, indeed all LR-hard random degrees, and all ω-c.e. random degrees. The last result implies recent results of Diamondstone's and Ng's regarding cupping with superlow c.e. degrees and thus gives a use of algorithmic randomness in the study of the c.e. Turing degrees
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2178/jsl/1294171001
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 56,949
Through your library

References found in this work BETA

Almost Everywhere Domination and Superhighness.Stephen G. Simpson - 2007 - Mathematical Logic Quarterly 53 (4):462-482.
Randomness and Computability: Open Questions.Joseph S. Miller & André Nies - 2006 - Bulletin of Symbolic Logic 12 (3):390-410.
Lowness Properties and Approximations of the Jump.Santiago Figueira, André Nies & Frank Stephan - 2008 - Annals of Pure and Applied Logic 152 (1):51-66.
Mass Problems and Almost Everywhere Domination.Stephen G. Simpson - 2007 - Mathematical Logic Quarterly 53 (4):483-492.
Promptness Does Not Imply Superlow Cuppability.David Diamondstone - 2009 - Journal of Symbolic Logic 74 (4):1264 - 1272.

View all 11 references / Add more references

Citations of this work BETA

Demuth Randomness and Computational Complexity.Antonín Kučera & André Nies - 2011 - Annals of Pure and Applied Logic 162 (7):504-513.
Strong Jump-Traceability.Noam Greenberg & Dan Turetsky - 2018 - Bulletin of Symbolic Logic 24 (2):147-164.

View all 9 citations / Add more citations

Similar books and articles

Lowness for Kurtz Randomness.Noam Greenberg & Joseph S. Miller - 2009 - Journal of Symbolic Logic 74 (2):665-678.
Strengthening Prompt Simplicity.David Diamondstone & Keng Meng Ng - 2011 - Journal of Symbolic Logic 76 (3):946 - 972.
Randomness, Lowness and Degrees.George Barmpalias, Andrew E. M. Lewis & Mariya Soskova - 2008 - Journal of Symbolic Logic 73 (2):559 - 577.
The Degrees of Conditional Problems.Su Gao - 1994 - Journal of Symbolic Logic 59 (1):166-181.
Promptness Does Not Imply Superlow Cuppability.David Diamondstone - 2009 - Journal of Symbolic Logic 74 (4):1264 - 1272.
Jump Operator and Yates Degrees.Guohua Wu - 2006 - Journal of Symbolic Logic 71 (1):252 - 264.
Degrees of Unsolvability of Continuous Functions.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (2):555 - 584.
On the Jump Classes of Noncuppable Enumeration Degrees.Charles M. Harris - 2011 - Journal of Symbolic Logic 76 (1):177 - 197.
Maximal Contiguous Degrees.Peter Cholak, Rod Downey & Stephen Walk - 2002 - Journal of Symbolic Logic 67 (1):409-437.
Kleene Index Sets and Functional M-Degrees.Jeanleah Mohrherr - 1983 - Journal of Symbolic Logic 48 (3):829-840.
Jumping to a Uniform Upper Bound.Harold T. Hodes - 1982 - Proceedings of the American Mathematical Society 85 (4):600-602.

Analytics

Added to PP index
2013-09-30

Total views
32 ( #321,901 of 2,409,924 )

Recent downloads (6 months)
4 ( #189,545 of 2,409,924 )

How can I increase my downloads?

Downloads

My notes