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 {\displaystyle S} dos números naturais é chamado recursivo se existe uma função computável total f {\displaystyle f} tal que f ( x ) = 1 {\displaystyle f(x)=1} se x ∈ S {\displaystyle x\in S} e f ( x ) = 0 {\displaystyle f(x)=0} se x ∉ S {\displaystyle x\not \in S} . Em outras palavras, o conjunto S {\displaystyle S} é recursivo se e somente se a função indicadora 1 S {\displaystyle 1_{S}} é computável.
dos 
tal que
f
(
x
)
=
1
{\displaystyle f(x)=1}
se
x
∈
S
{\displaystyle x\in S}
e
f
(
x
)
=
0
{\displaystyle f(x)=0}
se
x
∉
S
{\displaystyle x\not \in S}
. Em outras palavras, o conjunto
S
{\displaystyle S}
é 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 Δ 1 0 {\displaystyle \Delta _{1}^{0}} da hierarquia aritmética.
da 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
