Loading AI tools
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].
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 en utilisant la fonction de couplage de Cantor ;
- par un codage, associer à une entrée ;
- par un codage, associer à une machine ;
- 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] :
- 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
Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue pour ajouter des méthodes permettant de coder des machines ou des entrées sous forme d’entier naturel !
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.
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
