Une relation entre problèmes de décision (ensembles) A et B telle que A est réductible de Turing à B s'il existe une machine de Turing qui décide l'appartenance à A donnée en oracle pour B ; équivalemment, A est calculable relativement à B.

Principe

L'idée organisatrice est l'accès à B comme oracle : la machine peut poser des requêtes adaptatives sur l'appartenance à B et utiliser les réponses pour décider A, ainsi la calculabilité relative permet une interaction plutôt qu'une traduction uniforme unique.

Démonstration

Une démonstration standard montre que le problème d'arrêt H est réductible de Turing à l'arrêt relatif à un oracle O si un oracle pour O répond à des requêtes d'appartenance construites permettant la simulation ; plus concrètement, de nombreux ensembles indécidables se réduisent à H via des machines-oracle adaptant leurs requêtes selon les réponses précédentes.

Mauvaise application

Employer le terme pour impliquer une transformation calculable unique (many-one) ou ne pas permettre les requêtes adaptatives — prétendre à une réductibilité de Turing alors qu'il n'existe que des réductions non adaptatives — ou ignorer les limites de ressources implicites dans des modèles particuliers.

Conséquence

Si A ≤_T B, toute procédure oracle pour B fournit une procédure oracle pour A ; la relation induit des degrés de Turing qui classent les ensembles par calculabilité relative et soutient des résultats de relativisation en calculabilité et en théorie de la complexité.

Inversion

Inverser la réduction (B ≤_T A) change quel problème sert d'oracle ; la réductibilité mutuelle de Turing donne l'équivalence de Turing et un degré partagé, tandis qu'une réduction unidirectionnelle montre seulement la calculabilité relative de A à partir de B.

Limite

S'applique aux modèles classiques de calcul avec accès oracle ; exclut les réductions non uniformes de façon illimitée, et des distinctions apparaissent en imposant des contraintes de ressources comme le temps polynomial qui raffinent la notion (p-réduction de Turing, etc.).

Tension sémantique

La réductibilité de Turing se situe entre la réductibilité many-one (plus forte, non adaptative) et des notions plus faibles comme la truth-table ; elle contraste aussi avec des notions d'interprétabilité logique puisque la réductibilité de Turing est computationnelle plutôt que syntaxique ou modèle-théorique.

Synthèse

La réductibilité de Turing capture la calculabilité relative via l'accès à un oracle : une procédure de décision pour A peut être réalisée par une machine qui interroge de manière adaptative un oracle pour B, produisant des classes d'équivalence (degrés de Turing) représentant les relations de calculabilité mutuelle.