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 relacionadosEditar

  • 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.