About determining whether something’s a query: A formulation of the statement we want to test is, (A) “for every (infinite) input on the oracle tape, and every ε>0, there is a T∈N such that with probability >(1−ε), the program halts in ≤T steps.”
I think this is equivalent to, (B) “For every ε>0, there is a T∈N such that, for any input on the oracle tape, the program halts within T timesteps with probability >(1−ε).”
Reason why I think this is equivalent: Clearly (B) implies (A). Suppose that (B) is false; then there is a ε>0 such that for all T>0, there is an input on the oracle tape such that the program runs for >T steps with probability ≥ε. Let f(T) be a function that returns such an oracle tape input for every T.
Now, there either must be infinitely many T such that f(T) starts with 0, or infinitely many T such that f(T) starts with 1, or both. Write down such a bit; say, 1. Now, there must be infinitely many T such that f(T) starts with 10, or such that f(T) starts with 11, or both. Iterate; this way, we obtain an infinitely long input for the oracle tape, which has the property that for every T∈N, there are arbitrarily large—T′and in particular, there’s a—T′>Tsuch that the program runs for >T′ steps with probability ≥ε. In other words, for every T, the probability that the program runs for >T steps when given this input on its oracle tape is ≥ε. This shows that (A) is false.
Thus, it’s sufficient to test whether a prospective query satisfies (B). But in T timesteps, the machine can only read the first T bits of its oracle tape and of its random input tape, so the statement “for any input on the oracle tape, the program halts within T timesteps with probability >(1−ε)” is primitive recursive. Thus, (B) is a Π2 statement, which we can test with a double halting oracle.
(warning: math above written quickly and not carefully checked)
In the other direction, suppose that φ(m,n) is a primitive recursive predicate, and consider the following probabilistic Turing machine: First, randomly choose an m∈N (placing positive probability on every natural number). Then, search exhaustively for an n∈N such that φ(m,n) is true. If you find one, halt and output 1. This machine is a query if and only if ∃m.∀n.φ(m,n). Together with the parent comment, this shows that having an oracle that tells you whether or not something is a query is equivalent to having an oracle for Π2 statements (i.e., a double halting oracle).
About determining whether something’s a query: A formulation of the statement we want to test is, (A) “for every (infinite) input on the oracle tape, and every ε>0, there is a T∈N such that with probability >(1−ε), the program halts in ≤T steps.”
I think this is equivalent to, (B) “For every ε>0, there is a T∈N such that, for any input on the oracle tape, the program halts within T timesteps with probability >(1−ε).”
Reason why I think this is equivalent: Clearly (B) implies (A). Suppose that (B) is false; then there is a ε>0 such that for all T>0, there is an input on the oracle tape such that the program runs for >T steps with probability ≥ε. Let f(T) be a function that returns such an oracle tape input for every T.
Now, there either must be infinitely many T such that f(T) starts with 0, or infinitely many T such that f(T) starts with 1, or both. Write down such a bit; say, 1. Now, there must be infinitely many T such that f(T) starts with 10, or such that f(T) starts with 11, or both. Iterate; this way, we obtain an infinitely long input for the oracle tape, which has the property that for every T∈N, there are arbitrarily large—T′and in particular, there’s a—T′>Tsuch that the program runs for >T′ steps with probability ≥ε. In other words, for every T, the probability that the program runs for >T steps when given this input on its oracle tape is ≥ε. This shows that (A) is false.
Thus, it’s sufficient to test whether a prospective query satisfies (B). But in T timesteps, the machine can only read the first T bits of its oracle tape and of its random input tape, so the statement “for any input on the oracle tape, the program halts within T timesteps with probability >(1−ε)” is primitive recursive. Thus, (B) is a Π2 statement, which we can test with a double halting oracle.
(warning: math above written quickly and not carefully checked)
In the other direction, suppose that φ(m,n) is a primitive recursive predicate, and consider the following probabilistic Turing machine: First, randomly choose an m∈N (placing positive probability on every natural number). Then, search exhaustively for an n∈N such that φ(m,n) is true. If you find one, halt and output 1. This machine is a query if and only if ∃m.∀n.φ(m,n). Together with the parent comment, this shows that having an oracle that tells you whether or not something is a query is equivalent to having an oracle for Π2 statements (i.e., a double halting oracle).