Récursivement énumérable
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

La définition de Turing de l'énumérabilité

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 existe un "programme" qui peut dire si un élément appartient à l'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 être comprise comme un tout »,...). Le même programme ne peut rien dire si l'élément n'appartient pas à l'ensemble.

En théorie (Le mot théorie vient du mot grec theorein, qui signifie « contempler, observer, examiner ». Dans le langage courant, une théorie est une idée ou...) de la calculabilité (La théorie de la calculabilité (appelée aussi parfois théorie de la récursion) est une branche de la logique mathématique et de l'informatique théorique. Alors que la notion intuitive de...), un ensemble 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...) ou semi-décidable est un ensemble d'entiers (ou de codage (De façon générale un codage permet de passer d'une représentation des données vers une autre.) aisé dans les entiers) tel qu'il existe une machine de Turing qui termine en acceptant sur l'entrée n si et seulement si n appartient à l'ensemble. De façon équivalente, il s'agit d'un ensemble tel qu'il existe une machine de Turing qui écrit successivement tous les éléments de l'ensemble (dans un ordre quelconque), d'où le terme (les fonctions récursives au sens (SENS (Strategies for Engineered Negligible Senescence) est un projet scientifique qui a pour but l'extension radicale de l'espérance de vie humaine. Par une évolution progressive allant du ralentissement du vieillissement,...) 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 :) sont les fonctions calculables par les machines de Turing).

Les ensembles récursivement énumérables ne sont pas forcément des ensembles récursifs : ainsi, l'ensemble des numéros des machines de Turing qui terminent sur l'entrée vide (Le vide est ordinairement défini comme l'absence de matière dans une zone spatiale.) est clairement récursivement énumérable, mais n'est pas récursif, en vertu du théorème de Rice (En théorie de la calculabilité, le théorème de Rice dit que toute propriété non triviale (c.-à-d. qui n'est pas toujours vraie ou toujours fausse) sur la sémantique...).

On se gardera de confondre les ensembles récursivement énumérables avec les ensembles infinis dénombrables

Équivalence des deux définitions de Turing

  • S'il existe une machine qui affiche tous les éléments d'un ensemble, il est facile de savoir si un mot appartient ou non à l'ensemble. Attendre qu'il s'affiche. S'il s'affiche, il appartient à l'ensemble. S'il n'appartient pas à l'ensemble, il ne s'affichera pas.
  • Réciproquement, s'il existe une machine M1 qui se termine quand le mot entré appartient à l'ensemble, il est possible d'obtenir une machine M2 qui affiche tous les éléments de l'ensemble. On ordonne tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) d'abord tous les mots : appelons-les A,B,C.... Voici l'algorithme de M2.
    • Lancer M1 pendant un pas sur A.
    • Lancer M1 pendant deux pas sur A, puis deux pas sur B.
    • Lancer M1 pendant trois pas sur A, puis trois pas sur B, puis trois pas sur C.
    • Continuer...

Si M1 arrive à un état final, noter l'entrée comme faisant partie de l'ensemble. On obtient ainsi M2 qui écrit tous les éléments de l'ensemble, et eux seulement.

Exemples

D'une manière générale, tout algorithme A1 admettant un paramètre (Un paramètre est au sens large un élément d'information à prendre en compte pour prendre une décision ou pour effectuer un calcul.) entier n définit un ensemble récursivement énumérable, à savoir l'ensemble des entiers pour lequel l'algorithme se termine.

On ignore le plus souvent si un tel ensemble est récursif, c’est-à-dire s'il est possible de concevoir un algorithme A2 terminant et répondant Oui pour les entiers de l'ensemble, et répondant Non pour les entiers n'appartenant pas à l'ensemble.

Page générée en 0.037 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 - A propos - Informations légales
Partenaire: HD-Numérique