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 ${\displaystyle A\,}$  un conjunto recurrente, entonces su complementario (${\displaystyle A^{C}\,}$ ) también lo es.

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

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

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

•   Datos: Q877945