Récursivement énumérable - Définition

La définition de Turing de l'énumérabilité

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

Équivalence des deux définitions de Turing

• S'il existe une machine qui affiche tous les éléments d'un ensemble, il est facile de savoir si un mot appartient ou non à l'ensemble. Attendre qu'il s'affiche. S'il s'affiche, il appartient à l'ensemble. S'il n'appartient pas à l'ensemble, il ne s'affichera pas.
• Réciproquement, s'il existe une machine M1 qui se termine quand le mot entré appartient à l'ensemble, il est possible d'obtenir une machine M2 qui affiche tous les éléments de l'ensemble. On ordonne tout d'abord tous les mots : appelons-les A,B,C.... Voici l'algorithme de M2.
  • Lancer M1 pendant un pas sur A.
  • Lancer M1 pendant deux pas sur A, puis deux pas sur B.
  • Lancer M1 pendant trois pas sur A, puis trois pas sur B, puis trois pas sur C.
  • Continuer...

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.

Exemples

D'une manière générale, tout algorithme A₁ 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 A₂ terminant et répondant Oui pour les entiers de l'ensemble, et répondant Non pour les entiers n'appartenant pas à l'ensemble.