Conjunto recursivo

En la teoría de la computabilidad, un conjunto de números naturales se llama computable, recursivo o decidible si hay un algoritmo que decide correctamente si un número pertenece o no al conjunto en tiempo finito.

Un conjunto que no es computable se llama no computable o indecidible.

Una clase más general de conjuntos que los computables son los computablemente enumerables (c.e.). Para estos conjuntos, solo se requiere que exista un algoritmo que decida correctamente cuando un número está en el conjunto; el algoritmo puede no dar una respuesta (pero no la respuesta incorrecta) para los números que no están en el conjunto.

Desde el punto de vista de los problemas de decisión, un conjunto recursivo es uno para el cual el problema de pertenencia es decidible.

Definición formal

editar

Un conjunto   de naturales se llama computable si existe una función total computable   tal que   si   y   si   . En otras palabras, el conjunto   es computable si y solo si su función indicatriz lo es.

Ejemplos y contraejemplos

editar

Ejemplos:

Contraejemplos:

Propiedades

editar

Si A es un conjunto computable, entonces el complemento de A es un conjunto computable. Si A y B son conjuntos computables, entonces AB, AB y la imagen de A × B son conjuntos computables.

A es un conjunto computable si y solo si A y su complemento son computablemente enumerables (c.e.). La preimagen de un conjunto computable bajo una función computable total es computable.

A es un conjunto computable si y solo si está en el nivel   de la jerarquía aritmética .

A es un conjunto computable si y solo si es el rango de una función computable total no decreciente o el conjunto vacío. La imagen de un conjunto computable bajo una función computable total no decreciente es computable.

Véase también

editar

Referencias

editar