Oracle machine

An oracle Turing machine is a Turing machine that is connected to an oracle. Pictorial you can an oracle as a black box imagine that can be questioned by the Turing machine and solves a problem in one step. The concept of oracle Turing machine is used in theoretical computer science to define hierarchies of Berechenbarkeiten and complexities and to study their properties.

By appropriate oracles can enhance the predictability and reduce complexity. For example, Turing machines can solve the halting problem as an oracle for Turing machines with the halting problem. Turing machines with SAT as an oracle to solve every problem from NP in polynomial time. Oracle also be used to model non-determinism deterministic. A non-deterministic Turing machine can in fact be represented as a family of deterministic oracle Turing machines. The family parameter, the oracle, it expresses the result of the non-deterministic choices.

Definition

Let be a language over the alphabet. An oracle Turing machine with oracle is a Turing machine with an additional input tape ( oracle tape ) and three excellent conditions. Writes a word on the oracle tape and goes over to the state, so consulted the oracle: The successor state of if is true and otherwise. Then the oracle tape is erased.

If and classes of languages ​​, then denotes the class of languages ​​accepted by Turing machine with oracle, where and are. Typical classes are singleton classes, complexity classes such as P or NP, or even the class of all recursively enumerable languages.

Examples:

  • Denotes the class of languages ​​accepted by a deterministic, polynomial- time- bounded Turing machine with oracle.
  • Denotes the class of languages ​​that are accepted by a non- deterministic polynomial time bounded Turing machine with oracle from the class.

These complexity classes are used, among other things, to define the Polynomialzeithierarchie.

Properties

  • For two complexity classes, and one language, if the following conditions are met:   is - complete with respect to a reduction
  • The underlying class of Turing machine is powerful enough to calculate the reduction

For example, is true because - complete with respect to is Polynomialzeitreduktion.

  • Each oracle Turing machine has at least the capabilities of its Turing machine, its oracle and the Komplementsprache his oracle. It is therefore important, and all classes. The latter property is obtained if one interprets the states and reversed. In particular we
  • It applies and, as the Turing machine to consult the oracle instead, the response of the oracle can calculate yourself. The statement can not be generalized to non-deterministic complexity classes. The reason is the necessary property of the oracle class. For example, it would follow from the so far unresolved relationship.

To the halting problem

Note that the oracle is in no way limited. Even languages ​​that are not decidable come as an oracle in question. So one can use, for example, the halting problem as an oracle. Such holding oracle Turing machines can obviously solve the halting problem of Turing machines (without oracle ). This is of course not in contradiction with the Unentscheidbarkeitresultat the halting problem, since this means just saying that there is no Turing machine without oracle that solves the problem. However, the halting problem of retaining oracle Turing machine not holding oracle Turing machines is solvable.

The construction of increasingly strong oracle Turing machine leads to the arithmetic hierarchy and the Turing degrees.

Nondeterministic algorithm Recursive set Arithmetical hierarchy Jeffrey Ullman Christos Papadimitriou
622638
de