Reducción (teoría de la recursividad)
En la teoría de la computabilidad , se estudian muchas relaciones de reducibilidad (también llamadas reducciones , reducibilidades y nociones de reducibilidad ). Están motivados por la pregunta: dados conjuntos y de números naturales, ¿es posible convertir efectivamente un método para decidir la pertenencia a un método para decidir la pertenencia a ? Si la respuesta a esta pregunta es afirmativa entonces se dice que es reducible a .
El estudio de las nociones de reducibilidad está motivado por el estudio de los problemas de decisión . Para muchas nociones de reducibilidad, si cualquier conjunto no computable es reducible a un conjunto , entonces también debe ser no computable. Esto brinda una técnica poderosa para demostrar que muchos conjuntos no son computables.
Estas dos propiedades implican que la reducibilidad es un preorden del conjunto potencia de los números naturales. Sin embargo, no todos los pedidos anticipados se estudian como nociones de reducibilidad. Las nociones estudiadas en la teoría de la computabilidad tienen la propiedad informal de que es reducible a si y solo si algún procedimiento de decisión (posiblemente no efectivo) para puede convertirse efectivamente en un procedimiento de decisión para . Las diferentes relaciones de reducibilidad varían en los métodos que permiten utilizar dicho proceso de conversión.
Toda relación de reducibilidad (de hecho, todo preorden) induce una relación de equivalencia sobre el conjunto potencia de los números naturales en la que dos conjuntos son equivalentes si y sólo si cada uno es reducible al otro. En la teoría de la computabilidad, estas clases de equivalencia se denominan grados de la relación de reducibilidad. Por ejemplo, los grados de Turing son las clases de equivalencia de conjuntos de naturales inducidos por la reducibilidad de Turing.
Los grados de cualquier relación de reducibilidad están parcialmente ordenados por la relación de la siguiente manera. Sea una relación de reducibilidad y sean y dos de sus grados. Entonces si y solo si hay un conjunto en y un conjunto en tal que . Esto es equivalente a la propiedad de que para cada conjunto en y cada conjunto en , porque dos conjuntos cualesquiera en C son equivalentes y dos conjuntos cualesquiera en son equivalentes. Es común, como se muestra aquí, usar la notación en negrita para indicar grados.
