- Conjunto recursivo
-
En teoría de la computabilidad, un conjunto B es recurrente, 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
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.
- Sea
Wikimedia foundation. 2010.