Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

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

Un ensemble est récursif si et seulement s'il est récursivement énumérable ainsi que son complémentaire.

Voir aussi

• Problème décidable