
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 A 0 , A 1 such that γ ( A 0 ) = γ ( 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 ∈ [ 0 , 1 ] is equal to γ ( A ) for some c.e. set A if and only if r is left- Σ 3 0 . A surprising result is that if G is a Δ 2 0 1-generic set, and A ⩽ T G with γ ( A ) = 1, then A is coarsely computable at density 1.
Recursively (computably) enumerable sets and degrees, Applied Mathematics, Other Turing degree structures, Turing degrees, Numerical Analysis and Computation, Mathematics - Logic, 03D28, 03D25, 004, Asymptotic density, coarse computability, FOS: Mathematics, Logic (math.LO), Mathematics, asymptotic density
Recursively (computably) enumerable sets and degrees, Applied Mathematics, Other Turing degree structures, Turing degrees, Numerical Analysis and Computation, Mathematics - Logic, 03D28, 03D25, 004, Asymptotic density, coarse computability, FOS: Mathematics, Logic (math.LO), Mathematics, asymptotic density
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 13 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
