Conjunto recursivo
De Wikipedia, la enciclopedia libre
En teoría de la computabilidad, un conjunto B es recursivo (recursivo primitivo) cuando su función característica es computable total o lo que es lo mismo, es una función recursiva 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 A un conjunto recursivo, entonces su complementario (Ac) también lo es.
- Sean A y B conjuntos recursivos, entonces los siguientes conjuntos también lo son: A ∩ B y A ∪ B.
- Sea A un conjunto recursivo, entonces A es recursivamente enumerable.
- Un conjunto B es recursivo si y sólo si B y su complementario (Bc) son ambos recursivamente enumerables.