Dense Computability, Upper Cones, and Minimal Pairs
Status: published in Computability 8
(2019)
155 - 177
Availability: journal
version and
preprint
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.
drh@math.uchicago.edu