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 |
![]() ![]() ![]() ![]() |
Download options
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.
Computing K-Trivial Sets by Incomplete Random Sets.Laurent Bienvenu, Adam R. Day, Noam Greenberg, Antonín Kučera, Joseph S. Miller, André Nies & Dan Turetsky - 2014 - Bulletin of Symbolic Logic 20 (1):80-90.
Strong Jump-Traceability.Noam Greenberg & Dan Turetsky - 2018 - Bulletin of Symbolic Logic 24 (2):147-164.
Upper Bounds on Ideals in the Computably Enumerable Turing Degrees.George Barmpalias & André Nies - 2011 - Annals of Pure and Applied Logic 162 (6):465-473.
A Random Set Which Only Computes Strongly Jump-Traceable C.E. Sets.Noam Greenberg - 2011 - Journal of Symbolic Logic 76 (2):700 - 718.
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.
Jump Inversions Inside Effectively Closed Sets and Applications to Randomness.George Barmpalias, Rod Downey & Keng Meng Ng - 2011 - Journal of Symbolic Logic 76 (2):491 - 518.
Promptness Does Not Imply Superlow Cuppability.David Diamondstone - 2009 - Journal of Symbolic Logic 74 (4):1264 - 1272.
A Random Set Which Only Computes Strongly Jump-Traceable C.E. Sets.Noam Greenberg - 2011 - Journal of Symbolic Logic 76 (2):700 - 718.
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 )
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