Ensemble Récursif
- Ensemble Récursif
-
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).
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 tournent 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.
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 donnée.
- En revanche, l'ensemble des équations diophantiennes qui ont une solution entière est récursivement énumérable, mais non récursif (dixième problème de Hilbert).
Voir aussi
Liens
Cours sur la récursivité
Portail de l’informatique
Catégories : Logique mathématique | Calculabilité
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Ensemble Récursif de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Ensemble recursif — 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… … Wikipédia en Français
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… … Wikipédia en Français
Recursif — Récursif Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom … Wikipédia en Français
Récursif — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « Récursif », sur le Wiktionnaire (dictionnaire universel) Récursivité : une présentation générale… … Wikipédia en Français
Ensemble récursivement énumérable — Récursivement énumérable En théorie de la calculabilité, un ensemble récursivement énumérable ou semi décidable est un ensemble qui est le domaine de définition, ou, de façon équivalente, l image d un fonction calculable (il faut ajouter l… … Wikipédia en Français
Langage Récursif — En mathématiques, en logique et en informatique, un langage récursif est un type de langage formel qui est aussi appelé récursif, décidable, ou Turing decidable. Définitions Il y a plusieurs définitions équivalentes de langage récursif. On peut… … Wikipédia en Français
Langage recursif — Langage récursif En mathématiques, en logique et en informatique, un langage récursif est un type de langage formel qui est aussi appelé récursif, décidable, ou Turing decidable. Définitions Il y a plusieurs définitions équivalentes de langage… … Wikipédia en Français
Langage récursif — En mathématiques, en logique et en informatique, un langage récursif est un type de langage formel qui est aussi appelé récursif, décidable, ou Turing decidable. Définitions Il y a plusieurs définitions équivalentes de langage récursif. On peut… … Wikipédia en Français
Algorithme Récursif — Les algorithmes récursifs et les fonctions récursives sont fondamentaux en informatique. Un algorithme est dit récursif s il s appelle lui même. Les premiers langages de programmation qui ont introduit la récursivité sont LISP et Algol 60 et… … Wikipédia en Français
Algorithme recursif — Algorithme récursif Les algorithmes récursifs et les fonctions récursives sont fondamentaux en informatique. Un algorithme est dit récursif s il s appelle lui même. Les premiers langages de programmation qui ont introduit la récursivité sont LISP … Wikipédia en Français
