0
$\begingroup$

From Ullman's Introduction to Automata Theory, Languages and Computation, in a TM with oracle $A$ :

Observe that if $A$ is a recursive set, then the oracle $A$ can be simulated by another Turing machine, and the set accepted by the TM with oracle $A$ is recursively enumerable.

On the other hand, if $A$ is not a recursive set and an oracle is available to supply the correct answer, then the TM with oracle $A$ may accept a set that is not recursively enumerable.

  • Does the second sentence mean that a TM with oracle being r.e. accepts a non r.e. language?

  • Is it correct that there is no automaton which may accept a non r.e. language?

    So does a TM with oracle being r.e. not exist?

  • Is a TM with oracle also a TM?

    Is a TM with oracle being r.e. not a TM? (I guess so, because the language accepted by a TM must be r.e.)

  • For example, I am trying to understand the difference between a many-one reduction and a Turing reduction.

    A many-one reduction from language $L1$ to another $L2$ is defined as an algorithm i.e. a Turing machine which ....

    A Turing reduction from language $L1$ to another $L2$ is defined as a Turing machine with oracle $L2$ and accepting $L1$. Is a Turing reduction from a language to another necessarily an algorithm i.e. a TM?

Thanks.

$\endgroup$
4
  • $\begingroup$ The oracle could for example be a tool solving the halting problem which a turing machine cannot. So, such a turing machine is in general more powerful, and I think, it is reasonable to no more call it just a "turing machine". $\endgroup$
    – Peter
    Commented Jun 18, 2020 at 11:57
  • 1
    $\begingroup$ Is your question about language/definitions or about mathematics? I think whether or not "Turing machine with an oracle" counts as a "Turing machine" depends on context. Unless explicitly considering TMs with oracles, I think the phrase "Turing Machine" almost always refers to TMs without oracles; only in specific treatments of TMs with oracles might they fall under the more general phrase "TM". (Similarly: most skew fields aren't fields!) $\endgroup$
    – Mees de Vries
    Commented Jun 18, 2020 at 12:11
  • $\begingroup$ @MeesdeVries What is the difference between "about language/definitions" and "about mathematics"? $\endgroup$
    – Tim
    Commented Jun 18, 2020 at 12:19
  • $\begingroup$ @Tim, the distinction isn't strict. "Is 0 a prime number?", or "Do rings always have neutral element for multiplication?" are questions about language/definitions. "Are there infinitely many primes?" or "Is every finite skew field a field?" are questions about mathematics. $\endgroup$
    – Mees de Vries
    Commented Jun 18, 2020 at 13:01

1 Answer 1

Reset to default
1
$\begingroup$

  1. Not in general, but in some cases yes, it can happen. As a trivial example: let $A$ be r.e. and not recursive and consider the TM that just checks whether the input is in $A$.

  2. If by automaton you mean a TM (or something with at most the computational power of a TM) then yes. I don't get the second question though. Why shouldn't it exists?

  3. I guess this more a convention issue: usually you understand from the context whether TMs are allowed to have an oracle or not. But as a rule of thumb, if I just read "TM" I think of a TM with no oracle. So if you are wondering about what are the problems that can be solved by a TM then yes, you should not consider oracles (an oracle can drastically change the computational power of a TM).

  4. The existence of a many-one reduction is a much stronger condition than just a Turing reduction. E.g. every set is Turing reducible to its complement, but this is not the case for many-one reduction. Precisely, $A\le_m B$ iff there is a computable function $f$ s.t. $x\in A$ iff $f(x)\in B$. Of course every many-one reduction induces a Turing reduction, but the converse is not true. Consider for example how to reduce a set to its complement: given $x$ you just check whether $x\in A$ and negate the answer. We are not pinning a single element $f(x)$ s.t. $x\in A$ iff $f(x)\in A^C$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .