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. On a tout de même le résultat suivant : 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 :

  • tout ensemble fini (l'ensemble vide ∅ étant un exemple trivial) ;
  • l'ensemble des multiples d'un entier k (les nombres entiers, les nombres pairs, etc.) ;
  • l'ensemble des nombres premiers ;
  • l'ensemble des solutions d'une équation diophantienne donnée.


Les ensembles suivants sont non récursifs :

  • l'ensemble des équations diophantiennes qui ont une solution entière (par contre il est récursivement énumérable).


On ne sait actuellement toujours pas si le multiensemble des termes de la suite de Syracuse de terme initial u0 = k est récursif pour k > 0 quelconque (sous-entendu \forall k \in \mathbb{N}^*). Concrètement, il existe peut-être une valeur de k > 0 telle qu'on ne puisse pas décider de l'appartenance de 1 (en un temps fini) dans le multiensemble des termes de la suite de Syracuse de premier terme u0 = k. La conjecture de Syracuse prétend le contraire, mais reste encore à ce jour indémontrée. En revanche, il est récursivement énumérable par définition.

Voir aussi

Liens

Cours sur la récursivité


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

  • 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

  • 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”