Réduction de Turing

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.