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: O equivalentemente, 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.
La segunda condición sugiere por qué se usa computablemente enumerable.
En la teoría de la complejidad computacional, la clase de complejidad que contiene todos los conjuntos computablemente enumerables es RE.
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. Las siguientes propiedades de un conjunto de naturales S son equivalentes: La equivalencia de semidecidibilidad y enumerabilidad se puede obtener mediante la técnica de dovetailing.
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.
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.
