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