2
$\begingroup$

An oracle Turing machine (OTM) $\bar{M}$ can be denoted $M^{O}$ if it is a Turing machine (TM) $M$ with an oracle $O$. Given the oracle $O$, there exists a relation $R$ between OTMs and TMs such that $$\left( \bar{M}, M \right) \in R \Leftrightarrow \bar{M} = M^O$$

Given an OTM $\bar{M}$, how to find the TM $M$ such that $(\bar{M},M) \in R$?

Given a TM $M$, how to find the OTM $\bar{M}$ such that $(\bar{M},M) \in R$?

By using the definition of the OTM in wiki, In my opinion, $$\bar{\Gamma} = \Gamma,~\bar{q}_{start} = q_{start},~\bar{q}_{accept} = q_{accept}, \bar{q}_{reject} = q_{reject} $$ and $$Q_{0} = Q \cup\{ q_{query} , q_{response}\}$$ I have no idea about the relation between $\bar{\delta}$ and $\delta$. And what about the non-deterministic OTMs and NDTMs?

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
2
$\begingroup$

First of all the question is not very meaningful, indeed an OTM must "know" that it has such capability and use it in a proper manner. A nice way to compare $M$ and $M^O$ "syntactically" is to think that also $M$ is an oracle machine, but its oracle gives a constant (or identity) answer for every query.

Such a model makes the relation between $M$ and $\bar{M}$ trivial.

Indeed, without loss of generality, you can assume that an OTM has a special state $q_{query}$ and a special tape called the Query Tape.

Whenever $M^O$ enters the state $q_{query}$ the oracle reads the content of the Query Tape, erases it, and writes on it the answer (usually a $0$ or $1$)

But without loss of generality you can also assume that $M$ has an extra tape.

With this model the relation between $\bar{M}$ and $M$ is simply:

$$M = \bar{M}\; !!!$$

( $\delta = \bar{\delta}, \Sigma = \bar{\Sigma}, Q = \bar{Q}, Q_f = \bar{Q_f}, q_{s} = \bar{q_{s}}, \Gamma = \bar{\Gamma}$ )

in other words also $M$ is equipped with $q_{query}$ but when $M$ enters it nothing happens to the content of the extra tape.

As commented below, it should be clear (see also quicksort's answer) that an OTM could be much more powerful than a standard TM (e.g. it could solve the Halting problem), so in some (many:-) cases given an OTM $M^O$ you cannot build an equivalent TM. My answer is only an help to understand the way you can compare an OTM with a TM "syntactically" (I don't know a better term) which - I thought- was the aim of your question.

Improve this answer
$\endgroup$
2
  • $\begingroup$ @TeamBright: no, in the model I described in the answer $\bar{Q} = Q$, but for $M$ the state $q_{query}$ has no special meaning. $\endgroup$
    – Vor
    Oct 26, 2017 at 16:22
  • $\begingroup$ @TeamBright: it should be clear (see also quicksort's answer) that an OTM could be much more powerful than a standard TM (e.g. it could solve the Halting problem), so in some (many) cases given an OTM $M^O$ you cannot build an equivalent TM. My answer is only an help to understand the way you can compare an OTM with a TM "syntactically" (I don't know a better term) which - I thought- was the aim of your question. $\endgroup$
    – Vor
    Oct 26, 2017 at 16:28
2
$\begingroup$

The definition of $R$ you gave above doesn't make much sense, it looks like you're trying to build an equivalent TM that doesn't use the oracle, but the point of an oracle machine is to provide the TM with capabilities it wouldn't normally have.

For example, if $M$ is a machine with an oracle for the halting problem, then obviously there isn't in general an equivalent machine that can simulate the oracle.

If all the oracles you are using are oracles for decidable languages such as those used in complexity theory, then you can obviously simulate them (just construct a universal Turing Machine and use it to carry out the computation), but that's besides the point because it interferes with time/space complexity.

Nondeterministic oracle machines are exactly the same, the nondeterministic part is the transition function, queries to the oracle are treated as though they were a single computational step that magically happens, it is completely orthogonal to nondeterminism.

Improve this answer
$\endgroup$
3
  • $\begingroup$ The definitions always says that the OTM $\bar{M}$ is a TM $M$ with an oracle $O$, it means that there exists a rule such that we can build the $\bar{M}$ by following this rule using $M$ and $O$. I want know what the rule exactly is. ($M$ and $\bar{M}$ are not equivalent in general, but $\bar{M}$ comes from $M$.) In other words, what does the word "with" mean in the definition of OTM? $\endgroup$
    – Blanco
    Oct 26, 2017 at 9:59
  • 1
    $\begingroup$ @TeamBright At this point I'm not sure I understand what you're asking. You say that, I quote, "there must exist a rule such that we can build the $\bar{M}$ by following this rule using $M$ and $O$". What makes you think that's true? It's rather obvious that there exist oracles that cannot be computably simulated. $\endgroup$
    – quicksort
    Oct 26, 2017 at 17:35
  • $\begingroup$ When an OTM is written as $M^O$, what does it exactly mean? It is obvious that we know every details about this OTM given $M$ and $O$, otherwise this kind of denotation dose not make sense. $\endgroup$
    – Blanco
    Oct 27, 2017 at 15:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.