Oracle (machine de Turing)
Un article de Wikipédia, l'encyclopédie libre.
Vous avez de 
 |
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
Sommaire |
[modifier] Approche intuitive
Une machine de Turing avec oracle se fait aider par un oracle. L'oracle est une sorte de dieu (il vaut mieux ne pas le considérer comme une machine) qui est capable de résoudre un certain problème de décision en un temps nul. Autrement dit, on lui pose un problème et il donne immédiatement la réponse. Ce problème peut être dans n'importe quelle classe de complexité. On peut même imaginer un oracle résolvant des problèmes qu'aucune machine de Turing ne sait résoudre, par exemple le problème de l'arrêt.
Bien entendu, les oracles sont des outils purement théoriques, aucun oracle ne pouvant être construit.
[modifier] Usage
Sous leur forme standard, elles possèdent un ruban spécial, qui est le ruban d'oracle, ainsi que trois états particuliers, q?, qy et qn. 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 q?. Selon le mot, l'oracle décide si l'état suivant sera qy ou qn.
[modifier] Notations et complexité
On note L(MA) le langage reconnu par la machine M avec l'oracle A. 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 XY la complexité d'une machine de Turing appartenant à une classe de complexité X, munie d'un oracle que l'on pourrait décrire avec une machine appartenant à la classe Y.
Par exemple, PP = P, puisqu'il suffit de remplacer le ruban de l'oracle par la machine correspondante, et on conserve alors la polynomialité. 
, mais la question de l'égalité est toujours ouverte.
[modifier] Théorème de Baker, Gill et Solovay
Théorème (Baker, Gill, Solovay) : 
et 
