Conjunto simples

Na teoria da recursão (também chamada de teoria da computabilidade) um subconjunto dos números naturais é chamado de conjunto simples se ele é co-infinito e recursivamente enumerável, mas todo subconjunto infinito do seu complemento falha em ser enumerado recursivamente. Conjuntos simples são exemplos de conjuntos recursivamente enumeráveis que não são recursivos.

Relação com o problema de Post

Conjuntos simples foram concebidos por Emil Leon Post na busca por um conjunto que não fosse Turing completo e que fosse recursivamente enumerável. Se tais conjuntos existissem então seriam conhecidos como problema de Post. Post teve que provar duas coisas para obter seu resultado desejado,primeiro que um conjunto simples, digamos A, não é Turing-redutível ao conjunto vazio, segundo que K, o problema da parada, não é Turing-redutível à A. Ele obteve sucesso na primeira parte (que é a mais óbvia pela definição), mas para a segunda parte, ele só conseguiu provar a redução muitos para um (também chamada de redução por mapeamento).

Foi definida por Friedberg e Muchnik na década de 1950, uma nova técnica chamada de método de prioridade. Eles dão a construção de um conjunto que é simples (e, portanto, não-recursivo), mas essa técnica falha em calcular o problema da parada.

Definiçoes formais e algumas propriedades

• Um conjunto $I\subseteq \mathbb {N}$ é chamado imune se e somente se $I$ é infinito, mas para cada index $e$, Nós temos $W_{e}{\text{ infinite}}\implies W_{e}\not \subseteq I$. Ou equivalentemente: não há subconjunto infinito de $I$ que seja recursivamente enumerável.

• Um conjunto $S\subseteq \mathbb {N}$ é chamado simples se e somente se ele é recursivamente enumerável e seu complemento é imune.

• Um conjunto $I\subseteq \mathbb {N}$ é chamado efetivamente imune se e somente se$I$ é infinito, mas existe uma função recursiva $f$ tal que para cada index $e$, nós temos que $W_{e}\subseteq I\implies \#(W_{e})<f(e)$.

• Um conjunto $S\subseteq \mathbb {N}$ é chamado efetivamente simples se ele é recursivamente enumerável e seu complemento é efectivamente imune. Todo conjunto efectivamente simples , é simples and Turing-completo.

• Um conjunto $I\subseteq \mathbb {N}$ é chamado hyperimune se e somente se $I$ é infinito, mas $p_{I}$ não é computável, onde $p_{I}$ é a lista de membros de $I$ em ordem.

• Um conjunto $S\subseteq \mathbb {N}$ é chamado hypersimples se ele é simples e seu complemento é hyperimune.

Referências

• Soare, Robert I. (1987). Recursively enumerable sets and degrees. A study of computable functions and computably generated sets. Col: Perspectives in Mathematical Logic. Berlin: Springer-Verlag. ISBN 3-540-15299-7. Zbl 0667.03030 
• Odifreddi, Piergiorgio (1988). Classical recursion theory. The theory of functions and sets of natural numbers. Col: Studies in Logic and the Foundations of Mathematics. 125. Amsterdam: North Holland. ISBN 0-444-87295-7. Zbl 0661.03029 
• Nies, André (2009). Computability and randomness. Col: Oxford Logic Guides. 51. Oxford: Oxford University Press. ISBN 978-0-19-923076-1. Zbl 1169.03034