Conjunto recursivo

En teoría de la computabilidad, un conjunto B es recursivo, computable o decidible (recurrente primitivo) cuando su función característica es computable total. Esto significa que la función característica, la cual es un predicado, toma valor 1 (cierto) para todos los elementos del conjunto y 0 (falso) para el resto.

Teoremas relacionados

• Sea $A\,$ un conjunto recurrente, entonces su complementario ($A^{C}\,$) también lo es.

• Sean $A\,$ y $B\,$ conjuntos recurrente, entonces los siguientes conjuntos también lo son: $A\cap B\,$ y $A\cup B\,$.

• Sea $A\,$ un conjunto recurrente, entonces $A\,$ es recurrentemente enumerable.

• Un conjunto $B\,$ es recurrente si y sólo si $B\,$ y su complementario ($B^{C}\,$) son ambos recurrentemente enumerables.

• Datos: Q877945