Oracle (machine de Turing)
Un article de Freepedia.
- Pour les articles homonymes, voir oracle. Image:Logo Begriffsklärung.png
| Image:Math.png | Cet article est une ébauche à compléter concernant les mathématiques, vous pouvez partager vos connaissances en le modifiant. |
Les machines de Turing avec oracle sont une variante des machines de Turing
Usage
Sous leur forme standard, elles possèdent un ruban spécial, qui est le ruban d'oracle, ainsi que trois états particuliers, <math>q_?</math>, <math>q_y</math> et <math>q_n</math>. Le ruban d'oracle est un ruban d'écriture. Pour utiliser l'oracle, la machine écrit un mot sur ce ruban, puis va dans l'état <math>q_?</math>. Selon le mot, l'oracle décide si l'état suivant sera <math>q_y</math> ou <math>q_n</math>.
Notations et complexité
On note <math>L(M^A)</math> le langage reconnu par la machine <math>M</math> avec l'oracle <math>A</math>. Noter que l'oracle est interchangeable, avec la même machine.
Les machines de Turing avec oracle permettent d'aller beaucoup plus loin dans le calcul des complexités. On note <math>X^Y</math> la complexité d'une machine de Turing appartenant à une classe de complexité <math>X</math>, munie d'un oracle que l'on pourrait décrire avec une machine appartenant à la classe <math>Y</math>.
Par exemple, <math>P^P = P</math>, puisqu'il suffit de remplacer le ruban de l'oracle par la machine correspondante, et on conserve alors la polynomialité. <math>NP \subseteq P^{NP}</math>, mais la question de l'égalité est toujours ouverte.
Théorème de Baker, Gill et Solovay
Exemple de résultats intéressants obtenus avec les oracles.
Théorème (Baker, Gill, Solovay) : <math>\exists A : P^A = NP^A</math> et <math>\exists B : P^B \neq NP^B</math>
Preuve. A écrire. Fin.
