Conjunto recursivamente enumerable

En 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 Turing-reconocible si:

Existe un algoritmo que se detiene exactamente para los números de entrada de S.

O equivalentemente,

Hay un algoritmo que enumera los miembros de S. Es decir, su salida es una lista de los elementos de S: s₁, s₂, s₃, ... . Si S es infinito, este algoritmo se ejecuta indefinidamente.

La primera condición sugiere por qué a veces se usa el término semidecidible: Si un número pertenece al conjunto, uno lo puede decidir ejecutando el algoritmo, pero si el número no está en el conjunto, el algoritmo no devuelve información. Un conjunto que es "completamente decidible" es un conjunto computable. La segunda condición sugiere por qué se usa computablemente enumerable. Las abreviaturas c.e. y r.e. se usan a menudo.

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 c.e. bajo inclusión se denota ${\mathcal {E}}$ .

Definición 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 solo si su entrada es un miembro de S.

Formulaciones equivalentes

Las siguientes propiedades de un conjunto de naturales S son equivalentes:

Semidecidibilidad :

El conjunto S es computablemente enumerable. Es decir, S es el dominio de una función computable parcial.
El conjunto S es $\Sigma _{1}^{0}$ (refiriéndose a la jerarquía aritmética).^[1]
Existe una función computable parcial f tal que: $f(x)={\begin{cases}1&{\mbox{si}}\ x\in S\\{\mbox{indefinida/no termina}}\ &{\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 vacío. Si S es infinito, la función podría ser inyectiva.
El conjunto S es la imagen (rango) de una función recursiva primitiva o vacía. Si S es infinito 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 oscilando entre los números naturales tal que $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 enteros a enteros tal que el conjunto S contiene exactamente los números no negativos en su imagen.

La equivalencia de semidecidibilidad y enumerabilidad se puede obtener mediante la técnica de dovetailing.

Yuri Matiyasevich encontró las caracterizaciones diofánticas de un conjunto computablemente enumerable como parte de la respuesta negativa al Décimo problema de Hilbert. Los conjuntos diofánticos son anteriores a la teoría de la recursividad y, por lo tanto, fueron la primera caracterización de estos conjuntos (su equivalencia se demostraría más de tres décadas luego de la introducción de conjuntos c.e.).

Una enumeración de todas las máquinas de Turing que se detienen en una entrada fija: simule todas las máquinas de Turing (enumeradas en el eje vertical) paso a paso (eje horizontal), utilizando el intercalamiento mostrado. Si una máquina termina, imprima su número. De esta forma, se imprime el número de cada máquina que termina. En el ejemplo, el algoritmo imprime "9, 13, 4, 15, 12, 18, 6, 2, 8, 0, . . ."

Ejemplos

Todo conjunto computable es computablemente enumerable, pero no es cierto que todo conjunto computablemente enumerable sea computable. Para conjuntos computables, el algoritmo también debe decir si una entrada no está en el conjunto; esto no se requiere para conjuntos numerables computables.
Un lenguaje recursivamente enumerable es un subconjunto computablemente enumerable de un lenguaje formal.
El conjunto de todas las oraciones demostrables en un sistema axiomático es un conjunto computablemente enumerable.
El teorema de Matiyasevich establece que todo conjunto numerable computable es un conjunto diofántico (el recíproco es trivialmente cierto).
Los conjuntos simples son computablemente enumerables pero no computables.
Los conjuntos creativos son computablemente enumerables pero no computables.
Ningún conjunto productivo es computablemente enumerable.
Dada una enumeración de Gödel $\phi$ de las funciones computables, el conjunto $\{\langle i,x\rangle \mid \phi _{i}(x)\downarrow \}$ (donde $\phi _{i}(x)\downarrow$ indica que $\phi _{i}(x)$ está definido) es computablemente enumerable. Este conjunto codifica el problema de la parada, ya que describe los parámetros de entrada para los que se detiene cada máquina de Turing.
Dada una enumeración de Gödel $\phi$ de las funciones computables, el conjunto $\{\left\langle x,y,z\right\rangle \mid \phi _{x}(y)=z\}$ es computablemente 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 a los números naturales, f es una función parcial computable si y solo si la gráfica de f, es decir, el conjunto de todos los pares $\langle x,f(x)\rangle$ tal que f (x) está definida, es computablemente enumerable.

Propiedades

Si A y B son conjuntos computablemente enumerables, entonces A ∩ B, A ∪ B y A × B son conjuntos computablemente enumerables. La preimagen de un conjunto computable enumerable bajo una función computable parcial es un conjunto computable enumerable.

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

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

Observaciones

Suponiendo 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 hay algún algoritmo que produzca una enumeración de S. Sin embargo, esto no puede tomarse por definición, porque la tesis de Church-Turing es una conjetura informal.

La definición de un conjunto computablemente enumerable como el dominio de una función parcial, en lugar de la imagen de una función computable total es común en los textos contemporáneos. Esto sucede porque en las teorías de recursión generalizada (como la teoría de recursión α) la definición correspondiente a los dominios es más natural. Otros textos usan la definición en términos de enumeraciones, lo que es equivalente a conjuntos computablemente enumerables.

Véase también

Referencias

↑ Downey, Rodney G.; Hirschfeldt, Denis R. (29 de octubre de 2010). Algorithmic Randomness and Complexity (en inglés). Springer Science & Business Media. p. 23. ISBN 978-0-387-68441-3.

Bibliografía

Rogers, H. The Theory of Recursive Functions and Effective Computability, MIT Press. ISBN 0-262-68052-1.
Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. ISBN 3-540-15299-7.
Soare, Robert I. Recursively enumerable sets and degrees. Bull. Amer. Math. Soc. 84 (1978), no. 6, 1149–1181.

Datos: Q676835

[1] Downey, Rodney G.; Hirschfeldt, Denis R. (29 de octubre de 2010). Algorithmic Randomness and Complexity (en inglés). Springer Science & Business Media. p. 23. ISBN 978-0-387-68441-3.

[1]