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 Portail de l’informatique
Ce document provient de « Ensemble r%C3%A9cursif ».

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

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”