Ensemble récursif

En théorie de la calculabilité, un ensemble récursif ou ensemble décidable ou ensemble calculable 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.

Un ensemble dont un ordinateur peut, pour tous les entiers, déterminer l'appartenance ou non, est un ensemble récursif.

En d'autres termes, un ensemble $E$ est récursif si, et seulement si, il existe une machine de Turing $T$ (un programme informatique) permettant de déterminer en un temps fini si un entier quelconque est dans $E$ ou pas.

$\forall n\in \mathbb {N}$
$T(n)=OUI\ {\mbox{si}}\ n\in E$
$T(n)=NON\ {\mbox{si}}\ n\notin E$

Tout ensemble récursif est aussi récursivement énumérable, mais la réciproque est fausse.

Les ensembles récursifs correspondent à un concept effectif de John R. Myhill, qui sont les concepts qui peuvent être définis extensivement et sans ambiguïté^{[source insuffisante]}.

Propriétés

• Un ensemble A est récursif si et seulement si A et son complémentaire sont récursivement énumérables.
• Si A et B sont récursifs, alors A ∩ B et A ∪ B sont récursifs.
• L'image réciproque d'un ensemble récursif par une fonction récursive totale est récursif.
• Les ensembles récursifs sont exactement les ensembles $\Delta _{1}^{0}$ de la hiérarchie arithmétique.

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 récursivement énumérables mais pas récursifs :

• l'ensemble des équations diophantiennes qui ont une solution entière ;
• l'ensemble des programmes qui s'arrêtent (les programmes qui ne tournent pas indéfiniment) : voir « Problème de l'arrêt ».
• l'ensemble des propositions prouvables dans l'arithmétique de Peano, ou dans la théorie des ensembles de Zermelo-Fraenkel.

Les ensembles suivants ne sont ni récursifs, ni récursivement énumérables :

• l'ensemble des programmes s'arrêtant sur toutes leurs entrées.
• l'ensemble des propositions vraies dans le langage de l'arithmétique de Peano.

On ne sait actuellement toujours pas si le multiensemble des termes de la suite de Syracuse de terme initial $u_{0}=k$ est récursif pour $k>0$ quelconque (sous-entendu : $k$ entier). La conjecture de Syracuse prétend que ce multiensemble est récursif, mais reste encore à ce jour indémontrée. En revanche, il est récursivement énumérable par définition.

Voir aussi

Articles connexes

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

Lien externe

Cours sur la récursivité