Reducibilidad de enumeración

En la teoría de la computabilidad , la reducibilidad por enumeración (o e-reducibilidad, para abreviar) es un tipo específico de reducibilidad . En términos generales, A es reducible por enumeración a B si una enumeración de B puede convertirse algorítmicamente en una enumeración de A. En particular, si B es computacionalmente enumerable , entonces A también lo es.

En una de las posibles formalizaciones del concepto, una reducción de Turing de A a B es una máquina de Turing aumentada con una instrucción especial: "consultar al oráculo ". Esta instrucción toma un número entero x y devuelve instantáneamente si x pertenece a B. La máquina oráculo debería decidir A , posiblemente utilizando esta capacidad especial para decidir B. De manera informal, la existencia de una reducción de Turing de A a B significa que si es posible decidir B , entonces esto puede usarse para decidir A.

La reducibilidad de enumeración es una variante cuya explicación informal es que, si es posible enumerar B , entonces esto puede usarse para enumerar A. La reducción puede ser definida por una máquina de Turing con una instrucción de consulta de oráculo especial que no toma parámetros y devuelve un nuevo elemento de B o no devuelve ninguna salida. El oráculo proporciona los elementos de B en cualquier orden. Es posible que no devuelva ninguna salida para algunas consultas antes de reanudar la enumeración. La máquina debería enumerar de manera similar los miembros de A , en cualquier orden y a cualquier ritmo. ^{[ 1 ]} Las repeticiones en las enumeraciones de A y B pueden estar permitidas o no; el concepto es equivalente en ambos casos. Aunque esto podría precisarse, la definición que se da a continuación es más común por ser formalmente más simple.

La reducibilidad de enumeración es una forma de reducibilidad positiva , en el sentido de que la máquina oráculo recibe información sobre qué elementos están en B (información positiva), pero no sobre qué elementos no están en B (información negativa). De hecho, si un elemento aún no se ha listado, la máquina oráculo no puede saber si se listará más adelante o nunca.

El concepto de reducibilidad de enumeración fue introducido por primera vez por los resultados de John Myhill , que concluyeron que "un conjunto es completo muchos a uno si y solo si es recursivamente enumerable y su complemento es productivo". ^{[ 2 ]} Este resultado también se extiende a la reducibilidad de enumeración. La reducibilidad de enumeración fue posteriormente codificada formalmente por Rogers y su colaborador Richard M. Friedberg en Zeitschrift für mathematische Logik und Grundlagen der Mathematik (el predecesor de Mathematical Logic Quarterly ) en 1959. ^{[ 3 ]}

Fuente: ^{[ 4 ]}

Dejar${\displaystyle (D_{u})}$ser una numeración estándar de subconjuntos finitos de${\displaystyle \mathbb {N} }$y dejar${\displaystyle \langle \bullet ,\bullet \rangle }$ser una función de emparejamiento estándar . Un conjunto${\displaystyle A\subseteq \mathbb {N} }$¿Es la enumeración reducible a un conjunto?${\displaystyle B\subseteq \mathbb {N} }$si existe un conjunto enumerable computacionalmente${\displaystyle W}$de tal manera que para todos${\displaystyle x\in \mathbb {N} }$,

${\displaystyle x\in A\iff \exists u\ (D_{u}\subseteq B\land \langle x,D\rangle \in W)}$

Cuando A es reducible por enumeración a B , escribimos${\displaystyle A\leq _{e}B}$. La relación${\displaystyle \leq _{e}}$es un preorden . Su relación de equivalencia asociada se denota por${\displaystyle \equiv _{e}}$. ^{[ 5 ]}

• El supremo (límite superior mínimo, unión) de conjuntos${\displaystyle A}$y${\displaystyle B}$con respecto a${\displaystyle \leq _{e}}$está dado por la unión disjunta

${\displaystyle A\oplus B=\{2n:n\in A\}\cup \{2n+1:n\in B\}.}$^{[ 6 ]}

• A es Turing reducible a B si y solo si${\displaystyle A^{+}}$¿La enumeración es reducible a?${\displaystyle B^{+}}$donde el operador más se define como${\displaystyle A^{+}:=A\oplus {\overline {A}}}$. ^{[ 6 ]} De manera informal, este operador codifica la información positiva y negativa sobre A de forma positiva. Asimismo, A es computablemente enumerable con el oráculo B si y solo si A es reducible por enumeración a${\displaystyle B^{+}}$.
• Además, A es reducible por enumeración a B si y solo si, para todo X tal que B es computablemente enumerable con el oráculo X , se cumple que A también es computablemente enumerable con el oráculo X. Este es el teorema de Selman .

• reducción de Turing
• reducción de muchos a uno
• Reducción de tablas de verdad
• Jerarquía aritmética

• Introducción a la metamatemática
• "Teoría de las funciones recursivas y la computabilidad efectiva"
• Reducibilidad de enumeración y tiempo polinomial