Existem conjuntos contáveis ​​que não são computáveis ​​enumeráveis?

Um conjunto é contável se tiver uma bijeção com os números naturais e é computávelmente enumerável (ce) se houver um algoritmo que enumere seus membros.

Qualquer conjunto enumerável computacionalmente não finito deve ser contável, pois podemos construir uma bijeção a partir da enumeração.

Existem exemplos de conjuntos contáveis ​​que não são computáveis ​​enumeráveis? Ou seja, existe uma bijeção entre esse conjunto e os números naturais, mas não há algoritmo que possa calcular essa bijeção.

Existem exemplos de conjuntos contáveis ​​que não são enumeráveis?

Sim. Todos os subconjuntos dos números naturais são contáveis, mas nem todos são enumeráveis. (Prova: existem incontáveis ​​subconjuntos diferentes de  mas apenas inúmeras máquinas de Turing que poderiam atuar como enumeradores.) Portanto, qualquer subconjunto de  N que você já conhece não é recursivamente enumerável é um exemplo - como o conjunto de todos os números que codificam Turing máquinas que param para cada entrada.$\mathbb{N}$$\mathbb{N}$

Sim, todo idioma indecidível (não semi-decidível) possui essa propriedade.

Por exemplo, considere o conjunto .$L = \{(x,M) \mid M \text{ does not halt on input } x \}$

Suponha que tenhamos um algoritmo que pode enumerar os membros desse conjunto. Se esse algoritmo existisse, poderíamos usá-lo para resolver o problema de parada com as entradas , com o seguinte algoritmo:$x,M$

• Alternam entre funcionamento da máquina de n passos de x , e enumerar o n ° membro de L .$M$$n$$x$$n$$L$

para ou não para em x . Separar, finalmente encontraremos um n onde alcançamos um estado de parada. Se não parar, eventualmente alcançaremos ( M , x ) em nossa enumeração.$M$$x$$n$$(M,x)$

Portanto, temos uma redução e podemos concluir que não existe tal enumeração.

Observe que essas enumerações podem existir para problemas semi-decidíveis. Por exemplo, você pode enumerar o conjunto de todos os pares de entrada de máquina de parada, enumerando todos os traços possíveis de todas as execuções da Máquina de Turing após etapas e filtrar as que não terminam em um estado de parada. $n$

Na teoria da computabilidade, lidamos com subconjuntos de , onde Σ = { 0 , 1 } . Esse idioma é infinitamente contável e, portanto, qualquer subconjunto L ⊆ Σ ∗ é contável. Além disso, existem muitas linguagens indecidíveis, mas recursivamente enumeráveis, cujos complementos não são recursivamente enumeráveis. Estas línguas são subconjunto de Σ * e, portanto, são contáveis.$\Sigma^*$$\Sigma = \{0,1\}$$L \subseteq \Sigma^*$$\Sigma^*$