Conjunto recursivo
De Wikipedia, la enciclopedia libre
En teoría de la computabilidad, un conjunto B es recurrente (recurrente primitivo) cuando su función característica es computable total o lo que es lo mismo, es una función recurrente primitiva. 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.
[editar] Teoremas relacionados
- Sea
un conjunto recurrente, entonces su complementario (
) también lo es.
- Sean y
conjuntos recurrente, entonces los siguientes conjuntos también lo son: 
y 
.
- Sea un conjunto recurrente, entonces es recurrentemente enumerable.
- Un conjunto es recurrente si y sólo si y su complementario (
) son ambos recurrentemente enumerables.
