Simulation contexte et généralisations

La simulation est un concept singulier dans le calcul naturel. Bien que son intuition, la capacité de la reproduction du calcul, semble universelle, les définitions dont nous disposons sont toujours propres aux modèles qui les concernent. Ce schisme vient certainement du fait que nous n’avons jamais de définition unifiée de ce qu’est un calcul ; nous sommes réduits dans la pratique à ne définir que des exemples locaux de son apparition. En est-il de même avec la simulation, avec qui le calcul semble hautement apparenté ? Nous ne sommes pas les premiers à nous poser la question (BOAS 2014). Il est désirable d’obtenir une telle définition générale si elle existe, simplement car l’unifica- tion d’une partie des méthodes d’un large domaine de recherche est à la clé. Devant une question aussi ambitieuse, nous adoptons la démarche de décrire les intuitions qui semblent être clés dans les définitions de simulation dont nous disposons dans certains modèles de calcul comme les automates cellulaires, puis de poursuivre la généralisation de ces intuitions vers, nous l’espérons, une définition applicable dans un cadre plus général.La notion de simulation est fortement liée à la notion de l’universalité, dont il existe des variantes. La plus classique d’entre elles, l’universalité Turing, prend racine dans la thèse de Church-Turing, des deux mathématiciens qui, dans les années 1930, déclarent indépendamment avoir défini des modèles de calcul qui ont la faculté de reproduire tout calcul qu’un humain peut opérer si on lui procure une quantité infinie de feuilles, de crayon et de temps. Bien que cette thèse n’ait jamais été prouvée (car trop informelle), elle est communément admise et n’a jamais été contredite depuis 90 ans. Les machines de Turing sont parmi les exemples les plus connus de modèles dit Turing universels.

Une fois admise l’universalité Turing d’un modèle, il est possible d’étendre cette universalité à des modèles parfois de natures complètement différentes. Pour ce faire, on utilise la notion de simulation. La simulation est une relation entre modèles de calcul qui s’applique entre un modèle simulateur et un modèle simulé. En pratique, tout calcul opérable par la machine simulée peut être reconstruit comme un calcul opérable par la machine simulatrice, de façon à ce que le calcul de la machine simu- latrice permette de prédire tout aspect du calcul simulé. Une telle relation se devra d’être réflexive et transitive : une machine doit être capable de reproduire son propre calcul, ce qui est trivial ; si une machine en simule une seconde qui en simule une troisième, alors elle simule la troisième. Ces deux propriétés font de la simulation un pré-ordre.Une autre variante de l’universalité est nommée universalité intrinsèque, et ne fait sens que lorsque l’on examine la capacité d’un modèle à simuler tout autre modèle inclus dans la même famille. Cela est généralement dit d’un modèle spécifiquement capable d’une grande souplesse calculatoire. C’est le cas de certaines machines de Turing universelles, qui sont conçues pour accepter et reproduire le code décrivant n’importe quelle autre machine : une telle machine est intrinsèquement universelle dans la famille des machines de Turing. L’universalité intrinsèque ne découle cepen- dant pas toujours de l’universalité Turing. Pour être intrinsèquement universel, un modèle devra souvent opérer son calcul en exploitant les propriétés intrinsèques de la famille de modèles utilisés. Les conditions spécifiques de ces propriétés changent avec la famille considérée, mais en général impliquent une simulation plus efficace. Afin de se construire une intuition du fonctionnement de la simulation, examinons des définitions tirées de la littérature.

Les automates cellulaires sont une famille de modèles centrale dans le calcul na- turel. Une présentation sommaire d’une fraction emblématique de ces modèles, les automates cellulaires élémentaires, est faite en section 1.7. cellules de l’automate simulé par des regroupements de cellules dans l’automate simulateur. La figure 2.1 détaille l’exemple de la simulation de la règle 184 par la règle 134 : ici, chaque automate de la règle 184 est remplacé par 2 cellules dans l’auto- mate 134. On note également qu’une mise à jour supplémentaire est nécessaire entre chaque étape de la simulation. En d’autres termes, cette simulation opère par la mise à l’échelle dans l’espace et le temps de la règle 134. En choisissant une configuration initiale donnée par le bon encodage, la règle 134 se trouve reproduire “tous les calculs” de la règle 184.