Is a TM with oracle also a TM?

Question

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.

Answer 1

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$.