En la teoría de la computabilidad , un subconjunto de los números naturales se llama simple si es computablemente enumerable (ce) y co-infinito (es decir, su complemento es infinito), pero cada subconjunto infinito de su complemento no es ce. Los conjuntos simples son ejemplos de conjuntos ce que no son computables .
Relación con el problema de Post
Emil Leon Post ideó conjuntos simples en la búsqueda de un conjunto ce no completo de Turing. La existencia de tales conjuntos se conoce como problema de Post . Post tuvo que demostrar dos cosas para obtener su resultado: que el conjunto simple A no es computable, y que K , el problema que se detiene , no se reduce a A de Turing . Tuvo éxito en la primera parte (que es obvia por definición), pero en la otra parte, solo logró demostrar una reducción de muchos a uno .
La idea de Post fue validada por Friedberg y Muchnik en la década de 1950 utilizando una técnica novedosa llamada método de prioridad . Dan una construcción para un conjunto que es simple (y por lo tanto no computable), pero no logra calcular el problema de detención. [1]
Definiciones formales y algunas propiedades.
En lo que sigue, denota un listado ce estándar uniforme de todos los conjuntos ce.
- Un conjunto se llama inmune si es infinito, pero para cada índice , tenemos . O de manera equivalente: no hay un subconjunto infinito de eso es ce.
- Un conjunto Se llama simple si es ce y su complemento es inmune.
- Un conjunto se llama efectivamente inmune si es infinito, pero existe una función recursiva tal que para cada índice , tenemos eso .
- Un conjunto Se llama efectivamente simple si es ce y su complemento es efectivamente inmune. Cada conjunto efectivamente simple es simple y Turing completo.
- Un conjunto se llama hiperinmune si es infinito, pero no está dominado computablemente, donde es la lista de miembros de en orden. [2]
- Un conjunto Se llama hipersimple si es simple y su complemento es hiperinmune. [3]
Notas
Referencias
- Soare, Robert I. (1987). Conjuntos y grados recursivamente enumerables. Un estudio de funciones computables y conjuntos generados computablemente . Perspectivas en lógica matemática. Berlín: Springer-Verlag . ISBN 3-540-15299-7. Zbl 0667.03030 .
- Odifreddi, Piergiorgio (1988). Teoría clásica de la recursividad. La teoría de funciones y conjuntos de números naturales . Estudios de Lógica y Fundamentos de las Matemáticas. 125 . Amsterdam: Holanda Septentrional. ISBN 0-444-87295-7. Zbl 0661.03029 .
- Nies, André (2009). Computabilidad y aleatoriedad . Guías lógicas de Oxford. 51 . Oxford: Prensa de la Universidad de Oxford. ISBN 978-0-19-923076-1. Zbl 1169.03034 .