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 dos números naturais é chamado recursivo se existe uma função computável total tal que se e se . Em outras palavras, o conjunto é recursivo se e somente se a função indicadora é 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 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
Categoria:Teoria da computabilidade Categoria:Teoria da computação