Ensemble récursif

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant les mathématiques
Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Un ensemble dont un ordinateur peut déterminer l'appartenance ou non de tous les entiers est un 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, un ensemble est récursif si, et seulement si, il existe une machine de Turing (un programme informatique), permettant de déterminer en un temps fini si un entier quelconque est dans ou pas[1].



Si un ensemble est récursif alors il est récursivement énumérable. En revanche, 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.

Ce type d'ensemble correspond à un concept effectif de John R. Myhill, qui sont les concepts qui peuvent être définis extensivement et sans ambiguïté. La notion d'ensemble récursivement énumérable (non récursif) est plutôt un concept constructif, dont le contenu se précise et se comprends de mieux en mieux avec le temps, sans qu'il soit jamais possible de le cerner complètement[1].

Définition en terme de système formel[modifier | modifier le code]

Dans la terminologie des systèmes formels, la définition suivante est équivalente[1] :

est récursif si et seulement si il existe un système formel correct et complet pour les énoncés de la forme " est dans " et de la forme " n'est pas dans "

Exemples[modifier | modifier le code]

Les ensembles suivants sont récursifs :

  • tout ensemble fini (l'ensemble vide ∅ étant un exemple trivial) ;
  • l'ensemble des multiples d'un entier (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 est récursif pour quelconque (sous-entendu : entier). 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[modifier | modifier le code]

Liens[modifier | modifier le code]

Cours sur la récursivité

Notes et références[modifier | modifier le code]

  1. a, b et c Jean-Paul Delahaye, Information, Complexité et Hasard, Hermes Science Publishing, (ISBN 2-7462-0026-0)Voir et modifier les données sur Wikidata p. 74