Oracle (machine de Turing)

Page d'aide sur l'homonymie Pour les articles homonymes, voir Oracle et Turing.
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 [1].

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 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.