Abstract of Paper

On the Autoreducibility of Random Sequences
by Todd Ebert and Heribert Vollmer

Abstract:

A language $A$ is called i.o.\ autoreducible if $A$ is Turing-reducible to
itself via a machine $M$ such that, for infinitely many input words $w$, $M$
does not query its oracle $A$ about $w$. We examine the question if
algorithmically random languages in the sense of Martin-Loef are i.o.
autoreducible.  We obtain the somewhat counterintuitive result that every
algorithmically random language is polynomial-time i.o. autoreducible where
the autoreducing machine poses its queries in a ``quasi-nonadaptive'' way;
however, if in the above definition the ``infinitely many'' is replaced by
``almost all,'' then every algorithmically random language is not
autoreducible in this stronger sense.  Further results obtained give upper
and lower bounds on the number of queries of the autoreducing machine $M$
and the number of inputs $w$ for which $M$ does not query the oracle about
$w$.