Oracle (machine de Turing)

Oracle (machine de Turing)
Page d'aide sur l'homonymie Pour les articles homonymes, voir Oracle et Turing (homonymie).

En théorie de la complexité ou de la calculabilité, les machines de Turing avec oracle sont une variante des machines de Turing. On peut les voir comme une machine de Turing disposant d'une boîte noire, l'oracle, capable de résoudre un problème de décision en une seule opération. Ce problème peut être de n'importe quelle complexité.

Sommaire

Approche intuitive

Une machine de Turing avec oracle se fait aider par un oracle. L'oracle peut être vu comme un 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 une instance de ce 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.

Les oracles sont des outils purement théoriques, puisque ce modèle évite soigneusement de soulever la question de leur fonctionnement.

Définition

Soit A un langage. Une machine de Turing avec oracle A est une machine de Turing dotée d'un ruban spécial, le ruban d'oracle, et de trois états particuliers, q?, qy et qn. Pour consulter l'oracle, la machine écrit un mot sur ce ruban, puis entre dans l'état q?. L'oracle décide alors en une étape de calcul si l'état suivant est qy ou qn, selon que ce mot fait partie ou non du langage A.

La machine peut consulter plusieurs fois l'oracle. On remarque qu'une même machine peut fonctionner avec différents oracles ; le langage reconnu sera alors a priori différent.

Classes de complexité avec oracles

On note L(MA) le langage reconnu par la machine M avec l'oracle A, et AB, où A est une classe de complexité et B un langage, la classe des langages reconnus par un algorithme de classe A avec comme oracle le langage B.

On note encore AB, où cette fois-ci A et B sont deux classes de complexité, la classe des langages reconnus par un algorithme de classe A avec un oracle appartenant à la classe B. Il est prouvé que si B est un langage complet dans la classe C, alors AB = AC. Par exemple, PSAT est la classe des problèmes solubles en temps polynomial avec comme oracle le langage SAT. Comme SAT est NP-complet, PSAT = PNP.

Concernant les classes de complexité classiques, l'on a : PP = P, puisque pour transformer une machine de Turing polynomiale avec oracle polynomial en simple machine polynomiale, il suffit de remplacer le ruban de l'oracle par la machine correspondant au langage oracle; on vérifie aisément que la polynomialité est préservée. On sait aussi que NP \subseteq  P^{NP}, mais la question de l'égalité est ouverte (voir l'article hierarchie polynomiale).

Les oracles ont été utilisés pour étudier la question de savoir si P=NP :

Théorème (Baker, Gill, Solovay, 1975) : \exists A : P^A = NP^A et \exists B : P^B \neq NP^B

L'existence du langage A est assez facile à établir : il suffit de prendre un oracle assez puissant pour que la différence de puissance de calcul entre P et NP soit gommée. En fait, tout langage PSPACE-complet convient. En revanche, l'existence du langage B est remarquable. Elle ne permet cependant pas de trancher au sujet de savoir si P = NP : on peut imaginer que les modèles de calcul de la machine de Turing déterministe et non déterministe ont même puissance en temps polynomial, mais que l'un tire mieux parti de l'oracle B que l'autre.

Il est aussi possible de trouver un langage \ I tel que la propriété PI = NPI soit indécidable.

Bibliographie

  • C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. Section 14.3: Oracles, p. 339 – 343.

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Oracle (machine de Turing) de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать курсовую

Regardez d'autres dictionnaires:

  • Oracle (machine de turing) — Pour les articles homonymes, voir Oracle et Turing (homonymie). En théorie de la complexité ou de la calculabilité, les machines de Turing avec oracle sont une variante des machines de Turing. On peut les voir comme une machine de Turing… …   Wikipédia en Français

  • Machine De Turing — Pour les articles homonymes, voir Turing (homonymie). Une machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur et sa mémoire, créé par Alan Turing en vue de donner une définition précise …   Wikipédia en Français

  • Machine de turing — Pour les articles homonymes, voir Turing (homonymie). Une machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur et sa mémoire, créé par Alan Turing en vue de donner une définition précise …   Wikipédia en Français

  • Oracle machine — In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision… …   Wikipedia

  • Machine de Turing — Pour les articles homonymes, voir Turing (homonymie). Une machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur et sa mémoire, créé par Alan Turing en vue de donner une définition précise …   Wikipédia en Français

  • Turing — (homonymie) Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Alan Mathison Turing était un mathématicien et informaticien anglais, considéré comme l « inventeur » de l ordinateur. Son nom est… …   Wikipédia en Français

  • Turing (homonymie) — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Alan Mathison Turing était un mathématicien et informaticien anglais, considéré comme l « inventeur » de l ordinateur. Son nom est fréquemment… …   Wikipédia en Français

  • Turing reduction — In computability theory, a Turing reduction from a problem A to a problem B, named after Alan Turing, is a reduction which solves A, assuming B is already known (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to …   Wikipedia

  • Turing machine — For the test of artificial intelligence, see Turing test. For the instrumental rock band, see Turing Machine (band). Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine… …   Wikipedia

  • Turing completeness — For the usage of this term in the theory of relative computability by oracle machines, see Turing reduction. In computability theory, a system of data manipulation rules (such as an instruction set, a programming language, or a cellular… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”