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 .

Relación con el problema de Post

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]

Definiciones formales y algunas propiedades

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}$ ${\displaystyle e}$ ${\displaystyle W_{e}{\text{ infinite}}\implies W_{e}\not \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}$ ${\displaystyle f}$ ${\displaystyle 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}$ ${\displaystyle p_{I}}$ ${\displaystyle p_{I}}$ ${\displaystyle I}$
• Un conjunto se llama hipersimple si es simple y su complemento es hiperinmune. ^[3] ${\displaystyle S\subseteq \mathbb {N} }$

Notas

1. Nies (2009) pág. 35
2. Nies (2009) pág. 27
3. Nies (2009) pág. 37

Referencias

• 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  .