##  [Réduction de Turing](/fr/node/60172) 

 Définition

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

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

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

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

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

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

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

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

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.