Ensemble récursif

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.

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 $E$ est récursif si, et seulement si, il existe une machine de Turing $T$ (un programme informatique) permettant de déterminer en un temps fini si un entier quelconque est dans $E$ ou pas^[1].

\forall n\in \mathbb {N}

T(n)=OUI\ {\mbox{si}}\ n\in E

T(n)=NON\ {\mbox{si}}\ n\notin E

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 comprend de mieux en mieux avec le temps, sans qu'il soit jamais possible de le cerner complètement^[1].

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

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

E

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

Propriétés[modifier | modifier le code]

Un ensemble A est récursif si et seulement si A et son complémentaire sont récursivement énumérables.
Si A et B sont récursifs, alors A ∩ B et A ∪ B sont récursifs.

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 $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 récursivement énumérables mais pas récursifs :

l'ensemble des équations diophantiennes qui ont une solution entière ;
l'ensemble des programmes qui s'arrêtent (les programmes qui ne tournent pas indéfiniment) : voir « Problème de l'arrêt ».

On ne sait actuellement toujours pas si le multiensemble des termes de la suite de Syracuse de terme initial $u_{0}=k$ est récursif pour $k>0$ quelconque (sous-entendu : $k$ 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.

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

↑ ^{a b et c} Jean-Paul Delahaye, Information, Complexité et Hasard, Hermes Science Publishing, 1999 (ISBN 2-7462-0026-0) p. 74.

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Problème décidable
Dixième problème de Hilbert

Lien externe[modifier | modifier le code]

Cours sur la récursivité

Portail de l'informatique théorique

[Delahaye-1] {a b et c} Jean-Paul Delahaye, Information, Complexité et Hasard, Hermes Science Publishing, 1999 (ISBN 2-7462-0026-0) p. 74.

[1]

v · m Informatique théorique
Codage	Codage de l'information Compression de données Chiffrement Cryptanalyse Cryptographie Théorie de l'information
Modèles de calcul	Calculabilité Décidabilité et indécidabilité Ensemble récursif Problème de l'arrêt Ensemble récursivement énumérable Machine de Turing Thèse de Church Automate cellulaire Réseau de neurones artificiels Réduction polynomiale Problème NP-complet Principe de Church-Turing-Deutsch
Algorithmique	Algorithmique Algorithme glouton Algorithme probabiliste Algorithme génétique Complexité algorithmique Analyse d'algorithme Diviser pour régner Heuristique Programmation dynamique Géométrie algorithmique Algorithmes de tri Algorithmique du texte Exploration de données Science des données Apprentissage profond Test de primalité Structure de données Arbre enraciné Concurrence Parallélisme
Syntaxe	Réécriture Compilation Expression régulière Grammaire formelle Langage rationnel Ensemble rationnel Théorie des langages Théorie des automates Automate fini Automate sur les mots infinis Automate d'arbres Automate à pile Hiérarchie de Chomsky Linguistique informatique
Sémantique	Interprétation abstraite Méthodes formelles Vérification de modèles Sémantique des langages de programmation Sémantique dénotationnelle Sémantique axiomatique Sémantique opérationnelle
Logique mathématique	Assistant de preuve Calcul des prédicats Correspondance de Curry-Howard Fonction récursive Lambda-calcul Théorèmes d'incomplétude de Gödel Théorie des types
Mathématiques discrètes	Combinatoire Algorithme du simplexe Optimisation combinatoire Théorie des graphes Algorithmes de la théorie des graphes Recherche opérationnelle Théorie de la décision Analyse numérique