Ensemble récursif
Un article de Wikipédia, l'encyclopédie libre.
 |
Cet article est une ébauche concernant les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).
|
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 tourne pas indéfiniment) est un ensemble récursivement énumérable mais pas récursif.
Un ensemble est récursif si et seulement s'il est récursivement énumérable ainsi que son complémentaire.
[modifier] Exemples
Les ensembles suivants sont récursifs :
- l'ensemble des entiers,
- l'ensemble vide,
- l'ensemble des nombres pairs,
- l'ensemble des nombres premiers,
- l' ensemble des solutions d'une équation diophantienne.
[modifier] Voir aussi
- Problème décidable
