Ensemble récursif
Un article de Wikipédia, l'encyclopédie libre.
Vous avez de  |
Portail de l'informatique – Accédez aux articles de Wikipédia concernant l’informatique. |
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).
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
[modifier] Voir aussi
- Problème décidable
