Cover Image
QR Code

BENIGN COST FUNCTIONS AND LOWNESS PROPERTIES.

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 de...

Full description

Published in:Journal of Symbolic Logic Vol. 76; no. 1; pp. 289 - 313
Main Authors: GREENBERG, NOAM, NIES, ANDRÉ
Format: Article
Published: Cambridge University Press Mar2011
Subjects:
Complex variables
Mathematical logic
Random measures
Elliptic functions
Real variables
Online Access:View this record in EBSCOhost
fields @attributes:
  recordID: 1
pdfLink:
plink: https://search.ebscohost.com/login.aspx?direct=true&db=hlh&AN=59372101&site=ehost-live
header:
  @attributes:
    shortDbName: hlh
    uiTerm: 59372101
    longDbName: Humanities International Complete
    uiTag: AN
  controlInfo:
    bkinfo:
    jinfo:
      jid:
        00224812
        3TY
      jtl: Journal of Symbolic Logic
      issn: 00224812
      maglogo: N
    pubinfo:
      dt: Mar2011
      vid: 76
      iid: 1
      pid: 15979
      pub: Cambridge University Press
    artinfo:
      ui:
        59372101
        10.2178/jsl/1294171001
      ppf: 289
      ppct: 24
      formats:
      tig:
        atl: BENIGN COST FUNCTIONS AND LOWNESS PROPERTIES.
      aug:
        au:
          GREENBERG, NOAM
          NIES, ANDRÉ
        affil:
          SCHOOL OF MATHEMATICS, STATISTICS AND COMPUTER SCIENCE, VICTORIA UNIVERSITY OF WELLINGTON, WELLINGTON, NEW ZEALAND
          DEPARTMENT OF COMPUTER SCIENCE, UNIVERSITY OF AUCKLAND, AUCKLAND, NEW ZEALAND
      su:
        Complex variables
        Mathematical logic
        Random measures
        Elliptic functions
        Real variables
      sug:
        subj:
          Complex variables
          Mathematical logic
          Random measures
          Elliptic functions
          Real variables
      ab: 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.
      pubtype: Academic Journal
      doctype: Article
      src: R
    language: English
    refInfo:
    copyright:
      @attributes:
        flag: Y
      dt:
        @attributes:
          year: 2011
    holdings:
      @attributes:
        islocal: N