En la teoría de la computabilidad , un conjunto de números naturales se denomina computable , recursivo o decidible si existe un algoritmo que toma un número como entrada, termina después de una cantidad finita de tiempo (posiblemente dependiendo del número dado) y decide correctamente si el número pertenece al conjunto o no.
Un conjunto que no es computable se llama no computable o indecidible .
Una clase más general de conjuntos que los computables consiste en los conjuntos computablemente enumerables (ce) , también llamados conjuntos semidecidibles . Para estos conjuntos, solo se requiere que exista un algoritmo que decida correctamente cuándo un número está en el conjunto; el algoritmo puede no dar respuesta (pero no la respuesta incorrecta) para números que no están en el conjunto.
Un subconjunto de los números naturales se denomina computable si existe una función computable total tal que si y si . En otras palabras, el conjunto es computable si y solo si la función indicadora es computable .
Ejemplos:
No ejemplos:
Si A es un conjunto computable, entonces el complemento de A es un conjunto computable. Si A y B son conjuntos computables, entonces A ∩ B , A ∪ B y la imagen de A × B bajo la función de apareamiento de Cantor son conjuntos computables.
A es un conjunto computable si y solo si A y el complemento de A son ambos computablemente enumerables (ce). La preimagen de un conjunto computable bajo una función computable total es un conjunto computable. La imagen de un conjunto computable bajo una biyección computable total es computable. (En general, la imagen de un conjunto computable bajo una función computable es ce, pero posiblemente no computable).
A es un conjunto computable si y sólo si está en el nivel de la jerarquía aritmética .
A es un conjunto computable si y solo si es el rango de una función computable total no decreciente o el conjunto vacío. La imagen de un conjunto computable bajo una función computable total no decreciente es computable.
