Simulation entre modèles de calcul naturel et modularité des réseaux d’automate

Machines de Turing

Les machines de Turing sont un modèle de calcul que l’on peut représenter comme un robot qui avance et recule sur un ruban infini d’information. Le robot dispose d’une tête de lecture et écriture, d’un état et d’une table de transition. Cette table contient une entrée pour chaque état et chaque valeur de lecture possible; pour chacune de ces paires, cette table retourne une valeur à écrire, un déplacement optionnel et un nouvel état pour la machine de Turing. Mettre à jour la machine repose sur la lecture de cette table et l’application de son résultat. Ce calcul peut ne jamais s’arrêter; cependant on définit souvent des états spéciaux, dit finaux, qui une fois établis vérouillent la machine dans une position et préviennent toute autre modification. C’est une convention pour signifier la fin du calcul d’une machine de Turing. On fait la distinction entre les machines de Turing déterministes et les machines de Turing non déterministes sur le critère qu’une machine de Turing déterminisite dispose toujours d’un et un seul choix en toute circonstance. Une machine de Turing non déterminisite peut au contraire disposer d’une table de transition qui définit au moins deux possibles résultats pour les mêmes circonstances.

Automates cellulaires élémentaires

Les automates cellulaires disposent d’un ensemble régulier de cellules, comme une grille ou une ligne, et chacune de ces cellules contient une valeur. On met à jour un automate cellulaire en appliquant à chaque cellule une fonction locale qui prend en entrée la valeur de la cellule et de ses voisins. Les automates cellulaires élémentaires sont un ensemble de 256 automates cellulaires parmi les plus simples qu’il est possible de définir : ils opèrent sur des configurations en forme de ligne et sur un alphabet binaire, et considèrent une définition de voisinage très simple : les voisins d’une cellule sont elle-même, sa voisine de gauche, et sa voisine de droite. Ainsi, la fonction locale d’une cellule d’un automate cellulaire élémentaire est une fonction qui prend en entrée trois valeurs booléennes et retourne une valeur booléenne. Il n’existe que 22= 256 de ces fonctions, ce qui invite la convention de nommer un automate cellulaire élémentaire par le numéro qui encode la fonction locale qui le définit (WOLFRAM 1984).

Oracles

Une autre façon de définir des classes de complexité est par l’utilisation d’oracles. La notation coNPNP décrit la classe de problèmes qui sont dans coNP lorsque l’on dispose d’un oracle NP. Un oracle est une machine qui permet la résolution immédiate d’un problème de décision. Un problème est dans NPNP, par exemple, si ce problème peut être résolu par une machine de Turing non déterministe qui dispose de la capacité d’appeller un nombre polynomial d’oracles NP. Sous l’hypothèse que la classe P est différente de la classe NP, cette notation d’oracles, utilisée sur les classes P, NP et coNP, permet la définition d’une famille infinie de classes de complexité, appelée la hiérarchie polynomiale.

Intuition générale de la simulation

Lorsque nous étudions des modèles mathématiques, nous discutons souvent des intuitions qui se cachent derrière les définitions. La simulation n’est pas en reste; cette notion, qui a été formellement développée indépendamment dans de nombreux domaines, nous encourage à la généraliser, par l’intuition que si l’ensemble des domaines concernés ont employé ce terme pour parler de choses indépendantes, c’est qu’il existe une perception commune de ce qu’est la simulation. Si cela est avéré, cela nous encouragerait à poursuivre cette perception dans notre recherche d’une définition générale. Quelle est cette perception ? Pour conclure notre travail sur la simulation, nous proposons dans cette section une forme de discussion sur les idées qui entourent la simulation. Nous essayons, informellement, de comprendre ce qui lie la notion de simulation à la notion informelle de calcul; et nous faisons des liens avec l’idée d’émergence. Ce discours informel ne cherche pas à permettre l’élaboration d’un quelconque théorème, ou de tout autre résultat formel mesurable. Il cherche plutôt à organiser un ensemble d’images afin de clarifier notre propre perception du terme de simulation, et peut-être aussi d’élaborer des outils propres à l’éducation et la vulgarisation des notions employées.

La simulation, outil pratique de traduction

Pour guider le développement de cette idée, nous proposons la série d’images suivantes. Alice dispose d’un problème en tête. Il s’agit d’un problème arithmétique. Pour le résoudre, Alice rédige les équations pertinentes sur le papier et trouve la solution. Bob dipose d’un problème arithmétique, et pour le résoudre dispose d’une calculatrice. Bob entre le problème dans la calculatrice et la calculatrice lui donne une réponse, que Bob recopie. Charlie est abandonné sur une planète inconnue, et souhaite résoudre un problème arithmétique. Charlie est devant une machine extra-terrestre inconnue. Fort heureusement, Charlie dispose également d’un manuel d’utilisation, qui permet de se servir de cette machine inconnue comme d’une calculatrice. Charlie traduit son problème en quelque chose que la machine peut comprendre, puis interprète le résultat en quelque chose que lui même comprend, le tout grâce au manuel. Dans ces trois histoires, chacun de nos acteurs effectue un calcul; dans quelle histoire a-t-on un exemple de simulation ? L’histoire de Charlie est construite pour contenir la simulation la plus explicite. C’est le manuel d’instruction qui sert de preuve explicite que la machine extra-terrestre est capable du même calcul qu’une calculatrice. Est-ce la seule simulation que l’on peut extraire de ces histoires ? En plus des machines concrètes décrites dans ces histoires – la calculatrice, la machine extra-terrestre – Alice, Bob et Charlie disposent d’un problème d’arithmétique qui réside dans leur tête. Ce problème peut être résolu; et par notre définition de calcul, tout ce qui permet de le résoudre est alors un objet qui calcule. Cependant, nous estimons que ce problème est aussi lui-même un objet qui calcule car, à l’instar des problèmes de décision mentionnés en section 3.1, il est capable de prendre part dans une réduction avec d’autres problèmes, ou d’être simulé par des modèles. Les histoires d’Alice et Bob sont donc également une histoire de simulation, où la résolution de leur problème présuppose une simulation de l’ensemble des problèmes arithmétiques par les équations et la calculatrice respectivement. Cela est également observable dans l’histoire de Charlie, qui décrit finalement une simulation en deux étapes. Bien que Charlie ne dispose pas de calculatrice, mais seulement de la machine extra-terrestre, le manuel d’utilisation lui permet d’utiliser la complexité de la machine extra-terrestre comme d’une calculatrice : le manuel d’utilisation constitue en vérité une preuve de simulation d’une calculatrice par la machine extra-terrestre. En plus de cette simulation, Charlie utilise cette calculatrice virtuelle pour résoudre son problème. Et comme pour Alice et Bob, cela constitue en soi une simulation, qui est la seconde étape de la résolution du problème de Charlie.

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela rapport-gratuit.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

Résumé
Abstract
Remerciements
Introduction
1 Définitions et notations de base
1.1 Ensembles et séquences
1.2 Fonctions
1.3 Vecteurs
1.4 Graphes
1.5 Fonctions booléennes
1.6 Machines de Turing
1.6.1 Cas déterministe
1.6.2 Cas non déterminisite
1.7 Automates cellulaires élémentaires
1.8 Complexité
1.8.1 Problèmes de décision
1.8.2 Classes de complexité
1.8.3 Oracles
1.8.4 Réduction
1.8.5 Problème fonctionnel
1.8.6 Problème fonctionnel avec promesse
2 Simulation : contexte et généralisations
2.1 Une définition informelle
2.1.1 Simulation d’automates cellulaires
2.1.2 Simulation de réseaux d’automates
2.2 Simulation par forme
2.2.1 Modèles de forme et sous-espaces fonctionnels
2.2.2 Formes
2.2.3 Fonction de forme
2.2.4 Interprétation de forme
2.2.5 Simulation par forme
2.2.6 Critiques
2.3 Préordre de simulation
2.3.1 Définitions
2.3.2 Travail d’adaptation
2.4 Travail futur
3 Simulation : développements et discussion
3.1 Simulation et complexité
3.1.1 Problèmes et systèmes de transition d’états
3.1.2 Classes de simulation
3.2 Intuition générale de la simulation
3.2.1 La simulation et la notion de calcul
3.2.2 La simulation, outil pratique de traduction
3.2.3 Simulation et émergence
3.2.4 Conclusion
4 Réseaux d’automates
4.1 Introduction
4.2 Ensembles d’automates, états et configurations
4.3 Fonctions locales et graphe d’interaction
4.4 Mises à jour et exécutions
4.5 Graphe de la dynamique et attracteurs
4.6 Résultats fondamentaux
5 Modules
5.1 Introduction
5.2 Définitions
5.2.1 Entrées, fonctions locales, modules et graphe d’interaction
5.2.2 Mises à jour, exécutions et graphe de la dynamique
5.2.3 Branchements
5.3 Résultats
5.3.1 Universalité des branchements
5.3.2 Effets des branchements sur la dynamique
5.3.3 Modularité et simulation
5.4 Conclusion
6 Acyclicité
6.1 Les réseaux d’automates acycliques
6.2 Modules acycliques
6.2.1 Fonctions de sortie
6.2.2 Calcul d’une fonction de sortie booléenne
6.2.3 Dynamique des modules acycliques
6.2.4 Caractérisation de la dynamique par les fonctions de sortie
6.3 Modules 1-pour-1
6.3.1 Les registres à décalage à rétroaction linéaire comme des modules 1-pour-1
6.3.2 Les fleurs d’automates comme des modules 1-pour-1
6.4 Optimisation d’un module acyclique
6.4.1 Transformation d’un réseau d’automate en module acyclique
6.4.2 Calcul efficace des fonctions de sortie
6.4.3 Génération d’un module acyclique optimal
6.4.4 Recomposition du réseau final
6.4.5 Cas des modules 1-pour-1
6.5 Conclusion
Perspectives
Bibliographie
Index