Conjunto computable

En la teoría de la computabilidad , un conjunto de números naturales se denomina computable , recursivo o decidible si existe un algoritmo que toma un número como entrada, termina después de una cantidad finita de tiempo (posiblemente dependiendo del número dado) y decide correctamente si el número pertenece al conjunto o no.

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

Una clase más general de conjuntos que los computables consiste en los conjuntos computablemente enumerables (ce) , también llamados conjuntos semidecidibles . Para estos conjuntos, solo se requiere que exista un algoritmo que decida correctamente cuándo un número está en el conjunto; el algoritmo puede no dar respuesta (pero no la respuesta incorrecta) para números que no están en el conjunto.

Un subconjunto de los números naturales se denomina computable si existe una función computable total tal que si y si . En otras palabras, el conjunto es computable si y solo si la función indicadora es computable . ${\estilo de visualización S}$ ${\estilo de visualización f}$${\displaystyle f(x)=1}$${\displaystyle x\en S}$${\displaystyle f(x)=0}$${\displaystyle x\no en S}$${\estilo de visualización S}$ ${\displaystyle \mathbb {1} _ {S}}$

Ejemplos:

• Todo subconjunto finito o cofinito de los números naturales es computable. Esto incluye los siguientes casos especiales:
  • El conjunto vacío es computable.
  • Todo el conjunto de números naturales es computable.
  • Cada número natural ( tal como se define en la teoría de conjuntos estándar ) es computable; es decir, el conjunto de números naturales menores que un número natural dado es computable.
• El subconjunto de números primos es computable.
• Un lenguaje recursivo es un subconjunto computable de un lenguaje formal .
• El conjunto de números de Gödel de pruebas aritméticas descritos en el artículo de Kurt Gödel "Sobre proposiciones formalmente indecidibles de Principia Mathematica y sistemas relacionados I" es computable; véanse los teoremas de incompletitud de Gödel .

No ejemplos:

• 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 castores ocupados no es computable.
• El décimo problema de Hilbert no es computable.

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 bajo la función de apareamiento de Cantor son conjuntos computables.

A es un conjunto computable si y solo si A y el complemento de A son ambos computablemente enumerables (ce). La preimagen de un conjunto computable bajo una función computable total es un conjunto computable. La imagen de un conjunto computable bajo una biyección computable total es computable. (En general, la imagen de un conjunto computable bajo una función computable es ce, pero posiblemente no computable).

A es un conjunto computable si y sólo si está en el nivel de la jerarquía aritmética . ${\displaystyle \Delta _ {1}^{0}}$

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.

• Lenguaje recursivamente enumerable
• Lenguaje recursivo
• Recursión

• Cutland, N. Computabilidad. Cambridge University Press, Cambridge-Nueva York, 1980. ISBN  0-521-22384-9 ; ISBN 0-521-29465-7 
• Rogers, H. La teoría de funciones recursivas y computabilidad efectiva , MIT Press. ISBN 0-262-68052-1 ; ISBN 0-07-053522-1  
• Soare, R. Conjuntos y grados enumerables de forma recursiva. Perspectivas en lógica matemática. Springer-Verlag, Berlín, 1987. ISBN 3-540-15299-7 

• Sakharov, Alex. "Conjunto recursivo". MathWorld .