Ensemble récursif

En théorie de la calculabilité, un ensemble récursif ou ensemble décidable est un ensemble d'entiers (ou d'éléments facilement codables dans les entiers) dont la fonction caractéristique est une fonction récursive au sens de la logique mathématique.

En d'autres termes, il s'agit d'un ensemble dont le test d'appartenance peut être réalisé par un programme informatique qui s'arrête toujours (sans tenir compte des limites de mémoire ou de temps de calcul des ordinateurs actuellement réalisables).

Si un ensemble est récursif alors il est récursivement énumérable. Mais la réciproque est fausse : par exemple, d'après le problème de l'arrêt, l'ensemble des programmes qui s'arrêtent (les programmes qui ne tournent pas indéfiniment) est un ensemble récursivement énumérable mais pas récursif. On a tout de même le résultat suivant : un ensemble est récursif si et seulement s'il est récursivement énumérable ainsi que son complémentaire.

Exemples

Les ensembles suivants sont récursifs :

• tout ensemble fini (l'ensemble vide ∅ étant un exemple trivial) ;
• l'ensemble des multiples d'un entier k (les nombres entiers, les nombres pairs, etc.) ;
• l'ensemble des nombres premiers ;
• l'ensemble des solutions d'une équation diophantienne donnée.

Les ensembles suivants sont non récursifs :

• l'ensemble des équations diophantiennes qui ont une solution entière (par contre il est récursivement énumérable).

On ne sait actuellement toujours pas si le multiensemble des termes de la suite de Syracuse de terme initial u₀ = k est récursif pour k > 0 quelconque (sous-entendu $\forall k \in \mathbb{N}^*$). Concrètement, il existe peut-être une valeur de k > 0 telle qu'on ne puisse pas décider de l'appartenance de 1 (en un temps fini) dans le multiensemble des termes de la suite de Syracuse de premier terme u₀ = k. La conjecture de Syracuse prétend le contraire, mais reste encore à ce jour indémontrée. En revanche, il est récursivement énumérable par définition.

Voir aussi

• Problème décidable
• Dixième problème de Hilbert

Liens

Cours sur la récursivité