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 ${\displaystyle (i,e,s)\in \mathbb {N} ^{3}}$ en utilisant la fonction de couplage de Cantor ;
2. par un codage, associer à ${\displaystyle i}$ une entrée ${\displaystyle I_{i}}$ ;
3. par un codage, associer à ${\displaystyle e}$ une machine ${\displaystyle M_{e}}$ ;
4. simuler ${\displaystyle M_{e}}$ sur l’entrée ${\displaystyle I_{i}}$ pendant ${\displaystyle s}$ é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] :

• le nombre de transformations dans un système de réécriture ;
• le nombre de récursions dans l’évaluation d’une fonction récursive ;
• le nombre d’étapes de calcul d’une machine de Turing.

Codage des machines et des entrées

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, 26 septembre 2016, 254 p. (lire en ligne), p. 145-146
2. (en) Péter Gács, Theory of computation, 17 septembre 2008, 8 p. (lire en ligne), p. 1
3. Jean-Paul Delahaye, « Logique et calcul : Le monde des machines », Pour la Science, n^o 243,‎ janvier 1998, 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