Conjunto recursivo

Na teoria da computabilidade, um conjunto de números naturais é chamado recursivo, computável ou decidível se existe um algoritmo que termina após uma quantidade finita de tempo e decide corretamente se um número pertence ou não ao conjunto.

Uma classe mais geral de conjuntos consiste nos conjuntos recursivamente enumeráveis, também chamados conjuntos semidecidíveis. Para estes conjuntos, somente é requerido que exista um algoritmo que decida corretamente quando um número está no conjunto; o algoritmo pode não dar resposta (mas não uma resposta errada) para números que não estão no conjunto.

Um conjunto que não é computável é chamado não computável ou indecidível.

Definição formal

Um subconjunto $S$ dos números naturais é chamado recursivo se existe uma função computável total $f$ tal que $f(x)=1$ se $x\in S$ e $f(x)=0$ se $x\not \in S$. Em outras palavras, o conjunto $S$ é recursivo se e somente se a função indicadora $1_{S}$ é computável.

Exemplos

• Qualquer conjunto finito ou cofinito dos números naturais é computável. Isto inclui estes casos especiais:
  • O conjunto vazio é computável.
  • A totalidade do conjunto dos números naturais é computável.
  • Cada número natural (como definido na teoria dos conjuntos padrão) é computável; isto é, o conjunto dos números naturais menos um dado número natural é computável.
• O conjunto dos números primos é computável.
• Uma linguagem recursiva é um subconjunto recursivo de uma linguagem formal.
• O conjunto dos números de Gödel das provas aritméticas descritas no artigo de Kurt Gödel "On formally undecidable propositions of Principia Mathematica and related systems I"; veja teorema da incompletude de Gödel.

Propriedades

Se A é um conjunto recursivo, então o complemento de A é um conjunto recursivo. Se A e B são conjunto recursivos, então A ∩ B, A ∪ B e a imagem de A × B sobre a função de emparelhamento de Cantor são conjuntos recursivos.

Um conjunto A é um conjunto recursivo se e somente se A e o complemento de A forem ambos conjuntos recursivamente enumeráveis. A imagem inversa de um conjunto recursivo sobre uma função computável total é um conjunto recursivo. A imagem de um conjunto computável sobre uma bijeção computável total é computável.

Um conjunto é recursivo se e somente se estiver no nível $\Delta _{1}^{0}$ da hierarquia aritmética.

Um conjunto é recursivo se e somente se ele é ou o alcance de uma função computável total não decrescente ou se é o conjunto vazio. A imagem de um conjunto computável sobre uma função computável total não decrescente é computável.

Referências

• Cutland, N. Computability. Cambridge University Press, Cambridge-New York, 1980. ISBN 0-521-22384-9; ISBN 0-521-29465-7
• Rogers, H. The Theory of Recursive Functions and Effective Computability, MIT Press. ISBN 0-262-68052-1; ISBN 0-07-053522-1
• Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. ISBN 3-540-15299-7