Conjunto enumerable computacionalmente

En la teoría de la computabilidad , un conjunto S de números naturales se denomina computablemente enumerable (ce) , recursivamente enumerable (re) , semidecidible , parcialmente decidible , listable , demostrable o reconocible por Turing si:

• Existe un algoritmo tal que el conjunto de números de entrada para los cuales el algoritmo se detiene es exactamente S.

O, equivalentemente,

• Existe un algoritmo que enumera los elementos de S. Esto significa que su resultado es una lista con todos los elementos de S : s₁ , s₂ , s₃ _, ... Si S es infinito, este algoritmo se ejecutará indefinidamente, pero cada elemento de S se devolverá después _{de un tiempo finito. Cabe destacar que estos elementos no tienen por qué estar ordenados} de una forma específica, por ejemplo, de menor a mayor.

La primera condición sugiere por qué a veces se usa el término semidecidible . Más precisamente, si un número está en el conjunto, se puede determinar ejecutando el algoritmo; pero si el número no está en el conjunto, el algoritmo puede ejecutarse indefinidamente y no devuelve ninguna información. Un conjunto que es "completamente decidible" es un conjunto computable . La segunda condición sugiere por qué se usa el término computablemente enumerable . Las abreviaturas ce y re se usan a menudo, incluso en la impresión, en lugar de la frase completa.

En la teoría de la complejidad computacional , la clase de complejidad que contiene todos los conjuntos computablemente enumerables es RE . En la teoría de la recursión, el retículo de conjuntos ce bajo inclusión se denota${\displaystyle {\mathcal {E}}}$.

Un conjunto S de números naturales se denomina computablemente enumerable si existe una función computable parcial cuyo dominio es exactamente S , lo que significa que la función está definida si y solo si su entrada es un miembro de S.

Las siguientes son propiedades equivalentes de un conjunto S de números naturales:

Semidecidibilidad :

• El conjunto S es computacionalmente enumerable. Es decir, S es el dominio (corango) de una función computable parcial.
• El conjunto S es${\displaystyle \Sigma _{1}^{0}}$(en referencia a la jerarquía aritmética ). ^{[ 1 ]}
• Existe una función parcialmente computable f tal que:$${\displaystyle f(x)={\begin{cases}1&{\mbox{si}}\ x\in S\\{\mbox{indefinido/no se detiene}}\ &{\mbox{si}}\ x\notin S\end{cases}}}$$

Enumerabilidad :

• El conjunto S es el rango de una función computable parcial.
• El conjunto S es el rango de una función computable total, o está vacío. Si S es infinito, la función puede elegirse de manera que sea inyectiva .
• El conjunto S es el rango de una función recursiva primitiva o está vacío. Incluso si S es infinito, puede ser necesaria la repetición de valores.

Diofántico :

• Existe un polinomio p con coeficientes enteros y variables${\displaystyle x,a_{1},a_{2},a_{3},\dots ,a_{9}}$abarcando los números naturales de tal manera que$${\displaystyle x\in S\Leftrightarrow \exists a_{1},a_{2},a_{3},\dots ,a_{9}\ (p(x,a_{1},a_{2},a_{3},\dots ,a_{9})=0).}$$(El número de variables ligadas en esta definición es el mejor conocido hasta ahora; es posible que se pueda utilizar un número menor para definir todos los conjuntos diofánticos).
• Existe un polinomio de los números enteros a los números enteros tal que el conjunto S contiene exactamente los números no negativos en su rango.

La equivalencia entre semidecidibilidad y enumerabilidad se puede obtener mediante la técnica de cola de milano .

Las caracterizaciones diofánticas de un conjunto enumerable computable, si bien no son tan directas ni intuitivas como las primeras definiciones, fueron halladas por Yuri Matiyasevich como parte de la solución negativa al Décimo Problema de Hilbert . Los conjuntos diofánticos son anteriores a la teoría de la recursión y, por lo tanto, históricamente constituyen la primera forma de describir estos conjuntos (aunque esta equivalencia solo se señaló más de tres décadas después de la introducción de los conjuntos enumerables computables). ^{[ 2 ]}

• Todo conjunto computable es enumerable computablemente, pero no es cierto que todo conjunto enumerable computable sea computable. Para los conjuntos computables, el algoritmo también debe indicar si una entrada no pertenece al conjunto; esto no se requiere para los conjuntos enumerables computablemente.
• Un lenguaje recursivamente enumerable es un subconjunto computacionalmente enumerable de un lenguaje formal .
• El conjunto de todas las proposiciones demostrables en un sistema axiomático presentado de manera efectiva es un conjunto computacionalmente enumerable.
• El teorema de Matiyasevich afirma que todo conjunto computacionalmente enumerable es un conjunto diofántico (lo contrario es trivialmente cierto).
• Los conjuntos simples son enumerables de forma computable, pero no computables.
• Los conjuntos creativos son enumerables de forma computable, pero no computables.
• Ningún conjunto productivo es computacionalmente enumerable.
• Dado un número de Gödel${\displaystyle \phi }$de las funciones computables, el conjunto${\displaystyle \{\langle i,x\rangle \mid \phi _{i}(x)\downarrow \}}$(dónde${\displaystyle \langle i,x\rangle }$es la función de emparejamiento de Cantor y${\displaystyle \phi _{i}(x)\downarrow }$indica${\displaystyle \phi _{i}(x)}$está definido) es computacionalmente enumerable (cf. imagen para un x fijo ). Este conjunto codifica el problema de la parada, ya que describe los parámetros de entrada para los cuales se detiene cada máquina de Turing .
• Dado un número de Gödel${\displaystyle \phi }$de las funciones computables, el conjunto${\displaystyle \{\left\langle x,y,z\right\rangle \mid \phi _{x}(y)=z\}}$es computacionalmente enumerable. Este conjunto codifica el problema de decidir el valor de una función.
• Dada una función parcial f de los números naturales en los números naturales, f es una función computable parcial si y solo si la gráfica de f , es decir, el conjunto de todos los pares${\displaystyle \langle x,f(x)\rangle }$tal que f ( x ) esté definida, es computablemente enumerable.

Si A y B son conjuntos enumerables computacionalmente, entonces A ∩ B , A ∪ B y A × B (donde el par ordenado de números naturales se asigna a un único número natural mediante la función de emparejamiento de Cantor ) son conjuntos enumerables computacionalmente. La preimagen de un conjunto enumerable computacionalmente bajo una función parcialmente computable es un conjunto enumerable computacionalmente.

Un conjunto${\displaystyle T}$se denomina co-computable-enumerable o co-ce si su complemento${\displaystyle \mathbb {N} \setminus T}$es computablemente enumerable. Equivalentemente, un conjunto es co-re si y solo si está en el nivel${\displaystyle \Pi _{1}^{0}}$de la jerarquía aritmética. La clase de complejidad de conjuntos co-computable-enumerables se denota co-RE.

Un conjunto A es computable si y solo si tanto A como el complemento de A son computablemente enumerables.

Algunos pares de conjuntos computacionalmente enumerables son efectivamente separables y otros no.

El conjunto de todos los subconjuntos recursivamente enumerables de los números naturales puede convertirse en un poset bajo la inclusión de conjuntos ; este poset es un retículo . ^{[ 3 ]} Se sabe que la teoría de este retículo es un problema indecidible . ^{[ 3 ]} De manera similar, el conjunto de todos los espacios vectoriales computacionalmente enumerables también forma un retículo. ^{[ 4 ]} De hecho, se puede generalizar aún más esto al retículo L(Q) , que se define como compuesto por todos los filtros recursivamente enumerables , donde Q es algún álgebra booleana libre sin átomos . ^{[ 5 ]} Estos retículos están estrechamente ligados al estudio de las clases Pi-0-1 recursivamente enumerables . ^{[ 5 ]}

Según la tesis de Church-Turing , cualquier función efectivamente calculable es calculable por una máquina de Turing , y por lo tanto, un conjunto S es computacionalmente enumerable si y solo si existe algún algoritmo que produce una enumeración de S. Sin embargo, esto no puede tomarse como una definición formal, ya que la tesis de Church-Turing es una conjetura informal más que un axioma formal. ^{[ 8 ]}

En los textos contemporáneos, es común definir un conjunto enumerable computable como el dominio de una función parcial, en lugar del rango de una función computable total. Esta elección se justifica porque, en teorías de recursión generalizadas, como la teoría de la α-recursión , la definición correspondiente a los dominios resulta más natural. Otros textos utilizan la definición en términos de enumeraciones, lo cual es equivalente para conjuntos enumerables computablemente.

• RE (complejidad)
• Lenguaje recursivamente enumerable
• Jerarquía aritmética

• Rogers, H. La teoría de las funciones recursivas y la computabilidad efectiva , MIT Press . ISBN 0-262-68052-1ISBN​ 0-07-053522-1.
• Soare, R. Conjuntos y grados recursivamente enumerables. Perspectivas en lógica matemática. Springer-Verlag , Berlín, 1987. ISBN 3-540-15299-7.
• Soare, Robert I. Conjuntos y grados recursivamente enumerables. Bull. Amer. Math. Soc. 84 (1978), n.º 6, 1149–1181.