computability with random Oracles
David Madore
In short (a longer, more precise statement follows): is it true that
any (deterministic) function that is (almost surely) computable by a
Turing machine with a random Oracle is, in fact, computable?
Here is a rigorously formulated question. If A is a subset of N (the
set of naturals), a Turing machine with A for Oracle is a Turing
machine which is given the power, at any stage of its computation, to
ask the question "does this number belong to A?". We can then
consider the set of subsets of N which are recursive relative to the
Oracle A (meaning that their characteristic function is computable
with a Turing machine having A for Oracle); certainly A is recursive
relative to itself, and if A is recursive (in the usual sense) then
the subsets of N recursive relative to A are exactly the recursive
subsets of N in the usual sense. Now I can take A randomly (in 2^N
endowed with the product measure): I call a subset of N [almost
surely] recursive relative to a random Oracle when the probability
that it be recursive relative to A, when A is randomly chosen, is 1.
Obviously any recursive subset of N is recursive relative to a random
Oracle; my question is then: is it true that, conversely, any subset
that is recursive relative to a random Oracle recursive in the usual
sense?
Intuitively I tend to believe that the answer is "yes", because I
really can't see what computing power could be brought by a random
Oracle when the final result must be deterministic. Also, it seems
that the answer "no" would somehow endager (a moderately strong form
of) the Church-Turing thesis (since the notion of "being computable
relative to a random Oracle" is a not-too-far-fetched notion of
physical computability). But I can't imagine any way of proving that
the answer would be "yes". As a matter of fact, I'm not even sure how
I would proceed to prove that there exists *some* subset of N which is
not recursive relative to a random Oracle (the most straightforward
attempt with Fubini seems to fail).
I am also aware that random Oracles have been introduced in complexity
theory. For example, there are such landmark results as "almost
surely relative to a random Oracle A, P is not equal to NP". (This is
why I imagine my question about computability must be extremely naïve,
if anything is known about complexity.) This doesn't tell me,
however, anything about functions which are almost surely P relative
to a random Oracle, or about functions which are almost surely NP
relative to a random Oracle, or even about these two sets being
different (there is a difference in the order of the quantifiers).
In case I am wrong in believing that "computable relative to a random
Oracle" means the same as "computable", I can also ask about
"*uniformly* computable relative to a random Oracle", which is a
stronger statement, namely that there should exist a _fixed_ Turing
machine which, when given a random Oracle A, will almost surely
compute the given function.
Lastly, I can ask about generic Oracles instead of random ones: a
function is computable relative to a generic Oracle when the set of
Oracles relative to which it is not computable is meager in the Baire
sense (meaning that is contained in a countable union of nowhere dense
closed sets of 2^N).
I'll be grateful for any light on this problem.
Cheers,
--
David A. Madore
(david....@ens.fr,
http://www.eleves.ens.fr:8080/home/madore/ )
Thomas Holenstein
> My question is probably very naïve: I apologize in advance.
>
> In short (a longer, more precise statement follows): is it true that
> any (deterministic) function that is (almost surely) computable by a
> Turing machine with a random Oracle is, in fact, computable?
Let me first check that I understand your question correctly. You
assume that you have an oracle Turing machine A, such that for every
x, and a uniform randomly chosen oracle O, A^O stops, given x and
answers correctly with probability 1.
Then, you wonder if there is a Turing machine B which decides the same
language, but without an oracle.
Now, this should certainly hold: first note that if A stops for any
oracle O on input x, then the answer has to be correct. This is
because A can only make finitely long queries to the oracle, so the
probability of such an oracle cannot be 0.
On the other hand, it seems easy to find an oracle for which A stops.
Thomas
David Madore
> Let me first check that I understand your question correctly. You
> assume that you have an oracle Turing machine A, such that for every
> x, and a uniform randomly chosen oracle O, A^O stops, given x and
> answers correctly with probability 1.
No: although I did also mention this "uniform" question (and your
answer is assuredly interesting), my primary question was assuming
that for a uniform randomly chosen oracle O there exists with
probability 1 a Turing machine T such that for every x, T^O stops
given x and answers correctly. In other words, for almost every O
there exists T (etc.) and not, as you state above, there exists a T
such that for almost every O (etc.).
> Then, you wonder if there is a Turing machine B which decides the same
> language, but without an oracle.
Yes.
Here is another way of stating the question, which is perhaps clearer:
define a preorder -> ("Turing reducibility") on the set 2^N of subsets
of N (the naturals) by letting O->P when there exists a Turing machine
that computes (the characteristic function of) P given (the
characteristic function of) O as an Oracle. So recursive subsets of N
are minimal elements for this preorder: P is recursive iff {O | O->P}
is all of 2^N. Now I assume that P is such that {O | O->P} has
measure 1 and I ask whether P is, actually, recursive.
Denis Hirschfeldt
> Here is another way of stating the question, which is perhaps clearer:
> define a preorder -> ("Turing reducibility") on the set 2^N of subsets
> of N (the naturals) by letting O->P when there exists a Turing machine
> that computes (the characteristic function of) P given (the
> characteristic function of) O as an Oracle. So recursive subsets of N
> are minimal elements for this preorder: P is recursive iff {O | O->P}
> is all of 2^N. Now I assume that P is such that {O | O->P} has
> measure 1 and I ask whether P is, actually, recursive.
Yes, P must be computable (recursive) in this case. If P is not computable
then the set of all sets in which P is computable has measure 0. This is
proved in Gerald Sacks' book Degrees of Unsolvability (Annals of
Mathematical Studies 55, Princeton University Press, 1963, pp. 154-156).
The proof goes like this: Suppose that the set of all sets in which P is
computable has nonzero measure. By countable additivity, there is some
Turing machine T for which the set S of all sets O such that T computes P
with oracle O has measure m>0. Let r be a rational s.t. r/2<m<r. There is
a subset A of 2^N such that A is a finite union of basic open sets of 2^N,
the measure of A is at most r, and the measure of the intersection of A
and S is greater than r/2. For a natural number n and i = 0 or 1, let
B^n_i be the set of all finite strings F such that T(n) halts with oracle
F and gives the answer i, and let C^n_i be the subset of 2^N consisting of
all extensions of elements of B^n_i. The B^n_i are uniformly computably
enumerable, and (identifying P with its characteristic function) if P(n)=i
then the intersection of C^n_i with A has measure greater than r/2, while
the intersection of C^n_{1-i} with A has measure less than r/2. So to
compute P(n), it suffices to wait until we see the measure of the
intersection of C^n_i with A exceed r/2 for some i, which we can do
effectively, since A is a finite union of basic open sets. When this
happens, we know that P(n)=i.
Denis