How can we ensure that we are continuing to make sound and valid statements about complexity classes when using oracle Turing Machines? According to my understanding (based on the definitions given in introductory textbooks on the subject) oracle Turing machines can determine the membership status of a string with respect to an oracle language in one computation step. However the oracle languages often used are provably impossible to solve in constant time (take an EXPTIME-complete oracle, for example). To me this seems like "opening the door" to contradictions and after all, anything follows from a contradiction.
$\begingroup$
$\endgroup$
4
-
2$\begingroup$ If the oracle "really" took time $T$ then that's just a factor for the runtime of the total machine. Assuming constant cost (i.e. count how often you need the oracle) makes it easier to compare oracle-using algorithms. (The question if the obtained results have any relevance in reality is one you always face and/or ignore in TCS.) $\endgroup$– RaphaelDec 7, 2014 at 16:58
-
$\begingroup$ @Raphael By "you" in the parenthetical comment do you mean complexity theorists in general or me in particular? $\endgroup$– AriDec 7, 2014 at 18:18
-
$\begingroup$ The former. Well, both, in a way. $\endgroup$– RaphaelDec 7, 2014 at 18:34
-
$\begingroup$ an advanced topic. try starting with Fortnow who agrees they are sometimes "misused" & surveys the area. the self-consistent way to see these results is sort of like a "conditional" assertion. similarly to the way that many results are proved conditionally in math based on the Riemann hypothesis etc. $\endgroup$– vznDec 7, 2014 at 18:46
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
There's a number of ways to look at this.
One is that in proofs, implication is kind of like a function, that takes as input a proof of something, and outputs a proof of something else.
We can write functions that operate on values that we don't have.
For example, let's consider the halting number $h$, which is not computable. I can write the function
$haltingPlusOne : \{h \} \rightarrow \mathbb{N}$
$haltingPlusOne(x) = x + 1$.
This function takes as input the Halting number, and returns the Halting number plus one. Clearly this is a well defined function: if we give it the right input, it gives the right output. The fact that we can't find the right input doesn't make it any less valid of a transformation.
I see proofs with oracles as similar. They're basically functions which say, give me a Turing machine that solves problem $X$, and I'll give as output a proof of some theorem.
It's also important to realize that when we say something like "There is no Turing Machine that can decide the halting problem," that is saying that, there's no TM matching the standard definition of a TM that decides the halting problem.
An oracle is basically saying "Assume we have a TM that matches the normal definition except also assuming we can solve some problem". So there's no contradiction, since we're not assuming there's a normal TM accepting the problem, we're assuming there's a special TM accepting the problem.
In a very informal analogy, think of it like this. If I can prove to you that no humans without superpowers can fly, there's no contradiction saying that there's a superhero that can fly.
These oracles are purely logical objects. We don't know how to build physical machines that emulate them, the way we can with Turing machines, but as far as we know, there's no inherent contradiction between their definitions and our basic axioms. As logical objects, these oracles do exist. We know they're not standard Turing Machines or Lambda-Calculus terms or Partial-recursive functions. The Church-Turing thesis says that there's no more powerful model, but it's not a theorem, it's just a conjecture, and is too informal to ever really be proved.
answered Dec 7, 2014 at 17:04
-
$\begingroup$ I agree with/understand your answer, but only up to a certain point: For example, I see that your haltingPlusOne function is well-defined, but don't see how we can draw any meaningful conclusions from oracles, since we could make any "if" statement of a false statement and reach any conclusion, i.e. "If $n + 1 = n$ for all natural numbers $n \geq 1$ then there is only one natural number." $\endgroup$– AriDec 7, 2014 at 18:27
-
1$\begingroup$ The thing is, the statements are not false, we just can't construct them. The key is that oracles aren't Turing machines, it doesn't mean they don't exist. $\endgroup$ Dec 7, 2014 at 20:46
-
$\begingroup$ "find the right input" $\: \mapsto \:$ "find the right output" $\;\;\;$ ? $\;\;\;\;\;\;\;$ $\endgroup$– user12859Dec 8, 2014 at 2:57
$\begingroup$
$\endgroup$
Well, I would say that it is an essential feature of oracle TM that they have access to an oracle that is hard to solve. If you can decide the oracle $A$ in constant time, then for every class $B$ you would have $B=B^A$. So why to have the oracle at all in this case?
So what is the point in using a oracle TM then? I would say it allows us mainly theoretical considerations about the (degree of) hardness of problems. The oracle can even be undecidable. In this case you can define a whole hierarchy of undecidable problems (Turing degree). Of course, if your oracle is the halting problem you cannot convert your oracle TM into a traditional TM.
The oracle TM concept also is important to define a strong form of reductions (Turing reductions).
Note that the more theoretical motivation of oracle TM can have implications outside of the oracle world. You maybe know the famous $\sf P$ vs $\sf NP$ relativizing result.
As a last remark note that in order to query the oracle you have to write the query string $w$ first on the oracle tape. Thus, you cannot decide the membership in constant time, but in time $|w|$.
