Conjunto recursivo

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 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 \,.
  • Sea A \, un conjunto recurrente, entonces A \, es recurrentemente enumerable.
  • Un conjunto B \, es recurrente si y sólo si B \, y su complementario (B^C \,) son ambos recurrentemente enumerables.



Wikimedia foundation. 2010.

Игры ⚽ Нужна курсовая?

Mira otros diccionarios:

  • Conjunto recursivo — 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… …   Enciclopedia Universal

  • Conjunto recursivamente enumerable — Se denomina recursivamente enumerable (r. e.) a un conjunto, dentro de la teoría de la computabilidad, si existe una función computable g(x) que esté definida únicamente para aquellos números naturales que pertenecen a B: Véase también Lenguaje… …   Wikipedia Español

  • Conjunto recursivamente enumerable — En teoría de la computabilidad, un conjunto se denomina recursivamente enumerable (r. e.) si existe una función computable g(x) que esté definida únicamente para aquellos números naturales que pertenecen a B: B = x ∈ ℕ | g(x) = ↓ Ver también: ●… …   Enciclopedia Universal

  • Conjunto de Cantor — De izquierda a derecha, sucesivos pasos de la construcción geométrica del conjunto de Cantor. Para ilustrar la definición numérica se destacan cuatro puntos del conjunto (0, 2/3, 1 y 1/4) y su expresión en base 3. El conjunto de Cantor, llamado… …   Wikipedia Español

  • Función computable — Las funciones computables son el objeto básico de estudio de la teoría de la computabilidad y son, específicamente, las funciones que pueden ser calculadas por una máquina de Turing. Contenido 1 Introducción 2 Definición 3 Comentarios …   Wikipedia Español

  • Número real — Diferentes clases de números reales. Recta real …   Wikipedia Español

  • Teselación de Penrose — Una teselación de Penrose Una Teselación de Penrose o suelo de baldosas de Penrose es una teselación no periódica generada por un conjunto aperiódico de baldosas prototipo nombradas en honor a Roger Penrose, quien investigó esos conjuntos en la… …   Wikipedia Español

  • Algoritmo divide y vencerás — En la cultura popular, divide y vencerás hace referencia a un refrán que implica resolver un problema difícil, dividiéndolo en partes más simples tantas veces como sea necesario, hasta que la resolución de las partes se torna obvia. La solución… …   Wikipedia Español

  • Recursión — Saltar a navegación, búsqueda Anuncio de cacao con una imagen recursiva. La mujer muestra un paquete idéntico al del propio anuncio, conteniendo así a otra mujer que muestra otro paquete más pequeño, de forma recursiva …   Wikipedia Español

  • Grandes sistemas de Burroughs — Los grandes sistemas de Burroughs fueron los más grandes de tres series de computadores mainframes de Burroughs Corporation. Fundada en los años 1880, Burroughs era la más vieja entidad continuamente operando en el área de la computación, pero… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”