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

Un conjunto ${\displaystyle S}$ de naturales se llama computable si existe una función total computable ${\displaystyle f}$ tal que ${\displaystyle f(x)=1}$ si ${\displaystyle x\in S}$ y ${\displaystyle f(x)=0}$ si ${\displaystyle x\notin S}$ . En otras palabras, el conjunto ${\displaystyle S}$ es computable si y solo si su función indicatriz lo es.

Ejemplos y contraejemplos

Ejemplos:

• Todo subconjunto finito o cofinito de los números naturales es computable. Esto incluye estos casos especiales:
  • El conjunto vacío es computable.
  • El conjunto de los números naturales es computable.
  • E conjunto de números naturales menores que un número natural dado es computable.
• Los números primos son computables.
• Un lenguaje recursivo es un subconjunto computable de un lenguaje formal .

Contraejemplos:

• El conjunto de máquinas de Turing que se detienen no es computable.
• La clase de isomorfismo de dos complejos simpliciales finitos no es computable.
• El conjunto de campeones busy beaver no es computable.
• El décimo problema de Hilbert no es computable.

Propiedades

Si A es un conjunto computable, entonces el complemento de A es un conjunto computable. Si A y B son conjuntos computables, entonces A ∩ B, A ∪ B 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 ${\displaystyle \Delta _{1}^{0}}$ 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

• Lenguaje recursivamente enumerable
• Lenguaje recursivo
• Recursividad

Referencias

• Cutland, N. Computability. Cambridge University Press, Cambridge-New York, 1980. ISBN 0-521-22384-9; ISBN 0-521-29465-7
• Rogers, H. The Theory of Recursive Functions and Effective Computability, MIT Press. ISBN 0-262-68052-1; ISBN 0-07-053522-1
• Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. ISBN 3-540-15299-7