Conjuntos recursivamente enumeráveis
Na Teoria da Computabilidade, um conjunto de números naturais é chamado recursivamente enumerável (RE) se existe um algoritmo capaz de reconhecer seus elementos. Isso significa que, para qualquer número de entrada, o algoritmo para e aceita o número se ele pertence ao conjunto, e não para ou rejeita se não pertence. Esses conjuntos também são conhecidos por outros nomes, como computavelmente enumeráveis, semi-decidíveis ou Turing-reconhecíveis.
Pontos-chave
- Conjuntos RE são reconhecidos por algoritmos que param para elementos do conjunto.
- A definição pode ser estendida para conjuntos contáveis usando números de Gödel.
- Existem várias formulações equivalentes para conjuntos RE, incluindo a diofantina.
- Conjuntos RE são fechados sob operações como união, interseção e imagem por funções recursivas.
- Um conjunto é recursivo se ele e seu complemento são recursivamente enumeráveis.
Um conjunto S de números naturais é formalmente definido como recursivamente enumerável (RE) se existe uma função recursiva parcial (também chamada de função computável) cujo domínio é exatamente S. Isso significa que a função está definida se, e somente se, sua entrada é um membro de S. Essa definição pode ser ampliada para qualquer conjunto contável arbitrário A. Para isso, utiliza-se a numeração de Gödel para representar os elementos de A, e um subconjunto de A é considerado RE se o conjunto dos seus números de Gödel correspondentes for recursivamente enumerável.
Existem diversas propriedades equivalentes para caracterizar um conjunto S de números naturais como recursivamente enumerável. A equivalência entre a semidecidibilidade (reconhecibilidade por um algoritmo) e a enumerabilidade (ser o resultado de uma enumeração) pode ser demonstrada pela técnica de 'dovetailing'. Além disso, Yuri Matiyasevich, ao resolver negativamente o décimo problema de Hilbert, descobriu as caracterizações diofantinas para conjuntos recursivamente enumeráveis. Embora não sejam tão intuitivas quanto as definições iniciais, os conjuntos diofantinos são historicamente a primeira maneira de descrever esses conjuntos, mesmo que sua equivalência só tenha sido provada décadas depois da introdução dos conjuntos RE. O número de variáveis na definição diofantina é o menor conhecido até agora, mas pode ser que um número ainda menor possa ser usado.
Os conjuntos recursivamente enumeráveis (RE) possuem várias propriedades importantes que demonstram sua robustez sob certas operações. Se A e B são conjuntos RE, então sua interseção (A ∩ B), sua união (A ∪ B) e seu produto cartesiano (A × B, com pares ordenados mapeados para um único número natural pela função de emparelhamento de Cantor) também são conjuntos RE. A imagem de um conjunto RE sob uma função parcial recursiva também resulta em um conjunto RE. Um conjunto é RE se, e somente se, ele pertence ao nível Σ¹₀ da hierarquia aritmética. Um conjunto T é chamado co-recursivamente enumerável se seu complemento é RE, o que é equivalente a estar no nível Π¹₀ da hierarquia aritmética. Um conjunto A é recursivo (ou computável) se, e somente se, tanto A quanto seu complemento são recursivamente enumeráveis. Além disso, um conjunto A é recursivo se, e somente se, ele é finito ou a imagem de uma função crescente totalmente recursiva. É importante notar que alguns pares de conjuntos RE são efetivamente separáveis, enquanto outros não são.
De acordo com a Tese de Church-Turing, qualquer função que possa ser efetivamente calculada por um ser humano ou máquina é também calculável por uma Máquina de Turing. Consequentemente, um conjunto S é recursivamente enumerável se, e somente se, existe um algoritmo capaz de produzir uma enumeração de S. Contudo, essa afirmação não pode ser considerada uma definição formal, pois a Tese de Church-Turing é uma conjectura informal, e não um axioma formal. A definição de um conjunto RE como o domínio de uma função parcial é bastante comum na literatura, sendo preferida em algumas teorias de recursividade generalizada, como a teoria da α-recursão, onde essa abordagem se mostra mais natural. Outros textos, entretanto, utilizam a definição em termos de enumerações, que é equivalente para conjuntos recursivamente enumeráveis.


