Computablemente enumerable
En la teoría de la computabilidad , un conjunto S de números naturales se denomina computablemente enumerable (ce) , recursivamente enumerable (re) , semidecidible , parcialmente decidible , listable , demostrable o reconocible por Turing si:
La primera condición sugiere por qué a veces se usa el término semidecidable . Más precisamente, si un número está en el conjunto, uno puede decidir esto ejecutando el algoritmo, pero si el número no está en el conjunto, el algoritmo se ejecuta indefinidamente y no se devuelve información. Un conjunto que es "completamente decidible" es un conjunto computable . La segunda condición sugiere por qué se utiliza computablemente enumerable . Las abreviaturas ce y re se utilizan a menudo, incluso impresas, en lugar de la frase completa.
En la teoría de la complejidad computacional , la clase de complejidad que contiene todos los conjuntos enumerables computacionalmente es RE . En la teoría de la recursividad, se denota el enrejado de conjuntos de ce bajo inclusión .
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 sólo si su entrada es miembro de S .
La equivalencia de semidecidibilidad y enumerabilidad puede obtenerse mediante la técnica del acoplamiento .
Las caracterizaciones diofánticas de un conjunto computablemente enumerable, aunque no son tan sencillas o intuitivas como las primeras definiciones, fueron encontradas por Yuri Matiyasevich como parte de la solución negativa del Décimo Problema de Hilbert . Los conjuntos diofánticos son anteriores a la teoría de la recursividad y, por lo tanto, históricamente son la primera forma de describir estos conjuntos (aunque esta equivalencia solo se observó más de tres décadas después de la introducción de conjuntos computablemente enumerables).
