Conjunto recursivo

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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[editar | editar código-fonte]

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[editar | editar código-fonte]

  • 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[editar | editar código-fonte]

Se A é um conjunto recursivo, então o complemento de A é um conjunto recursivo. Se A e B são conjunto recursivos, então AB, AB 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^0_1 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[editar | editar código-fonte]