Automates cellulaires et réseaux d'automates : le rôle central de l'irrégularité

摘要

L'informatique jusqu'à présent s'est principalement bâtie sur le modèle de la machine de Turing, c'est-à-dire sur la base d'un système appliquant des algorithmes de manière déterministe et séquentielle sur un espace régulier. Par contraste avec cette approche « classique », un autre type d'informatique s'intéresse à la compréhension des systèmes où les irrégularités de toutes sortes, loin d'être un obstacle à éviter, jouent un rôle constructif dans leur évolution. Des exemples sont fournis par les automates cellulaires, les réseaux d'automates (réseaux booléens et réseaux multivalués), qui sont étudiés avec un fonctionnement asynchrone ou probabiliste et conduisent à des dynamiques complexes en dépit de l'utilisation de règles locales simples. On peut étudier comment les perturbations de la structure d'un système dynamique discret conduisent à observer des différences de comportement avec le système « régulier », ou alors tout simplement partir d'un graphe irrégulier de relations entre composants pour comprendre comment calculer sur de tels systèmes, comme dans le cas du calcul en milieu amorphe.