Reducción de Turing

En la teoría de la computabilidad , una reducción de Turing de un problema de decisión a un problema de decisión es una máquina de oráculo que decide un problema dado un oráculo para (Rogers 1967, Soare 1987). Se puede entender como un algoritmo que podría ser utilizado para resolver si tenía a su disposición una subrutina para la solución B . El concepto se puede aplicar de manera análoga a problemas funcionales . ${\ Displaystyle A}$ ${\ Displaystyle B}$ ${\ Displaystyle A}$ ${\ Displaystyle B}$ ${\ Displaystyle A}$

Si existe una reducción de Turing de a , entonces todos los algoritmos para ^[a] se pueden usar para producir un algoritmo para , insertando el algoritmo para en cada lugar donde la máquina del oráculo consulta el oráculo . Sin embargo, debido a que la máquina oracle puede consultar el oráculo una gran cantidad de veces, el algoritmo resultante puede requerir más tiempo de forma asintótica que el algoritmo o la computación de la máquina oracle . Una reducción de Turing en la que la máquina oráculo funciona en tiempo polinomial se conoce como reducción de Cook . ${\ Displaystyle A}$ ${\ Displaystyle B}$ ${\ Displaystyle B}$ ${\ Displaystyle A}$ ${\ Displaystyle B}$ ${\ Displaystyle A}$ ${\ Displaystyle B}$ ${\ Displaystyle B}$ ${\ Displaystyle A}$

La primera definición formal de computabilidad relativa, entonces llamada reducibilidad relativa, fue dada por Alan Turing en 1939 en términos de máquinas oráculo . Posteriormente, en 1943 y 1952, Stephen Kleene definió un concepto equivalente en términos de funciones recursivas . En 1944, Emil Post utilizó el término "reducibilidad de Turing" para referirse al concepto.

Dados dos conjuntos de números naturales, decimos que es Turing reducible a y escritura ${\ Displaystyle A, B \ subseteq \ mathbb {N}}$ ${\ Displaystyle A}$ ${\ Displaystyle B}$

si hay una máquina oráculo que calcula la función característica de A cuando se ejecuta con oráculo B . En este caso, también decimos que A es B -recursivo y B -computable .

Si hay una máquina de Oracle que, cuando se ejecuta con Oracle B , calcula una función parcial con el dominio A , entonces se dice que A es B - recursivamente enumerable y B - computablemente enumerable .