Moser, Philippe and Stephan, Frank
(2015)
Depth, Highness and DNR Degrees.
In: FCT 2015 : 20th International Symposium on Fundamentals of Computation Theory, 1719 August 2015, Gdansk, Poland.
Abstract
A sequence is Bennett deep [5] if every recursive approximation of the
Kolmogorov complexity of its initial segments from above satisfies that the difference
between the approximation and the actual value of the Kolmogorov complexity of
the initial segments dominates every constant function. We study for different lower
bounds r of this difference between approximation and actual value of the initial segment
complexity, which properties the corresponding r(n)deep sets have. We prove
that for r(n) = εn, depth coincides with highness on the Turing degrees. For smaller
choices of r, i.e., r is any recursive order function, we show that depth implies either
highness or diagonallynonrecursiveness (DNR). In particular, for leftr.e. sets, order
depth already implies highness. As a corollary, we obtain that weaklyuseful sets are
either high or DNR. We prove that not all deep sets are high by constructing a low
orderdeep set.
Bennett's depth is defined using prefixfree Kolmogorov complexity. We show that
if one replaces prefixfree by plain Kolmogorov complexity in Bennett's depth definition,
one obtains a notion which no longer satisfies the slow growth law (which
stipulates that no shallow set truthtable computes a deep set); however, under this
notion, random sets are not deep (at the unbounded recursive order magnitude). We
improve Bennett's result that recursive sets are shallow by proving all Ktrivial sets
are shallow; our result is close to optimal.
For Bennett's depth, the magnitude of compression improvement has to be achieved
almost everywhere on the set. Bennett observed that relaxing to infinitely often is
meaningless because every recursive set is infinitely often deep. We propose an alternative
infinitely often depth notion that doesn't suffer this limitation (called i.o.
depth).We show that every hyperimmune degree contains a i.o. deep set of magnitude
εn, and construct a π01 class where every member is an i.o. deep set of magnitude
εn. We prove that every nonrecursive, nonDNR hyperimmunefree set is i.o. deep
of constant magnitude, and that every nonrecursive manyone degree contains such
a set.
Repository Staff Only(login required)

Item control page 
Downloads per month over past year