## [Reducción de Turing](/es/node/60172) Definición 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 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 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 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 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 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 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 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 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.