2015/05/08 by Denis R. Hirschfeldt, Carl G. Jockusch, Hirschfeldt, Denis R. +5 · 1 citation
Computer Science · Mathematics · #03D25 #03D28 #Advanced Topology and Set Theory #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1505.01901
openalex publication_date 2015/05/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 \hbox 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-Σ03. A surprising result is that if G is a Δ02 1-generic set, and A ≤\subT G with γ(A) = 1, then A is coarsely computable at density 1.