Conjunto computável - Computable set
Na teoria da computabilidade , um conjunto de números naturais é denominado computável , recursivo ou decidível se houver um algoritmo que recebe um número como entrada, termina após um período finito de tempo (possivelmente dependendo do número fornecido) e decide corretamente se o número pertence ao conjunto ou não.
Um conjunto que não é computável é denominado não computável ou indecidível .
Uma classe de conjuntos mais geral do que os computáveis consiste nos conjuntos computáveis enumeráveis (ce) , também chamados de conjuntos semidecidíveis . Para esses conjuntos, é necessário apenas que exista um algoritmo que decida corretamente quando um número está no conjunto; o algoritmo pode não dar resposta (mas não a resposta errada) para números que não estão no conjunto.
Definição formal
Um subconjunto dos números naturais é denominado computável se existe uma função computável total tal que se e se . Em outras palavras, o conjunto é computável se e somente se a função do indicador for computável .
Exemplos e não exemplos
Exemplos:
- Cada subconjunto finito ou cofinito dos números naturais é computável. Isso inclui estes casos especiais:
- O conjunto vazio é computável.
- Todo o conjunto de números naturais é computável.
- Cada número natural ( conforme definido na teoria dos conjuntos padrão ) é computável; ou seja, o conjunto de números naturais menor que um determinado número natural é computável.
- O subconjunto de números primos é computável.
- Uma linguagem recursiva é um subconjunto computável de uma linguagem formal .
- O conjunto de números de Gödel de provas aritméticas descrito no artigo de Kurt Gödel "Sobre proposições formalmente indecidíveis de Principia Mathematica e sistemas relacionados I" é computável; veja os teoremas da incompletude de Gödel .
Não exemplos:
- O conjunto de máquinas de Turing que param não é computável.
- A classe de isomorfismo de dois complexos simpliciais finitos não é computável.
- O conjunto de campeões de castores ocupados não é computável.
- O décimo problema de Hilbert não é computável.
Propriedades
Se A é um conjunto computável, o complemento de A é um conjunto computável. Se A e B são conjuntos computáveis, então A ∩ B , A ∪ B e a imagem de A × B sob a função de emparelhamento de Cantor são conjuntos computáveis.
A é um conjunto computável se e somente se A e o complemento de A forem ambos ce . A pré-imagem de um conjunto computável sob uma função computável total é um conjunto computável. A imagem de um conjunto computável sob uma bijeção computável total é computável. (Em geral, a imagem de um conjunto computável sob uma função computável é ce, mas possivelmente não computável).
A é um conjunto computável se e somente se estiver no nível da hierarquia aritmética .
A é um conjunto computável se e somente se for o intervalo de uma função computável total não decrescente ou o conjunto vazio. A imagem de um conjunto computável sob 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. Theory of Recursive Functions and Effective Computability , MIT Press. ISBN 0-262-68052-1 ; ISBN 0-07-053522-1
- Soare, R. Conjuntos e graus recursivamente enumeráveis. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. ISBN 3-540-15299-7