Asymptotic density and the coarse computability bound

Article type: Research Article

Authors: Hirschfeldt, Denis R.^a | Jockusch Jr., Carl G.^b | McNicholl, Timothy H.^c | Schupp, Paul E.^d

Affiliations: [a] Department of Mathematics, University of Chicago, USA. drh@math.uchicago.edu | [b] Department of Mathematics, University of Illinois at Urbana-Champaign, USA. jockusch@math.uiuc.edu | [c] Department of Mathematics, Iowa State University, USA. mcnichol@iastate.edu | [d] Department of Mathematics, University of Illinois at Urbana-Champaign, USA. schupp@illinois.edu

Abstract: For r∈[0,1] we say that a set A⊆ω 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 γ(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∈(0,1] there are sets A0, A1 such that γ(A0)=γ(A1)=r where A0 is coarsely computable at density r while A1 is not coarsely computable at density r. We show that a real r∈[0,1] is equal to γ(A) for some c.e. set A if and only if r is left-Σ30. A surprising result is that if G is a Δ20 1-generic set, and A⩽TG with γ(A)=1, then A is coarsely computable at density 1.

Keywords: Asymptotic density, coarse computability, Turing degrees

DOI: 10.3233/COM-150035

Journal: Computability, vol. 5, no. 1, pp. 13-27, 2016