|Abstract of Paper|
On the Autoreducibility of Random Sequences
by Todd Ebert and Heribert Vollmer
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$.