En la teoría de la computabilidad , un conjunto de números naturales se llama computable , recursivo o decidible si hay un algoritmo que toma un número como entrada, termina después de un tiempo finito (posiblemente dependiendo del número dado) y decide correctamente si el número pertenece o no al conjunto.
Un conjunto que no es computable se llama no computable o indecidible .
Una clase de conjuntos más general que los computables consiste en los conjuntos computablemente enumerables (ce) , también llamados conjuntos semidecidibles . Para estos conjuntos, sólo se requiere que exista un algoritmo que decida correctamente cuándo un número está en el conjunto; el algoritmo puede no dar ninguna respuesta (pero no la respuesta incorrecta) para números que no están en el conjunto.
Un subconjunto de números naturales se llama computable si existe una función computable total tal que if y if . En otras palabras, el conjunto es computable si y sólo si la función del indicador 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 emparejamiento de Cantor son conjuntos computables.
A es un conjunto computable si y sólo 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 total computable es computable. (En general, la imagen de un conjunto computable bajo una función computable es ce, pero posiblemente no sea 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 sólo 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.
