Reducción (teoría de la computabilidad)

En la teoría de la computabilidad , se estudian muchas relaciones de reducibilidad (también llamadas reducciones , reducibilidades y nociones de reducibilidad ). Están motivadas por la pregunta: dados conjuntos${\displaystyle A}$y${\displaystyle B}$de números naturales, ¿es posible convertir eficazmente un método para decidir la pertenencia a${\displaystyle B}$en un método para decidir la pertenencia a${\displaystyle A}$Si la respuesta a esta pregunta es afirmativa, entonces...${\displaystyle A}$Se dice que es reducible a${\displaystyle B}$.

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${\displaystyle A}$entonces${\displaystyle A}$También debe ser no computable. Esto proporciona una técnica poderosa para demostrar que muchos conjuntos no son computables.

Una relación de reducibilidad es una relación binaria en conjuntos de números naturales que es

• Reflexivo : Todo conjunto es reducible a sí mismo.
• Transitivo : Si un conjunto${\displaystyle A}$es reducible a un conjunto${\displaystyle B}$y${\displaystyle B}$es reducible a un conjunto${\displaystyle C}$entonces${\displaystyle A}$es reducible a${\displaystyle C}$.

Estas dos propiedades implican que la reducibilidad es un preorden en el conjunto potencia de los números naturales. Sin embargo, no todos los preórdenes se estudian como nociones de reducibilidad. Las nociones estudiadas en la teoría de la computabilidad tienen la propiedad informal de que${\displaystyle A}$es reducible a${\displaystyle B}$si y solo si algún procedimiento de decisión (posiblemente ineficaz) para${\displaystyle B}$puede convertirse eficazmente en un procedimiento de decisión para${\displaystyle A}$Las diferentes relaciones de reducibilidad varían en los métodos que permiten utilizar en dicho proceso de conversión.

La noción de reducibilidad más fundamental es la reducibilidad de Turing . Un conjunto${\displaystyle A}$de números naturales es Turing reducible a un conjunto${\displaystyle B}$si y solo si existe una máquina de Turing oráculo que, cuando se ejecuta con${\displaystyle B}$como su conjunto oráculo, calculará la función indicadora (función característica) de${\displaystyle A}$. De forma equivalente,${\displaystyle A}$¿Es Turing reducible a?${\displaystyle B}$si y solo si existe un algoritmo para calcular la función indicadora para${\displaystyle A}$siempre que se le proporcione al algoritmo un medio para responder correctamente a preguntas de la forma "¿Es?${\displaystyle n}$en${\displaystyle B}$?".

La reducibilidad de Turing sirve como línea divisoria para otras nociones de reducibilidad porque, según la tesis de Church-Turing , es la relación de reducibilidad más general que resulta efectiva. Las relaciones de reducibilidad que implican la reducibilidad de Turing se conocen como reducibilidades fuertes , mientras que aquellas que se derivan de la reducibilidad de Turing se denominan reducibilidades débiles. De forma equivalente, una relación de reducibilidad fuerte es aquella cuyos grados forman una relación de equivalencia más precisa que los grados de Turing, mientras que una relación de reducibilidad débil es aquella cuyos grados forman una relación de equivalencia menos precisa que la equivalencia de Turing.

Las reducibilidades fuertes incluyen

• Reducibilidad uno a uno :${\displaystyle A}$es reducible uno a uno a${\displaystyle B}$si existe una función uno a uno computable${\displaystyle f}$con${\displaystyle A(x)=B(f(x))}$a pesar de${\displaystyle x}$.
• Reducibilidad muchos a uno :${\displaystyle A}$es reducible a muchos uno${\displaystyle B}$si existe una función computable${\displaystyle f}$con${\displaystyle A(x)=B(f(x))}$a pesar de${\displaystyle x}$.
• Tabla de verdad reducible :${\displaystyle A}$¿La tabla de verdad es reducible a?${\displaystyle B}$si${\displaystyle A}$¿Es Turing reducible a?${\displaystyle B}$mediante una única máquina de Turing (oráculo) que produce una función total relativa a cada oráculo.
• Tabla de verdad débil reducible :${\displaystyle A}$es una tabla de verdad débil reducible a${\displaystyle B}$si existe una reducción de Turing de${\displaystyle B}$a${\displaystyle A}$y una función computable${\displaystyle f}$que limita el uso . Siempre que${\displaystyle A}$¿La tabla de verdad es reducible a?${\displaystyle B}$,${\displaystyle A}$También es débilmente reducible a la tabla de verdad${\displaystyle B}$, puesto que se puede construir una cota computable en el uso considerando el uso máximo sobre el árbol de todos los oráculos, que existirá si la reducción es total en todos los oráculos.
• Reducible positivo:${\displaystyle A}$es positivo reducible a${\displaystyle B}$si y solo si${\displaystyle A}$¿La tabla de verdad es reducible a?${\displaystyle B}$de manera que se pueda calcular para cada${\displaystyle x}$una fórmula que consta de átomos de la forma${\displaystyle B(0),B(1),...}$de tal manera que estos átomos se combinan mediante y y o, donde el y de${\displaystyle a}$y${\displaystyle b}$es 1 si${\displaystyle a=1}$y${\displaystyle b=1}$etcétera.
• Reducibilidad de enumeración : Similar a la reducibilidad positiva, relacionada con el procedimiento efectivo de enumerabilidad a partir de${\displaystyle A}$a${\displaystyle B}$.
• Reducible disyuntivo: Similar a reducible positivo con la restricción adicional de que solo se permiten disyunciones.
• Reducibilidad conjuntiva: Similar a la reducibilidad positiva con la restricción adicional de que solo se permiten "y".
• Reducibilidad lineal: similar a la reducibilidad positiva pero con la restricción de que todos los átomos de la forma${\displaystyle B(n)}$se combinan mediante disyunciones exclusivas . En otras palabras,${\displaystyle A}$es linealmente reducible a${\displaystyle B}$si y solo si una función computable calcula para cada${\displaystyle x}$un conjunto finito${\displaystyle F(x)}$dada como una lista explícita de números tales que${\displaystyle x\in A}$si y solo si${\displaystyle F(x)}$contiene un número impar de elementos de${\displaystyle B}$.

Muchas de estas reducibilidades fueron introducidas por Post (1944). Post buscaba un conjunto no computable , pero sí enumerable, al que el problema de la parada no pudiera reducirse mediante la función de Turing. Como no pudo construir dicho conjunto en 1944, trabajó en los problemas análogos para las diversas reducibilidades que introdujo. Estas reducibilidades han sido objeto de numerosas investigaciones y se conocen muchas relaciones entre ellas.

Aunque la reducibilidad de Turing es la reducibilidad efectiva más general, comúnmente se estudian relaciones de reducibilidad más débiles. Estas reducibilidades están relacionadas con la definibilidad relativa de conjuntos sobre la aritmética o la teoría de conjuntos . Incluyen:

• Reducibilidad aritmética : Un conjunto${\displaystyle A}$es aritmético en un conjunto${\displaystyle B}$si${\displaystyle A}$es definible sobre el modelo estándar de aritmética de Peano con un predicado adicional para${\displaystyle B}$. De forma equivalente, según el teorema de Post , A es aritmético en${\displaystyle B}$si y solo si${\displaystyle A}$¿Es Turing reducible a?${\displaystyle B^{(n)}}$, el${\displaystyle n}$el salto de Turing de${\displaystyle B}$, para algún número natural${\displaystyle n}$La jerarquía aritmética proporciona una clasificación más precisa de la reducibilidad aritmética.
• Reducibilidad hiperaritmética : Un conjunto${\displaystyle A}$es hiperaritmético en un conjunto${\displaystyle B}$si${\displaystyle A}$es${\displaystyle \Delta _ {1}^{1}}$definible (ver jerarquía analítica ) sobre el modelo estándar de aritmética de Peano con un predicado para${\displaystyle B}$. De forma equivalente,${\displaystyle A}$es hiperaritmético en${\displaystyle B}$si y solo si${\displaystyle A}$¿Es Turing reducible a?${\displaystyle B^{(\alpha )}}$, el${\displaystyle \alpha }$el salto de Turing de${\displaystyle B}$, para algunos${\displaystyle B}$- ordinal recursivo${\displaystyle \alpha }$.
• Constructibilidad relativa : Un conjunto${\displaystyle A}$es relativamente construible a partir de un conjunto${\displaystyle B}$si${\displaystyle A}$está en${\displaystyle L(B)}$, el modelo transitivo más pequeño de la teoría de conjuntos ZFC que contiene${\displaystyle B}$y todos los ordinales .

• Enciclopedia de Filosofía de Stanford: Funciones recursivas