Conjunto computablemente enumerable

Concepto de lógica matemática

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 , enumerable , demostrable o reconocible mediante el método de Turing si:

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

O, equivalentemente,

• Existe un algoritmo que enumera los miembros de S. Esto significa que su salida es una lista de todos los miembros de S : s ₁ , s ₂ , s ₃ , ... . Si S es infinito, este algoritmo se ejecutará para siempre, pero cada elemento de S se devolverá después de una cantidad finita de tiempo. Tenga en cuenta que estos elementos no tienen que estar enumerados de una manera particular, por ejemplo, del más pequeño al más grande.

La primera condición sugiere por qué a veces se utiliza el término semidecidible . Más precisamente, si un número está en el conjunto, se puede decidir esto ejecutando el algoritmo, pero si el número no está en el conjunto, el algoritmo puede ejecutarse indefinidamente y no se devuelve ninguna información. Un conjunto que es "completamente decidible" es un conjunto computable . La segunda condición sugiere por qué se utiliza computablemente enumerable . Las abreviaturas ce y re se utilizan a menudo, incluso en forma impresa, 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, la red de conjuntos incluidos se denota como . ${\displaystyle {\mathcal {E}}}$

Definición formal

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 .

Formulaciones equivalentes

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

Semidecidibilidad:

• El conjunto S es computablemente enumerable. Es decir, S es el dominio (co-rango) de una función computable parcial.
• El conjunto S es (refiriéndose a la jerarquía aritmética ). ^[1] ${\displaystyle \Sigma _{1}^{0}}$
• Existe una función parcialmente computable f tal que: $${\displaystyle f(x)={\begin{cases}1&{\mbox{if}}\ x\in S\\{\mbox{undefined/does not halt}}\ &{\mbox{if}}\ 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 vacía. Si S es infinito, la función puede elegirse como inyectiva .
• El conjunto S es el rango de una función recursiva primitiva o vacía. Incluso si S es infinito, en este caso puede ser necesaria la repetición de valores.

Diofántico:

• Hay un polinomio p con coeficientes enteros y variables x , a , b , c , d , e , f , g , h , i que abarcan todos los números naturales tales que (El número de variables ligadas en esta definición es el mejor conocido hasta ahora; podría ser que se pueda usar un número menor para definir todos los conjuntos diofánticos). $${\displaystyle x\in S\Leftrightarrow \exists a,b,c,d,e,f,g,h,i\ (p(x,a,b,c,d,e,f,g,h,i)=0).}$$
• 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 de semidecidibilidad y enumerabilidad se puede obtener mediante la técnica de ensamblado .

Las caracterizaciones diofánticas de un conjunto computablemente enumerable, si bien no son tan sencillas o intuitivas como las primeras definiciones, fueron encontradas 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 son la primera forma de describir estos conjuntos (aunque esta equivalencia solo se observó más de tres décadas después de la introducción de los conjuntos computablemente enumerables).

Ejemplos

• Todo conjunto computable es computablemente enumerable, pero no es cierto que todo conjunto computablemente enumerable sea computable. En el caso de los conjuntos computables, el algoritmo también debe indicar si una entrada no está en el conjunto; esto no es necesario en el caso de los conjuntos computablemente enumerables.
• Un lenguaje enumerable recursivamente es un subconjunto computablemente enumerable de un lenguaje formal .
• El conjunto de todas las oraciones demostrables en un sistema axiomático efectivamente presentado es un conjunto computablemente enumerable.
• El teorema de Matiyasevich establece que todo conjunto computablemente enumerable es un conjunto diofántico (lo inverso es trivialmente cierto).
• Los conjuntos simples son computacionalmente enumerables pero no computables.
• Los conjuntos creativos son computacionalmente enumerables pero no computables.
• Cualquier conjunto productivo no es computablemente enumerable.
• Dada una numeración de Gödel de las funciones computables, el conjunto (donde es la función de emparejamiento de Cantor y indica que está definido) es computablemente enumerable (véase la imagen para una x fija ). Este conjunto codifica el problema de detención , ya que describe los parámetros de entrada para los cuales se detiene cada máquina de Turing . ${\displaystyle \phi }$ ${\displaystyle \{\langle i,x\rangle \mid \phi _{i}(x)\downarrow \}}$ ${\displaystyle \langle i,x\rangle }$ ${\displaystyle \phi _{i}(x)\downarrow }$ ${\displaystyle \phi _{i}(x)}$
• Dada una numeración de Gödel de las funciones computables, el conjunto es computablemente enumerable. Este conjunto codifica el problema de decidir el valor de una función. ${\displaystyle \phi }$ ${\displaystyle \{\left\langle x,y,z\right\rangle \mid \phi _{x}(y)=z\}}$
• Dada una función parcial f de los números naturales en los números naturales, f es una función parcial computable si y sólo si el gráfico de f , es decir, el conjunto de todos los pares tales que f ( x ) está definido, es computablemente enumerable. ${\displaystyle \langle x,f(x)\rangle }$

Propiedades

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

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

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

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

Observaciones

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 computablemente enumerable si y solo si existe algún algoritmo que produzca una enumeración de S. Sin embargo, esto no puede tomarse como una definición formal, porque la tesis de Church-Turing es una conjetura informal en lugar de un axioma formal.

La definición de un conjunto computablemente enumerable como el dominio de una función parcial, en lugar del rango de una función computable total, es común en los textos contemporáneos. Esta elección está motivada por el hecho de que en las teorías de recursión generalizada, como la teoría de la α-recursión , se ha encontrado que la definición correspondiente a los dominios es más natural. Otros textos utilizan la definición en términos de enumeraciones, lo que es equivalente para los conjuntos computablemente enumerables.

Véase también

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

Referencias

1. Downey, Rodney G.; Hirschfeldt, Denis R. (29 de octubre de 2010). Aleatoriedad y complejidad algorítmicas. Springer Science & Business Media. pág. 23. ISBN 978-0-387-68441-3.

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