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

editar

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

editar
  • 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

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   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