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.
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.
Dans la terminologie des systèmes formels, la définition suivante est équivalente :
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.
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 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 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.
Problème décidable
Dixième problème de Hilbert
Cours sur la récursivité
Catégorie:Logiqu
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a
This course constitutes an introduction to theory of computation. It discusses the basic theoretical models of computing (finite automata, Turing machine), as well as, provides a solid and mathematica
The student will learn state-of-the-art algorithms for solving differential equations. The analysis and implementation of these algorithms will be discussed in some detail.
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. Ce type d'ensemble correspond à un concept effectif de John R.
vignette|L'animation illustre une machine impossible : il n'y a pas de machine qui lit n'importe quel code source d'un programme et dit si son exécution termine ou non. En théorie de la calculabilité, le problème de l'arrêt est le problème de décision qui détermine, à partir d'une description d'un programme informatique, et d'une entrée, si le programme s'arrête avec cette entrée ou non.
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do the job of the function, i.e. given an input of the function domain it can return the corresponding output. Computable functions are used to discuss computability without referring to any concrete model of computation such as Turing machines or register machines.