Asymptotic density and the coarse computability bound
Date
Authors
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Authors
Research Projects
Organizational Units
Journal Issue
Is Version Of
Versions
Series
Department
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.