Affiliations: [a] Google LLC, 111 8th Ave., New York, NY 10011, USA. [email protected] | [b] Department of Mathematics, University of Chicago, 5734 S. University Ave., Chicago, IL 60637, USA. [email protected] | [c] Department of Mathematics, University of Illinois, 1409 W. Green St., Urbana, IL 61801, USA. [email protected]
Abstract: This paper concerns algorithms that give correct answers with (asymptotic) density 1. A dense description of a function g:ω→ω is a partial function f on ω such that {n:f(n)=g(n)} has density 1. We define g to be densely computable if it has a partial computable dense description f. Several previous authors have studied the stronger notions of generic computability and coarse computability, which correspond respectively to requiring in addition that g and f agree on the domain of f, and to requiring that f be total. Strengthening these two notions, call a function g effectively densely computable if it has a partial computable dense description f such that the domain of f is a computable set and f and g agree on the domain of f. We compare these notions as well as asymptotic approximations to them that require for each ε>0 the existence of an appropriate description that is correct on a set of lower density of at least 1−ε. We show that certain implications hold among these various notions of approximate computability, and that no other implications between these notions hold, in the strong sense that any Boolean combination of these notions is satisfied by a c.e. set unless it is ruled out by the implications we describe. We define reducibilities corresponding to dense and effectively dense reducibility and show that their uniform and nonuniform versions are different. We show that there are natural embeddings of the Turing degrees into the corresponding degree structures, and that these embeddings are not surjective and indeed that sufficiently random sets have quasiminimal degree. We show that nontrivial upper cones in the generic, dense, and effective dense degrees are of measure 0 and use this fact to show that there are minimal pairs in the dense degrees.
