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 , enumerable , demostrable o reconocible por Turing si:
La primera condición sugiere por qué a veces se usa el término semidecidible . 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 para siempre y no se devuelve información. Un conjunto que es "completamente decidible" es un conjunto computable . La segunda condición sugiere por qué se usa computablemente enumerable . Las abreviaturas ce y re se usan 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 computablemente enumerables es RE . En la teoría de la recursión, la red de conjuntos ce bajo inclusión se denota .
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 .
La equivalencia de semidecidibilidad y enumerabilidad se puede obtener mediante la técnica de cola de milano .
Yuri Matiyasevich encontró las caracterizaciones diofánticas de un conjunto numerable computable, aunque no tan sencillas o intuitivas como las primeras definiciones, como parte de la solución negativa al 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 los conjuntos computablemente enumerables).
