Oracle Turing machine

An oracle Turing machine is a Turing machine that is connected to an oracle . You can visualize an oracle as a black box that the Turing machine can interrogate and solve a problem in one step. The concept of oracle machine is used in theoretical computer science to hierarchies to be defined by Berechenbarkeiten and complexities and to study their properties.

By using suitable oracles, predictability can be increased or complexity reduced. For example, Turing machines with the stopping problem as an oracle can solve the stopping problem for Turing machines. Turing machines with SAT as an oracle can solve every problem from NP in polynomial time. Oracles are also used to deterministically model nondeterminism . A nondeterministic Turing machine can be represented as a family of deterministic oracle Turing machines. The host parameter, the oracle, expresses the sequence of nondeterministic decisions.

definition

Be a language above the alphabet . An oracle machine with oracle is a Turing machine with an additional input tape, the oracle band, and excellent three states: . If you write a word on the oracle ribbon and go into the state , the oracle asks : The successor state of be if applies and otherwise . Then the oracle ribbon will be deleted. ${\displaystyle A\subseteq \Sigma ^{*}}$ ${\displaystyle \!\ \Sigma }$ ${\displaystyle \!\ A}$ ${\displaystyle \!\ M}$ ${\displaystyle q_{j},~q_{n},~q_{?}}$ ${\displaystyle \!\ M}$ ${\displaystyle w\in \Sigma ^{*}}$ ${\displaystyle \!\ q_{?}}$ ${\displaystyle \!\ M}$ ${\displaystyle \!\ q_{?}}$ ${\displaystyle \!\ q_{j}}$ ${\displaystyle w\in A}$ ${\displaystyle \!\ q_{n}}$

If and are classes of languages, then denotes the class of languages accepted by the Turing machine with oracles , where and are. Typical classes are single-element classes, complexity classes such as P or NP , or the class of all recursively enumerable languages. ${\displaystyle \!\ T}$ ${\displaystyle \!\ K}$ ${\displaystyle \!\ T^{K}}$ ${\displaystyle \!\ M}$ ${\displaystyle \!\ A}$ ${\displaystyle L(M)\in T}$ ${\displaystyle A\in K}$

Examples:

• ${\displaystyle \!\ P^{SAT}}$denotes the class of languages ​​that are accepted by a deterministic, polynomial time-limited Turing machine with an oracle . ${\displaystyle \!\ SAT}$
• ${\displaystyle \!\ NP^{NP}}$denotes the class of languages ​​that are accepted from the class by a nondeterministic, polynomial time-limited Turing machine with an oracle . ${\displaystyle \!\ NP}$

These complexity classes are used, among other things, to define the polynomial time hierarchy .

properties

• For two complexity classes , and a language applies if the following conditions are met: ${\displaystyle T}$ ${\displaystyle K}$ ${\displaystyle L\in K}$ ${\displaystyle T^{K}=T^{L}}$
  1. ${\displaystyle L}$is - complete with respect to a reduction ${\displaystyle K}$ ${\displaystyle \preceq }$
  2. The underlying class of Turing machines is powerful enough to compute the reduction ${\displaystyle T}$ ${\displaystyle \preceq }$

     For example, it holds that - is complete with respect to polynomial time reduction . ${\displaystyle P^{NP}=P^{SAT}}$ ${\displaystyle SAT}$ ${\displaystyle NP}$

• Every oracle Turing machine has at least the capabilities of its Turing machine, its oracle and the complementary language of its oracle. It is therefore true , and for all classes and . The latter property results when the states and are interpreted interchanged. In particular, then ${\displaystyle T\subseteq T^{K}}$ ${\displaystyle K\subseteq T^{K}}$ ${\displaystyle coK\subseteq T^{K}}$ ${\displaystyle T}$ ${\displaystyle K}$ ${\displaystyle q_{j}}$ ${\displaystyle q_{n}}$ ${\displaystyle T^{K}=T^{coK}}$

• It applies and , as to question the Turing machine instead of the oracle, the response of the oracle can calculate yourself. The statement cannot be generalized to nondeterministic complexity classes. The reason for this is the necessary property of the oracle class . For example, the hitherto unexplained relationship would follow . ${\displaystyle P^{P}=P}$ ${\displaystyle NP^{P}=NP}$ ${\displaystyle K=coK}$ ${\displaystyle K}$ ${\displaystyle NP^{NP}=NP}$ ${\displaystyle coNP=NP}$ ${\displaystyle ({\overline {SAT}}\in NP)}$

To the holding problem

Note that the oracle is not limited in any way. Languages ​​that cannot be decided can also be used as oracles. So you can use the holding problem as an oracle, for example. Such holding oracle Turing machines can obviously solve the holding problem of Turing machines (without oracles). Of course, this does not contradict the undecidability result of the halting problem, because this only means that there is no Turing machine without an oracle that solves the problem. However, the holding problem of holding oracle Turing machines cannot be solved by holding oracle Turing machines either.

The construction of ever stronger oracle Turing machines leads to the arithmetic hierarchy and the Turing degrees .

Relative predictability

As above transferred already mentioned, most theorems of computability theory on oracle Turing machines. Above all, the Smn theorem together with the resulting recursion sentences as well as the undecidability of the (oracle) halting problem. One then speaks of relative predictability (am. Engl .: relativized recursion theory ), this is also reflected in the following definitions:

Let be sets of natural numbers . ${\displaystyle A;B\subseteq \mathbb {N} }$

• The set is called calculable in if there is a Turing machine with an oracle for that calculates the characteristic function , i.e. decides . ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle \chi _{A}}$ ${\displaystyle A}$

This is by definition exactly the case when to reduce Turing lets . ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A\preceq _{T}B}$

• The set is called recursively enumerable in , if there is a Turing machine with an oracle for which calculates the partial characteristic function , i.e. enumerates it . ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle \chi _{A}^{\bot }}$ ${\displaystyle A}$

Obviously, the relative predictability implies the relative enumerability, the reverse is generally not true. However, here, too, is computable in if both and its complement are enumerable in . ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle {\bar {A}}}$ ${\displaystyle B}$

Note: Relative enumerability should not be confused with enumerable reduction . The latter is really weaker than relative enumerability and generally incomparable with the Turing reduction.

literature

• John E. Hopcroft , Jeffrey D. Ullman : Introduction to Automata Theory, Formal Languages, and Complexity Theory . 4th revised edition. Oldenbourg, Munich et al. 2000, ISBN 3-486-25495-2 .
• Christos H. Papadimitriou : Computational Complexity . Addison-Wesley, Reading MA et al. 1994, ISBN 0-201-53082-1 .

• Hartley Rogers, Jr .: Theory of Recursive Functions and Effective Computability . McGraw-Hill, Cambridge, Massachusetts 1987, ISBN 0-262-68052-1 , pp. 145-149.