Conjunto computablemente enumerable

Concepto de lógica matemática

En la teoría de la computabilidad , un conjunto S de números naturales se llama 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 se detiene el algoritmo es exactamente S.

O equivalente,

• Existe un algoritmo que enumera los miembros de S. Eso significa que su salida es simplemente una lista de todos los miembros de S : s ₁ , s ₂ , s ₃ , .... Si S es infinito, este algoritmo se ejecutará para siempre.

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 ejecutando el algoritmo, pero si el número no está en el conjunto, el algoritmo se ejecuta para siempre 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 enumerable computable . Las abreviaturas ce y re se utilizan a menudo, incluso impresas, en lugar de la frase completa.

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

Definicion formal

Un conjunto S de números naturales se llama computablemente enumerable si hay una función computable parcial cuyo dominio es exactamente S , lo que significa que la función se define si y sólo si su entrada es 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 computable parcial 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, se puede elegir que la función sea 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 los números naturales tales que
  $${\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).}$$
  (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).
• Existe un polinomio de números enteros a 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 encaje .

Las caracterizaciones diofánticas de un conjunto computable enumerable, aunque 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 recursividad y, por lo tanto, son históricamente la primera forma de describir estos conjuntos (aunque esta equivalencia sólo se observó más de tres décadas después de la introducción de los conjuntos enumerables computablemente).

Ejemplos

• Todo conjunto computable es computable enumerable, pero no es cierto que todo conjunto computable enumerable sea computable. Para conjuntos computables, el algoritmo también debe indicar si una entrada no está en el conjunto; esto no es un requisito para conjuntos computablemente enumerables.
• Un lenguaje recursivamente enumerable es un subconjunto computable enumerable de un lenguaje formal .
• El conjunto de todas las oraciones demostrables en un sistema axiomático presentado efectivamente es un conjunto computable enumerable.
• El teorema de Matiyasevich establece que todo conjunto computable enumerable es un conjunto diofántico (lo contrario es trivialmente cierto).
• Los conjuntos simples son computablemente enumerables pero no computables.
• Los conjuntos creativos son computablemente 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 está la función de emparejamiento de Cantor e indica que está definida) es computablemente enumerable (ver imagen para una x fija ). Este conjunto codifica el problema de detención ya que describe los parámetros de entrada por 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 a los números naturales, f es una función computable parcial si y sólo si la gráfica 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 computable enumerable bajo una función computable parcial es un conjunto computable enumerable.

Un conjunto se llama co-computable-enumerable o co-ce si su complemento es computablemente enumerable. De manera equivalente, un conjunto es núcleo si y sólo si está en el nivel de la jerarquía aritmética. La clase de complejidad de conjuntos co-computables-numerables se denomina 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 mediante una máquina de Turing y, por tanto, un conjunto S es computablemente enumerable si y sólo 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 más que un axioma formal.

La definición de un conjunto computable 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 recursividad generalizada, como la teoría de la recursividad α , se ha descubierto que la definición correspondiente a los dominios es más natural. Otros textos utilizan la definición en términos de enumeraciones, que es equivalente para conjuntos computablemente enumerables.

Ver 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ítmica. Medios de ciencia y negocios de Springer. pag. 23.ISBN​ 978-0-387-68441-3.

• Rogers, H. La teoría de las funciones recursivas y la computabilidad efectiva , MIT Press . ISBN 0-262-68052-1 ; ISBN 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. Toro. América. Matemáticas. Soc. 84 (1978), núm. 6, 1149-1181.