Existe-t-il des ensembles dénombrables qui ne sont pas énumérables par ordinateur?

Un ensemble est dénombrable s'il a une bijection avec les nombres naturels et est numériquement calculable (ce) s'il existe un algorithme qui énumère ses membres.

Tout ensemble non finissable pouvant être énuméré doit être dénombrable puisque nous pouvons construire une bijection à partir de l'énumération.

Y a-t-il des exemples d'ensembles dénombrables qui ne sont pas énumérables par ordinateur? Autrement dit, une bijection entre cet ensemble et les nombres naturels existe, mais aucun algorithme ne peut calculer cette bijection.

Existe-t-il des exemples d'ensembles dénombrables qui ne sont pas énumérables?

Oui. Tous les sous-ensembles des nombres naturels sont dénombrables mais pas tous énumérables. (Preuve: il existe un nombre incalculable de sous-ensembles différents de  mais uniquement de nombreuses machines Turing qui pourraient agir comme des énumérateurs.) Ainsi, tout sous-ensemble de  N que vous connaissez déjà n'est pas énumérable récursivement est un exemple - tel que l'ensemble de tous les nombres codant Turing machines qui s'arrêtent pour chaque entrée.$\mathbb{N}$$\mathbb{N}$

Oui, chaque langue indécidable (non semi-décidable) possède cette propriété.

Par exemple, considérons l'ensemble .$L = \{(x,M) \mid M \text{ does not halt on input } x \}$

Supposons que nous ayons un algorithme qui puisse énumérer les membres de cet ensemble. Si un tel algorithme existait, nous pourrions l'utiliser pour résoudre le problème d'arrêt avec les entrées , avec l'algorithme suivant:$x,M$

• Alterner entre la machine en marche pour n étapes de x , et dénombrer le n ième élément de L .$M$$n$$x$$n$$L$

s'arrête ou ne s'arrête pas sur x . S'il s'arrête, nous trouverons finalement un n où nous atteindrons un état d'arrêt. Si cela ne s'arrête pas, nous atteindrons finalement ( M , x ) dans notre énumération.$M$$x$$n$$(M,x)$

Ainsi, nous avons une réduction, et nous pouvons conclure qu'il n'y a pas une telle énumération.

Notez que de telles énumérations peuvent exister pour des problèmes semi-décidables. Par exemple, vous pouvez énumérer l'ensemble de toutes les paires entrée-machine d'arrêt en énumérant toutes les traces possibles de toutes les exécutions de Turing Machine après étapes et filtrer celles qui ne se terminent pas dans un état d'arrêt. $n$

Dans la théorie de la calculabilité, nous traitons des sous-ensembles de , où Σ = { 0 , 1 } . Ce langage est infiniment dénombrable, et donc tout sous-ensemble L ⊆ Σ ∗ est dénombrable. En outre, il existe de nombreux langages indécidables mais récursivement énumérables dont les compléments ne sont pas récursivement énumérables. Ces langues sont un sous-ensemble de Σ ∗ et sont donc dénombrables.$\Sigma^*$$\Sigma = \{0,1\}$$L \subseteq \Sigma^*$$\Sigma^*$