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

Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.