Conjuntos recursivamente enumeráveis

Na Teoria da computabilidade, tradicionalmente chamada teoria da recursão, um conjunto S de números naturais é chamado recursivamente enumerável, computavelmente enumerável, semi-decidível, demonstrável ou Turing-reconhecível se:

Existe um algoritmo tal que o conjunto de números de entrada para qual o algoritmo pára é exatamente o conjunto de números em S.

Ou, equivalentemente,

Existe um algoritmo que enumera os membros de S. Isso significa que sua saída é simplesmente uma lista de membros de S: s₁, s₂, s₃, ... . Se necessário, esse algoritmo pode rodar para sempre.

A primeira condição sugere porque o termo semi-decidível às vezes é usado; o segundo sugere porque computavelmente enumerável é usado.

Na teoria de complexidade computacional, a classe de complexidade que contém todos os conjuntos recursivamente enumeráveis é RE (recursivamente enumerável). Na teorica da recursão, o Reticulado de conjuntos recursivamente enumeráveis sobre inclusão é denominado ${\mathcal {E}}$ .

Definição Formal

Um conjunto S de números naturais é chamado recursivamente enumerável se existe uma função recursiva parcial (também conhecida como função computável) na qual o domínio é exatamente S, significando que a função é definida se e somente se sua entrada é membro de S.

A definição pode ser estendida para um conjunto contável arbitrário A usando Número de Gödel para representar os elementos do conjunto e declarar um subconjunto de A para ser recursivamente enumerável se o conjunto dos números de Gödel correspondentes é recursivamente enumerável.

Formulações equivalentes

Abaixo todas as propriedades equivalentes de um conjunto S de números naturais:

Semi-decidibilidade:

O conjunto S é recursivamente enumerável. Ou seja, S é o domínio de uma função recursiva parcial.
Existe uma função recursiva parcial f tal que:

f(x)=\left\{{\begin{matrix}0&{\mbox{if}}\ x\in S\\{\mbox{indefinido/não pára}}\ &{\mbox{if}}\ x\notin S\end{matrix}}\right.

Enumerabilidade

O conjunto S é a imagem de uma função recursiva parcial.
O conjunto S é a imagem de uma função recursiva total ou vazia. Se S é infinito, a função pode ser escolhida para ser injetiva.
O conjunto S é a imagem de uma função recursiva primitiva ou vazia. Mesmo se S é infinito, repetição de valores podem ser necessárias nesse caso.

Diofantina:

Existe um polinômio p com coeficientes inteiros e variáveis x, a, b, c, d, e, f, g, h, i variando ao longo dos números naturais tais que

x\in S\Leftrightarrow \exists a,b,c,d,e,f,g,h,i\ (p(x,a,b,c,d,e,f,g,h,i)=0).

Existe uma polinomial de inteiros para inteiros tais que o conjunto S contém exatamente os números não negativos em seu intervalo.

A equivalência da semidecidibilidade e enumerabilidade pode ser obtida através da técnica de dovetailing.

As caracterizações Diofantina de um conjunto recursivamente enumerável, embora não tão simples ou intuitivo como as primeiras definições, foram encontradas por Yuri Matiyasevich como parte da solução negativa do décimo problema de Hilbert. Conjuntos diofantinos antecedem a teoria da recursão e são, historicamente, a primeira maneira de descrever esses conjuntos (embora essa equivalência apenas tenha sido demonstrada mais de três décadas depois da introdução dos conjuntos recursivamente enumeráveis). O número de variáveis associadas na definição acima de conjunto Diofantino é a mais conhecida até agora; pode ser que um número menor possa ser usado para definir todos os conjuntos diofantinos.

Exemplos

Todo conjunto recursivo é recursivamente enumerável, mas não é verdade que todo conjunto recursivamente enumerável é recursivo.
Uma linguagem recursivamente enumeravel é um subconjunto recursivamente enumerável de uma linguagem formal.
O conjunto de todas as sentenças demonstráveis em um sistema axiomático efetivamente apresentados é um conjunto recursivamente enumerável.
O teorema de Matiyasevich afirma que todo conjunto recursivamente enumerável é um conjunto Diofantino (o inverso é trivialmente verdadeiro).
Os conjuntos simples são recursivamente enumeráveis, mas não recursivos.
Os conjuntos criativos são recursivamente enumeráveis, mas não recursivos.
Qualquer conjunto produtivo não é recursivamente enumerável.
Dada uma numeração Gödel $\phi$ das funções computáveis, o conjunto $\{\langle i,x\rangle \mid \phi _{i}(x)\downarrow \}$ (onde $\langle i,x\rangle$ é a função de emparelhamento de Cantor e $\phi _{i}(x)\downarrow$ indica $\phi _{i}(x)$ é definido) é recursivamente enumerável. Este conjunto codifica o problema da parada, uma vez que descreve os parâmetros de entrada para qual cada máquina de Turing pára.
Dada uma numeração de Gödel $\phi$ das funções computáveis, o conjunto $\lbrace \left\langle x,y,z\right\rangle \mid \phi _{x}(y)=z\rbrace$ é recursivamente enumerável. Este conjunto codifica o problema de decidir um valor de uma função.
Dada uma função parcial f dos números naturais para os naturais, f é uma função parcialmente recursiva se e somente se o grafo de f, isto é, o conjunto de todos os pares $\langle x,f(x)\rangle$ tais que f(x) é definido, é recursivamente enumerável.

Propriedades

Se A e B são conjunto recursivamente enumeráveis então A ∩ B, A ∪ B and A × B (com o par ordenado de números naturais mapeado para um só número natural com a função de emparelhamento de Cantor) são conjuntos recursivamente enumeráveis. A imagem de um conjunto recursivamente enumerável sob uma função parcial recursiva é um conjunto recursivamente enumerável.

Um conjuntos é recursivamente enumerável se e somente se está no nível $\Sigma _{1}^{0}$ da hierarquia aritmética.

Um conjunto $T$ é chamado co-recursivamente enumerável se seu complemento é recursivamente enumerável. Equivalentemente, um conjunto é co-recursivamente enumerável se e somente se está no nível $\Pi _{1}^{0}$ da hierarquia aritmética.

Um conjunto A é recursivo (sinônimo: computável) se e somente se ambos A e o complemento de A são recursivamente enumeráveis. A é recursivo se e seomente se é ou um intervalo de um função crescente totalmente recursiva ou finito. Alguns pares de conjuntos recursivamente enumeráveis são efetivamente separáveis e outros não.

Remarcações

De acordo com a tese de Church-Turing, qualquer função efetivamente calculável é calculável por uma máquina de Turing, e, assim, um conjunto S é recursivamente enumerável se e somente se existe algum algoritmo que produz uma enumeração de S. No entanto, isso não pode ser tomado como uma definição formal, visto que a tese de Church-Turing é uma conjectura informal, ao invés de um axioma formal. A definição de um conjunto recursivamente enumerável como o domínio de uma função parcial, em vez de como o intervalo de uma função total recursiva, é bastante comum na literatura. Essa escolha é motivada pelo fato de que nas teorias de recursividade generalizada, como a teoria da α-recursão, a definição correspondente aos domínios foi feita para ser mais natural. Todavia, outros textos utilizam a definição em termos de enumerações, que é equivalente para conjuntos recursivamente enumeráveis.

Referências

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.
Soare, Robert I. Recursively enumerable sets and degrees. Bull. Amer. Math. Soc. 84 (1978), no. 6, 1149–1181.