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 A \, un conjunto recurrente, entonces su complementario (A^C \,) también lo es.
  • Sean  A \, y  B \, conjuntos recurrente, entonces los siguientes conjuntos también lo son: A \cap B \, y A \cup B \,.
  • Un conjunto B \, es recurrente si y sólo si B \, y su complementario (B^C \,) son ambos recurrentemente enumerables.