Benign cost functions and lowness properties

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

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

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 107,650

External links

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

Through your library

Similar books and articles

Randomness, Lowness and Degrees.George Barmpalias, Andrew E. M. Lewis & Mariya Soskova - 2008 - Journal of Symbolic Logic 73 (2):559 - 577.
Strengthening prompt simplicity.David Diamondstone & Keng Meng Ng - 2011 - Journal of Symbolic Logic 76 (3):946 - 972.
Computably enumerable sets below random sets.André Nies - 2012 - Annals of Pure and Applied Logic 163 (11):1596-1610.
Superhighness.Bjørn Kjos-Hanssen & Andrée Nies - 2009 - Notre Dame Journal of Formal Logic 50 (4):445-452.
Effective Domination and the Bounded Jump.Keng Meng Ng & Hongyuan Yu - 2020 - Notre Dame Journal of Formal Logic 61 (2):203-225.
Completely mitotic c.e. degrees and non-jump inversion.Evan J. Griffiths - 2005 - Annals of Pure and Applied Logic 132 (2-3):181-207.

Analytics

Added to PP
2013-09-30

Downloads
79 (#298,944)

6 months
2 (#1,494,698)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Demuth randomness and computational complexity.Antonín Kučera & André Nies - 2011 - Annals of Pure and Applied Logic 162 (7):504-513.
Reductions between types of numberings.Ian Herbert, Sanjay Jain, Steffen Lempp, Manat Mustafa & Frank Stephan - 2019 - Annals of Pure and Applied Logic 170 (12):102716.
Computably enumerable sets below random sets.André Nies - 2012 - Annals of Pure and Applied Logic 163 (11):1596-1610.

View all 9 citations / Add more citations

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 9 references / Add more references