Récursivement Énumérable

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.