Skip to main content
Article
Asymptotic density and the coarse computability bound
Computability
  • Dennis R. Hirschfeldt, University of Chicago
  • Carl G. Jockusch, University of Illinois at Urbana-Champaign
  • Timothy H. McNicholl, Iowa State University
  • Paul E. Schupp, University of Illinois at Urbana-Champaign
Document Type
Article
Publication Version
Accepted Manuscript
Publication Date
2-11-2016
DOI
10.3233/COM-150035
Abstract
For r is an element of [0, 1] we say that a set A subset of omega is coarsely computable at density r if there is a computable set C such that {n: C(n) = A(n)} has lower density at least r. Let gamma (A) = sup{r : A is coarsely computable at density r}. We study the interactions of these concepts with Turing reducibility. For example, we show that if r is an element of (0, 1] there are sets A(0), A(1) such that gamma(A(0)) = gamma(A(1)) = r where A(0) is coarsely computable at density r while A(1) is not coarsely computable at density r. We show that a real r is an element of [0, 1] is equal to gamma (A) for some c.e. set A if and only if r is left-Sigma(0)(3). A surprising result is that if G is a Delta(0)(2) 1-generic set, and A < = (T) G with gamma(A) = 1, then A is coarsely computable at density 1.
Comments

This is a manuscript of an article published as Hirschfeldt, Denis R., Carl G. Jockusch Jr, Timothy H. McNicholl, and Paul E. Schupp. "Asymptotic density and the coarse computability bound." Computability 5, no. 1 (2016): 13-27, doi:10.3233/COM-150035. Posted with permission.

Copyright Owner
IOS Press
Language
en
File Format
application/pdf
Citation Information
Dennis R. Hirschfeldt, Carl G. Jockusch, Timothy H. McNicholl and Paul E. Schupp. "Asymptotic density and the coarse computability bound" Computability Vol. 5 Iss. 1 (2016) p. 13 - 27
Available at: http://works.bepress.com/timothy-mcnicholl/17/