Conjunto recursivamente enumerable
En la teoría de la computabilidad, tradicionalmente llamada teoría de la recursión, un conjunto S de números naturales se llama recursivamente enumerable, computable enumerable, semidecidable, probable o Turing-reconocible si: ▪ Existe un algoritmo tal que el conjunto de números de entrada para el cual el algoritmo se detiene Exactamente S. O, equivalentemente, ▪ Existe un algoritmo que enumera los miembros de S. Esto significa que su salida es simplemente una lista de los miembros de S: s1, s2, s3, .... Si es necesario, este algoritmo puede Correr para siempre La primera condición sugiere por qué a veces se utiliza el término semidecidable; El segundo sugiere por qué computable enumerable se utiliza. Las abreviaturas r.e. Y c.e. Se utilizan a menudo, incluso en la impresión, en vez de la frase completa. En la teoría de complejidad computacional, la clase de complejidad que contiene todos los conjuntos recursivamente enumerables es RE. En la teoría de la recursión, la red de r.e. Conjuntos en la inclusión se denota.