Déployeur universel

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éfinition

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 régler 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 machines

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] :

Dans d’autres domaines

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érences

  1. 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)
  • Portail de l'informatique théorique
  • Portail des mathématiques
  • Portail de la logique
  • Portail de la physique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.