Classe d'ensembles (langages) pour lesquels il existe une machine de Turing qui énumère tous les éléments ou, de façon équivalente, accepte exactement les entrées du jeu en s'arrêtant et en acceptant ; la machine peut ne pas s'arrêter sur les non‑membres.

Principe

Récursivement énumérable (r.e.) signifie semi-décidable : il existe une procédure effective qui, pour chaque élément, finit par s'arrêter et signaler l'appartenance, alors que les non‑membres ne conduisent pas nécessairement à l'arrêt ; l'énumération et la reconnaissance sont des caractérisations équivalentes.

Démonstration

L'ensemble des théorèmes démontrables par un système formel axiomatisable calculablement est récursivement énumérable : une machine de Turing peut énumérer systématiquement toutes les preuves et ainsi lister toutes les formules démontrables.

Mauvaise application

Prendre un ensemble r.e. pour décidables parce que ses membres peuvent être listés ; interpréter l'absence d'arrêt sur un non‑membre comme une preuve de non-appartenance plutôt que comme absence de preuve.

Conséquence

L'appartenance à un ensemble r.e. peut être confirmée en exécutant l'énumérateur/recognizer jusqu'à l'acceptation ; cependant, l'absence d'acceptation après de longues exécutions n'apporte pas de réponse négative définitive sans information supplémentaire.

Inversion

Co-récursivement énumérable : ensembles dont le complément est r.e. ; décidables : ensembles à la fois r.e. et co-r.e.

Limite

Défini par rapport à un encodage standard et à un modèle (machines de Turing) ; exclut les machines avec oracle sauf indication contraire ; propriétés de clôture incluent l'union et l'intersection avec des ensembles décidables mais pas le complément en général.

Tension sémantique

Tension entre r.e. et décidabilité : la listabilité et la reconnaissabilité captent l'information positive tandis que la décidabilité exige des procédures positives pour les cas négatifs aussi.

Synthèse

Le concept récursivement énumérable saisit la reconnaissabilité algorithmique positive : les membres peuvent être produits ou reconnus de façon effective, tandis que leurs complémentaires peuvent rester hors de confirmation algorithmique sans structure supplémentaire.