Récursivement énumérable

En théorie de la calculabilité, un ensemble récursivement énumérable ou semi-décidable est un ensemble qui est le domaine de définition, ou, de façon équivalente, l'image d'une fonction calculable (il faut ajouter l'ensemble vide à la dernière définition pour avoir tout à fait l'équivalence). La notion 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.