Clase de conjuntos (lenguajes) para los que existe una máquina de Turing que enumera todos los miembros o, equivalentemente, acepta exactamente las entradas del conjunto deteniéndose y aceptando en ellas; la máquina puede no detenerse en los no-miembros.

Principio

Recursivamente enumerable (r.e.) significa semi-decidible: existe un procedimiento efectivo que, para cada miembro, eventualmente se detiene y señala la pertenencia, mientras que los no-miembros no necesariamente llevan a la detención; la enumeración y el reconocimiento son caracterizaciones equivalentes.

Demostración

El conjunto de teoremas demostrables por un sistema formal axiomatizable de forma computable es recursivamente enumerable: una máquina de Turing puede enumerar sistemáticamente todas las demostraciones y así listar todas las fórmulas demostrables.

Aplicación incorrecta

Suponer que un conjunto r.e. es decidible porque sus miembros pueden listarse; interpretar que la no-detención sobre un no-miembro es prueba de no-pertenencia en lugar de ausencia de evidencia.

Consecuencia

La pertenencia a un conjunto r.e. puede confirmarse ejecutando el enumerador/recognizer hasta la aceptación; sin embargo, la ausencia de aceptación tras ejecuciones largas no proporciona una respuesta negativa definitiva sin información adicional.

Inversión

Co-recursivamente enumerable: conjuntos cuyos complementos son r.e.; decidible: conjuntos que son a la vez r.e. y co-r.e.

Límite

Definido respecto a una codificación estándar y un modelo (máquinas de Turing); excluye máquinas con oráculo salvo que se especifique; propiedades de cerradura incluyen unión e intersección con conjuntos decidibles, pero no el complemento en general.

Tensión semántica

Tensión entre r.e. y decidibilidad: la enumerabilidad y el reconocimiento capturan información positiva, mientras que la decidibilidad exige procedimientos positivos simétricos para los casos negativos.

Síntesis

Recursivamente enumerable captura la noción de reconocibilidad algorítmica positiva: los miembros pueden ser efectivamente producidos o reconocidos, pero sus complementos pueden permanecer fuera de confirmación algorítmica sin estructura adicional.