Déployeur universel

machine abstraite simulant l’exécution de toutes les autres machines de son modèle de calcul sur toutes les entrées possibles

Un déployeur universel, appelé parfois dovetailer, est une machine abstraite simulant l’exécution de toutes les autres machines de son modèle de calcul sur toutes les entrées possibles. Par extension, la technique du déploiement universel consiste à s’appuyer sur l’existence d’une telle machine pour démontrer des propriétés en théorie de la calculabilité[1].

DéfinitionModifier

Le principal obstacle à la construction d’un déployeur universel est l’existence de machines qui bouclent indéfiniment et empêchent le déployeur de passer à la simulation des autres machines. Le schéma classique pour pallier ce problème est le suivant[1] :

  1. énumérer les triplets d’entiers   en utilisant la fonction de couplage de Cantor ;
  2. par un codage, associer à   une entrée   ;
  3. par un codage, associer à   une machine   ;
  4. simuler   sur l’entrée   pendant   étapes.

Notion de temps pour les machinesModifier

Le schéma précédent nécessite de pouvoir simuler une machine pendant un nombre maximal fixé d’étapes. Cette notion de temps est propre au modèle de calcul choisi, par exemple[2] :

Codage des machines et des entréesModifier

Dans d’autres domainesModifier

Sous la théorie du computationnalisme, qui postule que l’esprit humain est une machine à calculer complexe, il existe une étape dans l’exécution d’un déployeur universel durant laquelle le fonctionnement d’un cerveau humain est parfaitement simulé[3].

Par ailleurs, un déployeur universel gère toutes les histoires computationnelles[style à revoir] possibles et rejoint la théorie des mondes multiples d'Everett.

RéférencesModifier

  1. a et b Akim Demaille, Pierre Senellart et François Yvon, Théorie des langages, , 254 p. (lire en ligne), p. 145-146
  2. (en) Péter Gács, Theory of computation, , 8 p. (lire en ligne), p. 1
  3. Jean-Paul Delahaye, « Logique et calcul : Le monde des machines », Pour la Science, no 243,‎ , p. 102 (ISSN 0153-4092, lire en ligne)