Intuitivement un ensemble est récursivement énumérable s'il existe un procédé mécanique (en gros qui peut être réalisé par un ordinateur) qui liste ses éléments. On dirait aussi qu'il existe un "programme" qui peut dire si un élément appartient à l'ensemble. Le même programme ne peut rien dire si l'élément n'appartient pas à l'ensemble.
En théorie de la calculabilité, un ensemble récursivement énumérable ou semi-décidable est un ensemble d'entiers (ou de codage aisé dans les entiers) tel qu'il existe une machine de Turing qui termine en acceptant sur l'entrée n si et seulement si n appartient à l'ensemble. De façon équivalente, il s'agit d'un ensemble tel qu'il existe une machine de Turing qui écrit successivement tous les éléments de l'ensemble (dans un ordre quelconque), d'où le terme (les fonctions récursives au sens de la logique mathématique sont les fonctions calculables par les machines de Turing).
Les ensembles récursivement énumérables ne sont pas forcément des ensembles récursifs : ainsi, l'ensemble des numéros des machines de Turing qui terminent sur l'entrée vide est clairement récursivement énumérable, mais n'est pas récursif, en vertu du théorème de Rice.
On se gardera de confondre les ensembles récursivement énumérables avec les ensembles infinis dénombrables
Si M1 arrive à un état final, noter l'entrée comme faisant partie de l'ensemble. On obtient ainsi M2 qui écrit tous les éléments de l'ensemble, et eux seulement.
D'une manière générale, tout algorithme A1 admettant un paramètre entier n définit un ensemble récursivement énumérable, à savoir l'ensemble des entiers pour lequel l'algorithme se termine.
On ignore le plus souvent si un tel ensemble est récursif, c’est-à-dire s'il est possible de concevoir un algorithme A2 terminant et répondant Oui pour les entiers de l'ensemble, et répondant Non pour les entiers n'appartenant pas à l'ensemble.