Ensemble récursif
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

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

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...) 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 données de base, devant...) 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. On dirait aussi qu'il...) 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 à...) diophantienne.
Page générée en 0.202 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
Partenaire: HD-Numérique