Author |
Topic: Oracle Queries (Read 1994 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Oracle Queries
« on: May 7th, 2003, 12:18pm » |
 Quote  Modify
|
This is actually from my computability and complexity homework this week. I'm stuck on it. If anyone sees the solution, some hints would be appreciated.
ORACLE QUERIES
Consider the language ATM = { <M,w> : M is a Turing Machine that accepts the string w }. Suppose you are given an oracle for ATM, a black box which, when queried with the input <M,w>, returns YES if M accepts w, and NO otherwise. The query is written on a special "oracle tape" of the calling Turing machine, and the output from the oracle is returned in a single step.
Now supppose you are given n pairs <M1, w1>, ... , <Mn, wn>, and you want to decide which of them belong to ATM. Obviously you could accomplish this easily by calling the oracle n times, once for each pair. Devise a scheme that solves the problem with only O(log n) calls to the oracle.
Note: The notation <M,w> denotes an encoding of the Turing machine M and the string w. This encoding is stored on the tape of a Turing Machine as input.
Some thoughts: I guess some creativity will be required in combining the machines to make a super machine which we feed into the oracle. The running time of the solution implies binary search. I'm guessing we need some ordering of the machines M1 through Mn such that when the oracle returns an ACCEPT, that means ALL the machines indexed less than some integer k accept their own strings. And when the oracle REJECTs, the binary search moves to a different pivot point. I can't come up with this ordering though ... too tricky.
|
| « Last Edit: May 7th, 2003, 12:20pm by william wu » |
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Oracle Queries
« Reply #1 on: May 7th, 2003, 1:06pm » |
Quote Modify
|
Right now, it seems like you can have more than one of <Mi, wi> as part of the ATM language.
If this is so, then there are 2n possibilities, and we have to extract exactly this much information out of the oracle.
I don't really understand Turing machines or languages, but given that there are 2n possibilites, we only have O(log n) calls, and there are n pairs to test, we have to be able to send in more than one pair at a time, and get more than one bit out at a time (but you seem to indicate only one bit at a time). Based on this, I would say that the problem likely stated that only one pair was accepted by ATM, or only one pair was rejected by ATM.
Assuming for the moment that just one of them is part of ATM, we just have to figure out a way of combining n/2 pairs into a super-pair, so that if one of the n/2 pairs is acceptable, then the oracle returns ACCEPT, and if none of them are acceptable, then the oracle returns REJECT. Then we combine the pairs like this:
Super-pair 0 = <M1, w1> + <M3, w3> + <M5, w5> + <M7, w7>...
Super-pair 1 = <M2, w2> + <M3, w3> + <M6, w6> + <M7, w7>...
etc. (just break it out binary-wise)
Putting the results of the tests together in a bit sequence gives you the index of the pair that is part of ATM.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Oracle Queries
« Reply #2 on: May 7th, 2003, 7:19pm » |
Quote Modify
|
Thanks for checking out the problem James. The problem statement is actually correct. I asked my professor about this, and he noted that the information theoretic objection would be correct if you were ONLY allowed to use the oracle to determine which pairs are accepting. However, you also have a Turing Machine at your disposal, whose only limitation is the number of times it calls the oracle. So the information theoretic objection turns out to not be a problem.
A classmate in my study group came up with a solution that I believe works; I'll post it here later if no one comes up with it.
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Oracle Queries
« Reply #3 on: May 8th, 2003, 7:09am » |
Quote Modify
|
So I guess we're getting information from the Turing Machines as well as the oracle. I thought we were passing in the Turing Machine into the oracle, not running the Turing Machine as well. The easiest way to do it seems to be n calls, one to each Turing machine: "M1, do you accept string w1?". Then don't bother calling the oracle at all ... pity I don't understand Turing machines ... or this problem 
We can only get O(log n) information from the oracle, because it can only be called O(log n) times. However, we need O(n) information (n bits, to be exact). Therefore, we must get at least O(n) information from the Turing Machines themselves. The easiest way to do this is to run them, is it not? Do we even need the oracle? Great confusion from over here ...
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Oracle Queries
« Reply #4 on: May 10th, 2003, 11:39pm » |
Quote Modify
|
OK, I will try to clarify. The problem is phrased verbatim from my problem set, but I think the phrasing could be improved.
Solving the problem does not really require a good understanding of what a Turing Machine is -- just think of a TM as a program. Given some input string, the program will either output ACCEPT or REJECT. Or it might loop forever and never output anything. A language is a fancy way of saying "a set of finite strings", and so every Turing Machines accepts some language. Finally, inputs to a Turing Machine are initially stored on a one-way infinite length tape. (Essentially the model consists of this tape, a read/write head that can move left and right, and a DFA whose transition function can depend on the current state and the tape symbol on which the read/write head rests.)
We are given as input N program-string pairs < progi, stri > , and we want to know which pairs are accepting, in that if you run progi on stri, the output will be an ACCEPT.
The problem says to "devise a scheme" that solves this problem, calling the oracle log N times. The context implies that we really want to design a Turing Machine to solve this problem* -- the bracket notation < blah > denotes an encoding of some object blah for a Turing Machine tape. So in reply to the information theoretic objection, that's what my professor meant by also having a Turing Machine ... not only can your Turing Machine query the oracle, but rather it can also run its own algorithms on the input pairs.
Why do we need an oracle at all? We could just simulate each of the Turing Machines on their respective strings and find out which ACCEPT. The problem with this is some of the programs will never halt on their strings. So you will wait forever and that doesn't fly.
In retrospect this post was pretty clumsy ... please ask more questions if it's still not making sense. I believe the following rephrasing of the problem retains most of the problem's integrity without delving into the notion of Turing Machines:
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.
Notes:
* The famous Church-Turing thesis says that every effective or mechanical method can be carried about by a Turing Machine. So we can equate the idea of a "scheme" or algorithm with a corresponding Turing Machine that implements it. It is rather amazing that a read/write head, state machine and one-way infinite tape can implement any algorithm you can think of. This thesis is not a mathematical truth of course, because the notion of "effective" method is vague. However, every model of computation that people have come up with so far has been proven to be modellable by a Turing Machine, including the lambda calculus (Lisp), Markov algorithms, and partially recursive functions. One of the most convincing arguments for the TM's worth as a computational model is the proof that random access machines (RAMs) are modellable by TMs. A random access machine is basically some assembly language with registers. Since today's computer programs can be translated into assembly, we can be convinced that a TM can even model a modern day Pentium IV PC.
Why all this fuss about modelling computation? Well, we would like to know what a computer is capable of. What kinds of problems can it solve? What are its limits? This is not just a practical question but also a philosophical one, since you would like some feel for what a computer can do. Trying to analyze a modern computer in pursuit of these goals seems pretty hopeless, because its such a complex machine with so many parts. Hence the desire for a simple model, and Turing's is wonderfully simple.
Interestingly, around the same time that computer scientists were trying to figure out what computers were capable of, mathematicians were trying to figure out what mathematics was capable of. Godel's Incompleteness Theorem and Turing's work on uncomputability separate each other by about 5 years if I recall correctly. It turns out they were actually solving the same problem.
|
| « Last Edit: May 10th, 2003, 11:52pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Oracle Queries
« Reply #5 on: May 10th, 2003, 11:52pm » |
Quote Modify
|
A solution, which I think is very clever ... maybe some of you find it obvious though ...
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.
2. Query the oracle binary search style, using the super machines as input to the oracle. Note that while the oracle also takes a string as a second input, our super machines ignore all strings -- they just simulate the Mi machines in parallel, whose strings have been hardcoded a priori. After at most log n queries, we will know exactly how many of the machines accept. Call this number K.
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.
Edit: Corrected an error. s/"exactly"/"at least". Thanks Bryan! 4:16 AM 10/19/2003
|
| « Last Edit: Oct 19th, 2003, 4:17am by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Oracle Queries
« Reply #6 on: May 11th, 2003, 1:19am » |
Quote Modify
|
Some more stuff I wanted to share: Every year there are a bunch of people who claim to devise a model of computation better than a Turing Machine (capable of solving a larger class of problems), but they all get proven wrong. I attended the American Mathematical Society conference that was held recently at SFSU, particularly the sessions on computability and complexity theory. It was an interesting mix of mathematicians, computer scientists and philosophers. There were many presentations on super-Turing models of computation. The last presenter though, was Martin Davis, an emeritus logician at Berkeley, an old guy. He attacked the super Turing people, criticizing several papers, many of the authors of which were sitting right in the audience! People were getting pretty angry ... they looked like they were going to bust of their seats and bumrush the stage. One guy claimed to have solved Hilbert's 10th problem (solutions to diophantine equations) with a Quantum Algorithm. Davis pointed out some problems in the paper, and also noted that while he didn't know much about quantum mechanics himself, he discussed the matter with a bunch of people at MIT who do know a lot about it, and they all assured him that the algorithm was bogus. Another model claimed to produce uncomputable (super-Turing) outputs, but it required uncomputable inputs. Davis noted that while these results are impressive, they're also incredibly obvious. And after one philosopher's talk on the invalidity of the Church-Turing thesis, Davis fell out of his chair. As he got back up, he said, "I found this paper disstressing, but I didn't realize that I'd even fall out of my chair!" HAHA  Sigh ... dude, it was so damn funny.
|
| « Last Edit: May 11th, 2003, 3:45pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Bryan
Guest
|
Just three quick things:
First, note that the oracle solves something which contains as a subset the Halting Problem, which is not possible for a Turing Machine. As such, it's not suprising that the oracle can do amazing things for us 
Second, I think you misphrased your solution. I believe ::the Ci machine should ACCEPT if at least i of the machines accept their string. Your way doesn't allow for binary search as after testing a machine string pair we don't know whether to increase or decrease i.::
Third, Turing Machines are actually more powerful, computationally, than a desktop PC, as a Turing Machine has an infinite tape. A desktop with infinite memory would be equivalent. Not that this goes against what you said, I just think it's cute.
// solution content hidden by wwu on 4:16 AM 10/19/2003
|
| « Last Edit: Oct 19th, 2003, 4:22am by william wu » |
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Oracle Queries
« Reply #8 on: Oct 19th, 2003, 4:21am » |
Quote Modify
|
Ah, yes ... I meant to say ::at least i.:: If the criterion is "exactly", then I end up making at most n queries to the oracle, and as you say, there's no opportunity for binary search. The post has been fixed now.
|
| « Last Edit: Oct 19th, 2003, 4:23am by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove