Una relación entre problemas de decisión (conjuntos) A y B donde A es reducible de Turing a B si existe una máquina de Turing que decide la pertenencia a A dada una oráculo para B; equivalentemente, A es computable relativamente a B.

Principio

La idea organizadora es el acceso a B como oráculo: la máquina puede formular consultas adaptativas sobre la pertenencia en B y usar las respuestas para decidir A, de modo que la computabilidad relativa permite interacción en lugar de una única traducción uniforme.

Demostración

Una demostración típica muestra que el problema de la parada H es reducible de Turing si un oráculo para cierta O responde consultas construidas que permiten la simulación; más concretamente, muchos conjuntos indecidibles se reducen a H mediante máquinas-oráculo que adaptan consultas basadas en respuestas previas.

Aplicación incorrecta

Usar el término para implicar una transformación computable única (many-one) o no permitir consultas adaptativas — afirmar reducibilidad de Turing donde solo existen reducciones no adaptativas — u omitir las restricciones de recursos implícitas en modelos concretos.

Consecuencia

Si A ≤_T B, cualquier procedimiento con oráculo para B proporciona uno para A; la relación induce grados de Turing que clasifican conjuntos por computabilidad relativa y fundamenta resultados de relativización en teoría de la computabilidad y complejidad.

Inversión

Invertir la reducción (B ≤_T A) cambia qué problema actúa como oráculo; la reducibilidad mutua de Turing produce equivalencia de Turing y grado compartido, mientras que una reducción unidireccional solo muestra la computabilidad relativa de A desde B.

Límite

Se aplica a modelos clásicos de computación con acceso a oráculo; excluye reducciones no uniformes sin límites, y surgen distinciones al imponer límites de recursos como tiempo polinómico que refinan la noción (p-reducibilidad de Turing, etc.).

Tensión semántica

La reducibilidad de Turing se sitúa entre la reducibilidad many-one (más fuerte, no adaptativa) y nociones más débiles como truth-table; también contrasta con nociones de interpretabilidad lógica porque la reducibilidad de Turing es computacional y no sintáctica o modelotécnica.

Síntesis

La reducibilidad de Turing captura la computabilidad relativa mediante acceso a oráculo: un procedimiento de decisión para A puede implementarse por una máquina que consulta de forma adaptativa un oráculo para B, generando clases de equivalencia (grados de Turing) que representan relaciones mutuas de computabilidad.