Récursivement énumérable

Carte Commune · n° 435749

En théorie de la calculabilité, un ensemble E d'entiers naturels est récursivement énumérable ou semi-décidable si : il existe un algorithme qui prend un entier naturel en entrée, et qui s'arrête exactement sur les entiers de E ; ou, de manière équivalente : il existe un procédé algorithmique qui, au cours de son fonctionnement, énumère en sortie tous les entiers de E et seulement ceux-ci (il est possible, et même nécessaire quand E est infini, qu'il ne s'arrête pas). Cette notion, définie pour les nombres entiers, se généralise aux couples et n-uplets d'entiers et de façon plus générale aux objets qui peuvent se coder dans les entiers, mots d'un langage, formules logiques, etc. Par exemple, on montre que l'ensemble des programmes informatiques que l'on peut écrire dans un langage donné, ou que l'ensemble des théorèmes d'une théorie finiment axiomatisable est récursivement énumérable. Les ensembles récursifs, on dit aussi décidables, sont tous récursivement énumérables mais la réciproque...

Lire sur Wikipédia · Image Jean-Christophe BENOIST, CC BY-SA 4.0