Oracle Query
You are given n programs p1 ... pn, each of which take an ASCII string as input. Each program will either output an ACCEPT signal, or a REJECT signal, or will loop forever. You are also given n strings s1 ... sn, each affiliated with a respective program. Your task is to write a meta-program that determines which of the N program-string pairs output an ACCEPT. To assist you in this task, your meta-program is allowed to query an oracle, a black box that takes a program and a string as inputs, and immediately tells you if the computation ACCEPTs, REJECTs, or loops forever. However, you can only query the oracle log n times.

The oracle is a super-Turning-Machine, which can tell you three results about the input/program immediately: ACCEPTs, REJECTs, or Loops Forever

Answer: From the forum

1. Construct the super machines C1 ... Cn, where Ci is a machine that runs all the given machine-string pairs M1 through Mn in parallel and ACCEPTs only if exactly at least i of those machines accept.

For example: C[i] looks like
CountOfAccepts(P1(s1),P2(s2), ..., Pn(Sn)) > i == TRUE

2. Query the oracle binary search style, using the super machines as input to the oracle. Note that the strings have been hardcoded to the super machines, therefore the query to the Oracle has no input. After at most log(n) queries, we will know exactly how many of the machines accept. Call this number K.

For example: Query C[N] and C[1] first,
if Oracle(C[N], NULL) == Accepts then K=N
if Oracle(C[1], NULL) == Rejected then K=0
Else
we have Oracle(C[N], NULL) == Rejected and
Oracle(C[1], NULL) == Accepts
then we try Oracle(C[N/2]), based on the result, we will always try the middle in the
range with different status, i.e. Rejected..Accepts or Accepts..Rejected
This exactly like the binary searching

3. Finally, simulate all the machine-string pairs in parallel. Once exactly K of the machines have ACCEPTed, terminate the simulation program. Thus we have figured out which machines accept. There can be no more than K, because the oracle says so. And our simulation will not run forever, because if a machine accepts a string, it will accept after a finite amount of time.

Once we have the exactly value of K, We run the Pi(Si) in parallel and wait for the exactly K accepts. This can not be done if we do not know K because some of them will run forever.

- posted by Pop @ 3:56 PM