  This paper concerns algorithms that give correct answers with (asymptotic)
density $1$. A dense description of a function $g : \omega \to \omega$ is a
partial function $f$ on $\omega$ such that $\left\{n : f(n) = g(n)\right\}$ 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 $\epsilon > 0$
the existence of an appropriate description that is correct on a set of lower
density of at least $1 - \epsilon$. We determine which implications hold among
these various notions of approximate computability and show that any Boolean
combination of these notions is satisfied by a c.e. set unless it is ruled out
by these implications. 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.
