Conjunto recursivo

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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[editar]

  • Sea un conjunto recurrente, entonces su complementario () también lo es.
  • Sean y conjuntos recurrente, entonces los siguientes conjuntos también lo son: y .
  • Un conjunto es recurrente si y sólo si y su complementario () son ambos recurrentemente enumerables.