En la teoría de la computabilidad, un conjunto de números naturales se llama computable, recursivo o decidible si hay un algoritmo que decide correctamente si un número pertenece o no al conjunto en tiempo finito.
Un conjunto que no es computable se llama no computable o indecidible.
Para estos conjuntos, solo se requiere que exista un algoritmo que decida correctamente cuando un número está en el conjunto; el algoritmo puede no dar una respuesta (pero no la respuesta incorrecta) para los números que no están en el conjunto.
Ejemplos: Contraejemplos: Si A es un conjunto computable, entonces el complemento de A es un conjunto computable.
A es un conjunto computable si y solo si A y su complemento son computablemente enumerables (c.e.).
A es un conjunto computable si y solo si está en el nivel
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.