Reducibilidad de enumeración

---

En la teoría de la computabilidad y la teoría de la complejidad computacional , la reducibilidad de la enumeración es un método de reducción que determina si existe algún procedimiento efectivo para determinar la enumerabilidad entre conjuntos de números naturales . Una enumeración en el contexto de la e -reducibilidad es una lista de los elementos en un conjunto particular , o colección de elementos, aunque no necesariamente ordenados o completos.

La e -reducibilidad es una forma de reducibilidad positiva , lo que significa que solo se procesa información positiva. La información positiva denota la sintaxis lógica para "y" ( ) y "o" ( ). La sintaxis para la negación , "no" ( ), no se incluye ni se utiliza.${\ estilo de visualización \ tierra, \ y}$${\ estilo de visualización \ lor, \ |}$${\ estilo de visualización \ neg}$

Según Hartley Rogers Jr. , un modelo intuitivo que se puede utilizar para explicar la e -reducibilidad es el siguiente:

Dejar conjuntos y darse. Considere un procedimiento que está determinado por un conjunto finito de instrucciones de la siguiente manera. Se inicia un cómputo . El cálculo procede algorítmicamente excepto que, de vez en cuando, se le puede solicitar al agente informático que obtenga un número entero de "entrada" y, de vez en cuando, el procedimiento produce un número entero de "salida". Cuando se solicita una entrada, cualquier número entero, o ningún entero, puede suministrarse. Suponga que cuando se suministran los miembros de , en cualquier orden como entradas, entonces el cálculo siempre finalmente produce el conjunto , en algún orden , como salidas. El orden en el que los miembros de${\displaystyle A}$${\displaystyle B}$${\displaystyle B}$${\displaystyle A}$${\displaystyle A}$aparecer puede variar ya que varía el orden de las entradas. (Permitimos repeticiones en el listado de y en el listado de .) Si tal procedimiento existe, decimos que la enumeración es reducible a . ^[1]${\displaystyle B}$${\displaystyle A}$${\displaystyle A}$${\displaystyle B}$

El concepto de e -reducibilidad fue introducido por primera vez por los resultados de John Myhill , quien concluyó que "un conjunto es muchos-uno completo si y solo si es recursivamente enumerable y su complemento es productivo". ^[2] Este resultado se extiende también a la e -reducibilidad. La e -reducibilidad 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]

En las definiciones proporcionadas a continuación, denote el conjunto de números naturales ( ) y denote los subconjuntos de . Deje minúsculas y represente números y funciones de a .${\displaystyle \omega }$${\displaystyle \mathbb {N} }$${\displaystyle A,B...}$${\displaystyle \omega }$${\displaystyle n,x...}$${\displaystyle f,g...}$${\displaystyle \omega }$${\displaystyle \omega }$

---