See also: Oracle

The machines of Turing with oracle are an alternative of the machines of Turing

Intuitive approach

A machine of Turing with oracle is made help by an oracle. Oracle is a kind of god (it is not to better regard it as a machine) which is able to solve a certain problem of decision in a null time. In other words, one poses a problem to him and it gives the answer immediately. This problem can be in any class of complexity. One can even imagine a solving oracle of the problems which no machine of Turing can solve, for example the Problème of the stop.

Of course, oracles are purely theoretical tools, no oracle which cannot be built.

Use

In do their standard form, they have a special ribbon, which is the ribbon of oracle , like three particular states, $q\_?$, $q\_y$ and $q\_n$. The ribbon of oracle is a ribbon of writing. For to use oracle, the machine writes a word on this ribbon, then goes in the state $q\_?$. According to the word, oracle decides if the following state will be $q\_y$ or $q\_n$.

Notations and complexity

One notes $L\; (M^A)$ the language recognized by the machine $M$ with oracle $A$. To note that oracle is interchangeable, with the same machine.

The machines of Turing with oracle make it possible to go much further in the calculation of the Complexité S. One notes $X^Y$ the complexity of a machine of Turing pertaining to a class of $X$ complexity, provided with an oracle which one could describe with a machine belonging to the class $Y$.

For example, $P^P\; =\; P$, since it is enough to replace the ribbon of oracle by the corresponding machine, and one preserves the polynomiality then. $NP\; \backslash \; subseteq\; P^\; \{NP\}$, but the question of the equality is always open.

Theorem of Baker, Gill and Solovay

Theorem (Baker, Gill, Solovay): $\backslash \; exists\; a:\; P^A\; =\; NP^A$ and $\backslash \; exists\; b:\; P^B\; \backslash \; neq\; NP^B$

Random links:

Hornoy-the-borough | Play of the baccalaureat | Code figure-sounds | Kugar | Boćevica