Recherchez sur tout Techno-Science.net
       
Techno-Science.net : Suivez l'actualité des sciences et des technologies, découvrez, commentez
 A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | +
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 (La logique mathématique est née à la fin du XIXe siècle de la logique au sens philosophique du terme. Ses débuts furent marqués par la rencontre entre deux idées nouvelles :).

En d'autres termes, il s'agit d'un ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut...) dont le test d'appartenance peut être réalisé par un programme informatique (Un programme informatique est une liste d'ordres indiquant à un ordinateur ce qu'il doit faire. Il se présente sous la forme d'une ou plusieurs séquences d'instructions, comportant souvent des...) qui s'arrête toujours (sans tenir compte des limites de mémoire (D'une manière générale, la mémoire est le stockage de l'information. C'est aussi le souvenir d'une information.) ou de temps (Le temps est un concept développé par l'être humain pour appréhender le changement dans le monde.) de calcul des ordinateurs actuellement réalisables).

Un ensemble est récursif si et seulement s'il est récursivement énumérable (Intuitivement un ensemble est récursivement énumérable s'il existe un procédé mécanique (en gros qui peut être réalisé par un ordinateur) qui liste ses éléments....) ainsi que son complémentaire.

Exemples

Les ensembles suivants sont récursifs :

  • l'ensemble des entiers,
  • l'ensemble vide (En mathématiques, l'ensemble vide est l'ensemble ne contenant aucun élément.),
  • l'ensemble des nombres pairs,
  • l'ensemble des nombres premiers,
  • l' ensemble des solutions d'une équation (En mathématiques, une équation est une égalité qui lie différentes quantités, généralement pour poser le problème de leur identité. Résoudre l'équation consiste à déterminer toutes les façons de donner à certaines...) diophantienne.
Source: Wikipédia publiée sous licence CC-BY-SA 3.0.

Vous pouvez soumettre une modification à cette définition sur cette page. La liste des auteurs de cet article est disponible ici.
Page générée en 0.084 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - Informations légales