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

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

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

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

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.