Clase de conjuntos cuyos complementos son recursivamente enumerables; equivalentemente, problemas para los cuales la no‑pertenencia puede semi-decidirse por un procedimiento efectivo que se detiene en las instancias negativas.

Principio

Un conjunto es co-recursivamente enumerable (co-r.e.) cuando existe una máquina de Turing que acepta y se detiene exactamente en las entradas que no pertenecen al conjunto; co-r.e. captura la semi-decidibilidad de la falsedad en lugar de la verdad.

Demostración

Si el conjunto de parada K es recursivamente enumerable, su complemento —los codificados de pares programa/entrada que no se detienen— es co-recursivamente enumerable; la pertenencia al complemento puede confirmarse si existe un reconocedor de no-parada (por ejemplo, mediante enumeración de pruebas de no-parada en contextos restringidos).

Aplicación incorrecta

Asumir que co-r.e. implica decidibilidad, o tratar un procedimiento que a veces refuta la pertenencia como un método uniforme de refutación para todas las entradas sin verificar cobertura completa.

Consecuencia

Para un conjunto co-r.e. es posible certificar algorítmicamente la no‑pertenencia ejecutando el co-reconocedor hasta la aceptación; como con las r.e., las co-r.e. pueden no admitir una refutación universal efectiva de la pertenencia sin estructura adicional.

Inversión

Recursivamente enumerable: conjuntos semi-decidibles para la pertenencia; decidible: conjuntos que son tanto r.e. como co-r.e.; no-co-r.e.: complementos de conjuntos sin enumeradores para los no-miembros.

Límite

Definido respecto a modelos estándar; la clase no está cerrada por complemento en general (el complemento de una co-r.e. es r.e.), y muchas clases no son ni r.e. ni co-r.e.; excluye clases con oráculos salvo que se especifique.

Tensión semántica

La tensión está con r.e.: la asimetría entre reconocer evidencia positiva y reconocer evidencia negativa genera comportamientos algorítmicos y propiedades de cerradura diferentes.

Síntesis

Co-recursivamente enumerable formaliza la reconocibilidad algorítmica de la no‑pertenencia: mientras la pertenencia puede permanecer esquiva, la no‑pertenencia puede certificarse por un procedimiento efectivo que se detiene cuando el conjunto pertenece a esta clase.