Conjunto simple

En teoría de computabilidad , un subconjunto de los números naturales se denomina simple si es computablemente enumerable (ce) y coinfinito (es decir, su complemento es infinito), pero todo subconjunto infinito de su complemento no es ce. Los conjuntos simples son ejemplos de conjuntos ce que no son computables .

Los conjuntos simples fueron ideados por Emil Leon Post en la búsqueda de un conjunto ce no Turing-completo. Si tales conjuntos existen o no se conoce como el problema de Post . Post tuvo que probar dos cosas para obtener su resultado: que el conjunto simple A no es computable, y que K , el problema de la parada , no se reduce a A por Turing . Tuvo éxito en la primera parte (lo cual es obvio por definición), pero para la otra parte, solo logró probar una reducción de muchos-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 . Proporcionan 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]

A continuación se denota un listado uniforme estándar de todos los conjuntos ce. ${\displaystyle W_{e}}$

• Un conjunto se llama inmune si es infinito, pero para cada índice , tenemos . O equivalentemente: no existe ningún subconjunto infinito de que sea ce.${\displaystyle I\subseteq \mathbb {N} }$${\displaystyle I}$${\estilo de visualización e}$${\displaystyle W_{e}{\text{ infinito}}\implica W_{e}\no \subseteq I}$${\displaystyle I}$
• Un conjunto se llama simple si es ce y su complemento es inmune.${\displaystyle S\subseteq \mathbb {N}}$
• Un conjunto se llama efectivamente inmune si es infinito, pero existe una función recursiva tal que para cada índice , tenemos que .${\displaystyle I\subseteq \mathbb {N} }$${\displaystyle I}$${\estilo de visualización f}$${\estilo de visualización e}$${\displaystyle W_{e}\subseteq I\implies \#(W_{e})<f(e)}$
• Un conjunto se llama efectivamente simple si es ce y su complemento es efectivamente inmune. Todo conjunto efectivamente simple es simple y Turing-completo.${\displaystyle S\subseteq \mathbb {N}}$
• Un conjunto se llama hiperinmune si es infinito, pero no está dominado computacionalmente, donde es la lista de miembros de en orden. ^[2]${\displaystyle I\subseteq \mathbb {N} }$${\displaystyle I}$$estilo de visualización p_{I}}$$estilo de visualización p_{I}}$${\displaystyle I}$
• Un conjunto se llama hipersimple si es simple y su complemento es hiperinmune. ^[3]${\displaystyle S\subseteq \mathbb {N}}$

• Soare, Robert I. (1987). Conjuntos y grados enumerables recursivamente. Un estudio de funciones computables y conjuntos generados computacionalmente . 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 recursión. La teoría de funciones y conjuntos de números naturales . Estudios de lógica y fundamentos de las matemáticas. Vol. 125. Ámsterdam: Holanda Septentrional. ISBN 0-444-87295-7.Zbl 0661.03029  .
• Nies, André (2009). Computabilidad y aleatoriedad . Oxford Logic Guides. Vol. 51. Oxford: Oxford University Press. ISBN 978-0-19-923076-1.Zbl 1169.03034  .