Récursivement énumérable

En théorie de la calculabilité, un ensemble 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 ; 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 et seulement ceux-ci (il est possible, et même nécessaire quand 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 est fausse. Par exemple l'ensemble des programmes informatiques qui s'arrêtent est un ensemble récursivement énumérable et non récursif de par l'indécidabilité du problème de l'arrêt. Dit autrement si un ensemble est décidable, il est semi-décidable, mais les deux notions ne sont pas équivalentes. En arithmétique, on montre que les ensembles récursivement énumérables sont les ensembles définissables par divers types de formules n'utilisant essentiellement que des quantificateurs existentiels en tête, l'exemple le plus fin de ce genre de résultat étant la caractérisation de ces ensembles comme ensembles diophantiens, caractérisation qui conduit directement au théorème de Matiiassevitch. En théorie de la complexité, la classe des langages récursivement énumérables est notée RE. S'il existe une machine M1 qui affiche au cours de son fonctionnement tous les éléments d'un ensemble E et rien que ces éléments, on fabrique une machine M2 qui prend en entrée un mot n, lance le calcul de M1 et attend que n s'affiche. S'il s'affiche, il appartient à l'ensemble, et M2 s'arrête.