Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Récursivement énumérable

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.

Voir aussi

• Ensemble récursif