# Is a TM with oracle also a TM?

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.

• 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". Jun 18, 2020 at 11:57
• 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!) Jun 18, 2020 at 12:11
• @MeesdeVries What is the difference between "about language/definitions" and "about mathematics"?
– Tim
Jun 18, 2020 at 12:19
• @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. Jun 18, 2020 at 13:01

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