Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Oracle (machine de Turing)
Résumé
vignette|upright=2|Une machine de Turing avec oracle peut faire appel à une boîte noire (oracle).
En théorie de la complexité ou de la calculabilité, les machines de Turing avec oracle sont une variante des machines de Turing disposant d'une boîte noire, un oracle, capable de résoudre un problème de décision en une seule opération élémentaire. En particulier, l'oracle peut résoudre en temps constant un problème indécidable comme le problème de l'arrêt. Les machines de Turing avec oracle servent notamment à définir la hiérarchie polynomiale ou la hiérarchie arithmétique.
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 constant. Autrement dit, on donne une instance de ce problème entrée à l'oracle et il donne la réponse en un temps constant indépendant de la taille de la question. 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, c'est-à-dire un problème indécidable comme 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.
Soit L un langage. Une machine de Turing avec oracle L est une machine de Turing à plusieurs rubans avec un ruban de travail habituellement mais également dotée d'un ruban spécial, le ruban d'oracle, et de trois états particuliers, , et . Pour consulter l'oracle, la machine écrit un mot sur ce ruban, puis entre dans l'état . L'oracle décide alors en une étape de calcul si l'état suivant est ou , selon que ce mot fait partie ou non du langage L.
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.
On note où A est une classe de complexité et L un langage, la classe des langages reconnus par un algorithme de classe A avec comme oracle le langage L.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.