Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-17T08:26:29.000Z Has data issue: false hasContentIssue false

Benign cost functions and lowness properties

Published online by Cambridge University Press:  12 March 2014

Noam Greenberg
Affiliation:
School of Mathematics, Statistics and Computer Science, Victoria University of Wellington, Wellington, New Zealand, E-mail: greenberg@msor.vuw.ac.nz
André Nies
Affiliation:
Department of Computer Science, University of Auckland, Auckland, New Zealand, E-mail: andre@cs.auckland.ac.nz

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.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable