Ensemble récursif

Dans la terminologie des systèmes formels, la définition suivante est équivalente[1] :

${\displaystyle E}$ est récursif si et seulement si il existe un système formel correct et complet pour les énoncés de la forme « ${\displaystyle n}$ est dans ${\displaystyle E}$ » et de la forme « ${\displaystyle n}$ n'est pas dans ${\displaystyle E}$ ».

• 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.

Les ensembles suivants sont récursifs :

• tout ensemble fini (l'ensemble vide ∅ étant un exemple trivial) ;
• l'ensemble des multiples d'un entier ${\displaystyle 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 ».

On ne sait actuellement toujours pas si le multiensemble des termes de la suite de Syracuse de terme initial ${\displaystyle u_{0}=k}$ est récursif pour ${\displaystyle k>0}$ quelconque (sous-entendu : ${\displaystyle k}$ entier). 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.