Benign cost functions and lowness properties

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

Download options

PhilArchive



    Upload a copy of this work     Papers currently archived: 72,805

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Analytics

Added to PP
2013-09-30

Downloads
32 (#361,273)

6 months
2 (#258,199)

Historical graph of downloads
How can I increase my downloads?

References found in this work

Computability and Randomness.André Nies - 2008 - Oxford, England: Oxford University Press UK.
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.

View all 11 references / Add more references

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.