Des articles

12 : Automates Cellulaires II - Analyse - Mathématiques


  • 12.1 : Tailles de l'espace de règles et de l'espace de phase
    L'une des caractéristiques uniques des modèles CA typiques est que le temps, l'espace et les états des cellules sont tous discrets. En raison d'une telle discrétion, le nombre de toutes les fonctions de transition d'état possibles est fini, c'est-à-dire qu'il n'y a qu'un nombre fini d'« univers » possibles dans un cadre d'AC donné. De plus, si l'espace est fini, toutes les configurations possibles de l'ensemble du système sont également énumérables. Cela signifie que, pour des paramètres CA raisonnablement petits, on peut effectuer une recherche exhaustive de l'ensemble de l'espace de règles o
  • 12.2 : Visualisation de l'espace des phases
    Si l'espace de phase d'un modèle CA n'est pas trop grand, vous pouvez le visualiser en utilisant la technique dont nous avons parlé à la section 5.4. De telles visualisations sont utiles pour comprendre la dynamique globale du système, en particulier en mesurant le nombre de bassins d'attraction séparés, leurs tailles et les propriétés des attracteurs.
  • 12.3 : Approximation du champ moyen
    Les comportements des modèles CA sont complexes et hautement non linéaires, il n'est donc pas facile d'analyser leur dynamique d'une manière mathématiquement élégante. Mais encore, il existe des méthodes analytiques disponibles. L'approximation du champ moyen est l'une de ces méthodes analytiques. C'est une méthode analytique puissante pour faire une prédiction approximative du comportement macroscopique d'un système complexe.
  • 12.4 : Analyse du groupe de renormalisation pour prédire les seuils de percolation
    La méthode analytique suivante consiste à étudier les seuils critiques pour que la percolation se produise dans les processus de contact spatial, comme ceux du modèle d'AC épidémique/feu de forêt discuté à la section 11.5. Le seuil de percolation peut être estimé analytiquement par une méthode appelée analyse de groupe de renormalisation.

Automates cellulaires

4.9 Automates réseau cellulaires : un développement pour l'avenir ?

Les automates cellulaires en réseau (ANC) sont un développement assez récent des automates cellulaires [ Wol02 ]. Voici un essai de définition :

Les cellules sont définies comme des nœuds dans un réseau de connexions. Contrairement aux automates cellulaires conventionnels, les cellules ne constituent pas nécessairement une partition volumique de l'espace, elles sont abstraites à un niveau supérieur. En fait, un réseau peut généralement être mappé sur un nombre quelconque de dimensions. Dans la figure 4-30, les cellules sont dessinées sur une grille périodique 2D, mais il convient de noter que cette spécification de grille est ne pas partie de la définition du réseau, c'est simplement une façon de dessiner le réseau de façon ordonnée.

FIGURE 4-30 . Automates cellulaires en réseau.

Une définition de voisinage de cellule est déterminée par la configuration locale du réseau. Un exemple de définition pourrait être : la cellule elle-même plus toutes les cellules qui lui sont directement connectées et toutes les connexions entre ces cellules, comme illustré pour la cellule grise dans la découpe de la Figure 4-30 .

L'état d'une cellule de réseau est la configuration des connexions au sein de son voisinage.

Une règle de changement d'état opère sur la configuration du réseau au sein du voisinage. Des connexions peuvent être ajoutées, supprimées et modifiées. La seule restriction est qu'aucune connexion ne doit être ajoutée aux cellules en dehors du voisinage. Pour ce faire, il faudrait des informations sur l'emplacement dans le réseau des cellules à l'extérieur du quartier, ce qui revient à considérer un quartier plus grand, par exemple en incluant me niveau, cellules indirectement connectées.

4.9.1 Automates cellulaires de réseau combiné

Les automates cellulaires à réseau combiné (CNCA) sont une extension logique de NCA. Le concept est simple : l'état d'une cellule est une combinaison de la configuration du réseau dans le voisinage et un état séparé, éventuellement avec des attributs, attribué à la cellule elle-même. Comme le montre la Figure 4-31 , la principale différence avec la NCA standard est qu'une règle de changement d'état s'applique désormais également à ces états de cellule séparés et à leurs attributs. Ce chiffre fait également allusion à l'énorme quantité de possibilités qui pouvez être utilisé pour définir la fonction de transformation d'état F, car la combinaison de la configuration du réseau et des états de cellule séparés a un grand nombre de combinaisons possibles. Il faut s'attendre à ce que, lors de l'utilisation de CNCA, on limite les combinaisons possibles, mais l'ouverture de la définition permet de sélectionner celles qui sont nécessaires. Prenons l'exemple de la Figure 4-31 :

FIGURE 4-31 . Automates cellulaires de réseau combiné.

F prend en entrée les états des cellules du voisinage et/ou la configuration locale des connexions entre la cellule centrale et ses voisines.

F doit être défini pour toutes les configurations état-réseau combinées possibles, par exemple, la configuration initiale à gauche dans la découpe de la figure 4-31 conduit à la situation modifiée dans la partie droite de la figure : —

L'état de la cellule est modifié de UNE à B.

Certaines connexions réseau sont supprimées tandis que d'autres sont créées, modifiant ainsi la configuration du réseau local mais redéfinissant également le voisinage pour l'étape CNCA suivante.

Il est important de noter que, selon le type de reconfiguration du réseau, dans certains cas, la transformation d'état ne peut pas être effectuée sur toutes les cellules en parallèle, car des conflits peuvent apparaître lorsque le réseau local est modifié simultanément pour les cellules voisines. Ce sujet nécessite plus de recherches au niveau de la méthode mathématique, mais une approche pratique consiste soit à construire une fonction de transformation d'état qui garantit que de tels conflits ne peuvent pas se produire, soit à ne pas effectuer de transformations d'état sur toutes les cellules en parallèle.

La question cruciale est maintenant : de telles CNCA peuvent-elles être utiles pour modéliser l'évolution de la microstructure, ou sont-elles seulement utiles dans la recherche d'une grande théorie unifiée [ Wol02 ] ?

4.9.2 CNCA pour la modélisation de l'évolution des microstructures

Différentes structures de type réseau peuvent être observées dans les microstructures :

Les microstructures sont des grains lié par les joints de grains.

Une microstructure 2D est un ensemble de jonctions triples reliées par des joints de grains.

Peut-être, une microstructure 3D est représentable comme un ensemble de jonctions quadruples et triples reliées par des joints de grains.

Certaines microstructures de matériaux composites ou multiphasiques montrent clairement des réseaux dans leur structure.

En prenant le premier exemple de la liste, voici un moyen plausible de modéliser la croissance des grains à l'aide de la CNCA :

Attribuez à tous les grains de la microstructure un numéro d'identification unique.

L'état d'une cellule peut être n'importe lequel de ces numéros d'identification et représente un grain entier dans la microstructure.

L'attribut de l'état d'une cellule est son orientation cristallographique. Des attributs supplémentaires peuvent être le volume du grain, sa composition chimique moyenne, sa température, sa densité de dislocation, sa phase, etc.

La configuration du réseau est telle que chaque cellule de grain est reliée aux cellules de grain avec lesquelles elle est en contact par une surface de joint de grain (on pourrait ajouter des triples jonctions).

Un exemple d'un tel modèle est donné à la Figure 4-32.

FIGURE 4-32 . Automates cellulaires à réseaux combinés appliqués à une microstructure simple d'oxyde d'aluminium. L'encart montre une microstructure plus complexe d'un acier duplex laminé, où la détermination du réseau est également beaucoup plus complexe.

Il est incontestable que l'utilité du CNCA pour l'analyse et la modélisation de microstructures évolutives reste à étudier. Mais comme dernier acte de ce chapitre sur les automates cellulaires, je voudrais mettre en avant la vision que :

Il est possible de analyser l'évolution de microstructures 3D complexes à l'aide de CNCA, et que beaucoup plus de détails doivent être trouvés sur la dépendance de l'évolution de la microstructure sur le voisinage local des grains, qui sont, après tout, les éléments constitutifs des microstructures.

En outre, qu'en utilisant les résultats d'une telle analyse, au moins dans certains cas simplifiés, il est possible de prédire l'évolution de ces microstructures.

Liste des symboles

fonction de transformation d'état

k Constante de Boltzmann (= 1,38065812 e −23 J/K)

je Californie longueur unidimensionnelle d'une cellule

m mobilité des joints de grains

m0 préfacteur indépendant de la température de la mobilité des joints de grains

pune pression de conduite supplémentaire

rη rayon du quartier

rc rayon équivalent d'une cellule

fonction d'état global d'un automate cellulaire

vitesse aux joints de grains


Automates cellulaires de Noël 1983

Il existe une certaine complexité dans de nombreuses formes caractéristiques utilisées dans les images de Noël : flocons de neige, arbres de Noël, motifs de givre, etc.

Et comme dans tant d'autres cas, il est assez facile de capturer l'essence de ces formes en utilisant des règles d'automates cellulaires très simples.

Cela signifie donc qu'il est facile d'utiliser les règles des automates cellulaires pour créer des images de Noël.

Eh bien, en parcourant certaines de mes archives récemment, je me suis souvenu que je l'avais fait il y a presque exactement vingt ans pour Noël 1983. (La date réelle du fichier est le 22 novembre 1983.)

J'ai imprimé quatre types de cartes pour Noël 1983 :

Ci-joint des scans des cartes originales de 1983, ainsi que des versions modernes réalisées avec les mêmes règles (bien qu'avec des choix légèrement différents de conditions initiales aléatoires).

C'est bien sûr inévitable, mais je trouve toujours agréable que quelle que soit l'année où l'on crée une image d'automate cellulaire, elle a toujours le même look frais. D'une certaine manière, cela me rappelle les polyèdres de l'Antiquité, qui ressemblent bien sûr aux polyèdres d'aujourd'hui.

Depuis 1983, de nombreuses images d'automates cellulaires ont été utilisées pour les cartes de Noël par moi et d'autres. Et ce serait certainement formidable de voir certains d'entre eux publiés sur le forum. Mais j'ai pensé que les membres du Forum pourraient être amusés de voir mes efforts initiaux de 1983.

Notez l'absence dans ces efforts de la règle 30 ou quelque chose comme ça. Ce n'est qu'en 1984 que je me suis pleinement rendu compte que des conditions initiales simples pouvaient encore produire un comportement très complexe. (Voir le livre NKS, page 881)


Assis, F., Pedreira, C. : Une architecture pour le calcul des logarithmes de Zech en GF(2m). IEEE Trans. Calcul. 49(5), 519–524 (2000)

Bao, F. : Crytanalyse d'un nouveau cryptosystème d'automates cellulaires. 8th Australasian Conference on Information Security and Privacy – ACISP 2003. Lecture Notes in Computer Science, vol. 2727, p. 416-427. Springer, Berlin Heidelberg New York (2003)

Blackburn, S., Merphy, S., Paterson, K. : Commentaires sur « Théorie et applications des automates cellulaires en cryptographie ». IEEE Trans. Calcul. 46, 637–638 (1997)

Cattell, K., Muzio, J. : Analyse d'automates cellulaires hybrides linéaires unidimensionnels sur GF(q). IEEE Trans. Calcul. 45(7), 782–792 (1996)

Cattell, K., Muzio, J. : Synthèse d'automates cellulaires hybrides linéaires unidimensionnels. IEEE Trans. Des. assistée par ordinateur. Intégr. Système de circuits 15(3), 325–335 (1996)

Cattell, K., Shujian, Z.: Automates cellulaires hybrides linéaires unidimensionnels à coût minimal de degré à 500. J. Electron. Test.: Théorie Appl. 6, 255–258 (1995)

Cattell, K., Muzio, J. : Un algorithme d'automates cellulaires linéaires : Théorie. Département d'informatique. Université de Victoria, Canada, Tech. Rép. DCS-161-IR, 1991

Coppersmith, D., Krawczyk H., Mansour, Y. : Le générateur de rétrécissement. Avancées en cryptologie –CRYPTO'93. Notes de cours en informatique, vol. 773, p. 22-39. Springer, Berlin Heidelberg New York (1994)

Cho, S., Un-Sook, C., Yoon-Hee, H. : Calcul des déphasages de séquences d'automates cellulaires de longueur maximale 90/150. Proc. of ACRI 2004. Notes de cours sur l'informatique, vol. 3305, p. 31-39. Springer, Berlin Heidelberg New York (2004)

Das, A.K., Ganguly, A., Dasgupta, A., Bhawmik, S., Chaudhuri, P.P. : Caractérisation efficace des automates cellulaires. IEE Proc., Partie E. 1, 81–87 (1990)

Golomb, S. : Shift-Register Sequences (édition révisée). Aegean Park, Laguna Hills, Californie (1982)

Gong, G. : Théorie et applications des séquences entrelacées q-aires. IEEE Trans. Informer. Théorie 41, 400–411 (1995)

Golic, J., O'Connors, L. : Une cryptanalyse de registres à décalage contrôlés par horloge avec plusieurs étapes. Cryptographie : politique et algorithmes 41, 174–185 (1995)

Johansson, T. : Attaques par corrélation de complexité sur deux générateurs commandés par horloge. Proc. d'Asiacrypt'98. Notes de cours en informatique, vol. 1426, p. 342-356. Springer, Berlin Heidelberg New York (1998)

Kanso, A. : Générateur de rétrécissement commandé par horloge de registres à décalage de rétroaction. 8th Australasian Conference on Information Security and Privacy – ACISP 2003. Lecture Notes in Computer Science, vol. 2727, p. 443–451. Springer, Berlin Heidelberg New York (2003)

Lidl, R., Niederreiter, H. : Introduction aux champs finis et à leurs applications. Cambridge University Press, Cambridge, Royaume-Uni (1986)

Martin, O., Odlyzko, A.M., Wolfram, S. : Propriétés algébriques des automates cellulaires. Comm. Math. Phys. 93, 219–258 (1984)

Menezes, A.J., van Oorschot, P., Vanstone, S.A. : Manuel de cryptographie appliquée. CRC, New York (1997)

Nandi, S., Kar, B.K., Chaudhuri, P.P. : Théorie et applications des automates cellulaires en cryptographie. IEEE Trans. Calcul. 43, 1346–1357 (1994)

Rueppel, R.A. : Chiffrements de flux. Dans : Simmons G.J. (éd.) Cryptologie contemporaine, La science de l'information, pp. 65-134. IEEE, Piscataway, New Jersey (1992)

Serra, M., Slater, T., Muzio, J., Miller, D.M. : L'analyse des automates cellulaires linéaires unidimensionnels et leurs propriétés d'aliasing. IEEE Trans. Des. assistée par ordinateur. Intégr. Système de circuits 9(7), 767–778 (1990)

Simpson, L. et al. Horloge-une attaque de corrélation probabiliste sur le générateur de rétrécissement. Proc. of Australasian Conference on Information Security and Privacy – ACISP 1998. Lecture Notes in Computer Science, vol. 1438, p. 147-158. Springer, Berlin Heidelberg New York (1998)

Wolfram, S. : Génération de séquences aléatoires par des automates cellulaires. Av. Appl. Math. 7(123), (1986)

Wolfram, S. : Cryptographie avec automates cellulaires. Avancées en cryptologie – CRYPTO'85. Notes de cours en informatique, vol. 218, p. 22-39. Springer, Berlin Heidelberg New York (1994)

Zhang, S. : Analyse quantitative pour l'AC hybride linéaire et le LFSR en tant que générateurs BIST pour les défauts séquentiels. J. Electron. Test. 7(3), 209–221 (1995)


Wolfram, S. Rév. Mod. Phys. 55, 601–644 (1983).

Wolfram, S. Physique 10 , 1–35 (1984).

Wolfram, S. Commun. Math. Phys. (dans la presse).

Wolfram, S. Automates cellulaires (Los Alamos Science, automne 1983).

Mandelbrot, B. La géométrie fractale de la nature (Freeman, San Francisco, 1982).

Packard, N., Préimpression Modèles d'automates cellulaires pour la croissance dendritique (Institut d'études avancées, 1984).

Madore, B. & Freedman, W. La science 222, 615–616 (1983).

Greenberg, J.M., Hassard, B.D. et amp Hastings, S.P. Taureau. Amer. Math. Soc. 84, 1296–1327 (1978).

Vichniac, G. Physique 10 , 96–116 (1984).

Domany, E. & Kinzel, W. Phys. Rév. Lett. 53, 311–314 (1984).

Waddington, C.H. & Cowe, R.J. J. théor. Biol. 25, 219–225 (1969).

Lindsay, D.T. Véliger 24, 297–299 (1977).

Young, D.A. Un modèle local activateur-inhibiteur des schémas cutanés des vertébrés (Lawrence Livermore National Laboratory Rep., 1983).

Guckenheimer, J. & Holmes, P. Oscillations non linéaires, systèmes dynamiques et bifurcations de champs vectoriels (Springer, Berlin, 1983).

Hopcroft, J.E. et Ullman, J.D. Introduction à la théorie des automates, aux langages et au calcul (Addison-Wesley, New York, 1979).

Packard, N. Préimpression, Complexité des modèles de croissance dans les automates cellulaires (Institut d'études avancées, 1983).

Martin, O, Odlyzko, A. et Wolfram, S. Commun. Math. Phys. 93, 219–258 (1984).

Grassberger, P. Physique 10 , 52–58 (1984).

Lind, D. Physique 10 , 36–44 (1984).

Margolus, N. Physique 10 , 81–95 (1984).

Smith, A.R. Journal de l'Association pour les machines informatiques 18, 339–353 (1971).

Berlekamp, ​​E.R., Conway, J.H. & Guy, R.K. Façons gagnantes pour vos jeux mathématiques Vol. 2, Ch. 25 (Académique, New York, 1982).

Gardner, M. Roues, vie et autres amusements mathématiques (Freeman, San Francisco, 1983).

Wolfram, S. Manuel de référence SMP (Groupe de mathématiques informatiques, Inference Corporation, Los Angeles, 1983).


Instantanés


Le programme de simulation est écrit en JavaScript et HTML5, donc un navigateur décent, prenant en charge ces technologies est une exigence absolue. J'ai testé le simulateur dans la dernière version de bureau Firefox, Chrome et Opera et cela fonctionne bien. Cela ne fonctionne pas dans IE9, mais IE 10 devrait le prendre en charge (jamais testé cependant). Il fonctionnera également sur certains navigateurs mobiles, en particulier sur Android et Chrome, mais l'interface est plus adaptée à la souris, pas aux écrans tactiles.

Utilisation de base

J'espère que vous trouverez l'interface du simulateur pour être la plupart du temps explicite. Comme dans la plupart des simulateurs CA conventionnels, vous pouvez modifier les modèles de cellules avec la souris et exécuter la simulation, étape par étape ou en continu. Si vous avez vu Golly, vous savez tout. La fonctionnalité clé que vous ne trouverez pas dans Golly est le bouton &ldquoReverse Play&rdquo qui vous permet d'évaluer l'univers cellulaire dans le temps. En effet, cela n'est possible que pour les automates cellulaires réversibles.

  • Modification des cellules en utilisant la souris ou l'interface tactile (cette dernière n'est pas pratique mais supportée).
  • Exécution de l'automate dans le sens avant et arrière.
  • Modification de la règle d'automatisation cellulaire. Soit sélectionnez l'une des règles prédéfinies, soit entrez la vôtre dans la notation de transposition (Voir &ldquoRulse dans le quartier Margolus&rdquo ci-dessus).
  • Sélection:
    • Effacer la zone sélectionnée ou non sélectionnée
    • Remplir avec des cellules aléatoires
    • Analyser le motif sélectionné (voir fonctionnalités avancées)
    • Copiez le motif sélectionné dans le tampon interne, puis collez-le dans le champ

    Fonctionnalités avancées

    • Analyseur de formes
    • Attrapeur de vaisseau spatial
    • Analyseur de règles
    • Enregistrer l'état dans l'URL

    Analyseur de formes

    • Type de motif: oscillateur, vaisseau spatial (diagonal, orthogonal ou oblique) ou aucun.
    • Période de modèle, s'il s'agit d'un oscillateur ou d'un vaisseau spatial.
    • Vitesse de déplacement du motif, au cas où il s'agirait d'un vaisseau spatial.
    Un vaisseau spatial diagonal avec la période 10896 et la vitesse c/5448. La règle est “Rotations II”. Essayez-le en direct (nouvelle fenêtre).

    Des périodes aussi longues compliquent énormément l'analyse manuelle des modèles. Étant donné 2 motifs visuellement différents, comment décidez-vous : s'agit-il de phases différentes du même motif, ou simplement de 2 motifs différents ? La forme canonique donne une solution à ce problème. L'analyseur évalue un modèle donné au cours de sa période et choisit une configuration qui minimise certains critères. (À proprement parler, il recherche la configuration la plus compacte, mais ce n'est pas vraiment important). Ce qui est important, c'est que cette forme canonique soit déterminée de manière unique (dans la plupart des cas). De plus, si le motif a été identifié comme étant un vaisseau spatial et que la règle autorise les rotations, la forme canonique est tournée de sorte que la direction du mouvement soit vers la droite (orthogonale) ou vers le bas à droite (diagonale). En utilisant la forme canonique, la détermination de l'équivalence de deux modèles est triviale : les modèles équivalents ont les mêmes formes canoniques.

    Attrapeur de vaisseau spatial

    Cette fonctionnalité facilite la recherche des vaisseaux spatiaux nés naturellement en initialisant le champ avec un motif initial aléatoire au centre et en collectant les vaisseaux spatiaux qui s'échappent. Lorsque le capteur de vaisseau spatial est activé, tous les motifs touchant la bordure du champ en sont supprimés, analysés et les vaisseaux spatiaux sont ajoutés à la bibliothèque actuellement ouverte. Tous les 30000 pas (valeur par défaut modifiable dans le volet &ldquoSettings&rdquo), le champ est réinitialisé : la sélection en cours est remplie aléatoirement.


    Haze risk : diffusion de l'information basée sur des automates cellulaires

    Les effets négatifs du risque de brume peuvent facilement se propager plus rapidement et plus largement, cependant, les études existantes étudient rarement toute la période ou le cycle des événements de diffusion, ce qui entraîne une baisse des connaissances du public, entraînant souvent des effets négatifs exagérés. Dans cet article, le modèle de simulation de diffusion basé sur des automates cellulaires est utilisé pour évaluer la diffusion des informations sur le risque de brume. Premièrement, selon le cycle de vie complet des urgences, le public affecté par les informations sur les risques de brume est classé en ressemblant au modèle SEIR des maladies infectieuses. Deuxièmement, une règle de diffusion des individus inconnus vers les individus exposés est développée sur la base de la théorie des automates cellulaires. Ensuite, en fonction de la transformation de l'état individuel à différentes étapes, un modèle de cycle de vie complet concernant la diffusion et la propagation des informations sur le risque de brume est construit. Enfin, des paramètres appropriés sont sélectionnés pour calculer les résultats sans intervention. Les résultats montrent que pendant tout le processus d'évolution, les inconnues continuent de diminuer et les lurkers continuent d'augmenter. En raison de l'existence de la période de vaccination, les personnes immunisées atteignent leur nombre maximum avant qu'elles ne soient sur le point de perdre leur immunité, et le nombre de communicateurs atteint leur minimum. Par la suite, le nombre de personnes immunisées a diminué à un niveau stable et le nombre de communicateurs continue d'augmenter vers un avantage d'agglomération. Par conséquent, afin d'obtenir un contrôle efficace de la propagation des informations sur le risque de brume, des mesures de contrôle fortes et faibles sont prises pour chaque type d'individus, et l'immunité des inconnus et des rôdeurs est augmentée pour le contrôle du type individuel. Pour l'ensemble du contrôle de la diffusion de l'information, augmentez l'immunité du communicateur et réduisez le taux de conversion de la vaccination. L'étude de la diffusion de l'information sur le risque de brume contribue à accroître le sens des responsabilités du public, contribue à améliorer la crédibilité du gouvernement et contribue à l'établissement d'une société harmonieuse.

    Ceci est un aperçu du contenu de l'abonnement, accessible via votre institution.


    2. Quelques notions de base et résultats

    2.1 Définitions de base

    Nous examinons maintenant de plus près l'AC, en nous concentrant sur les modèles et les résultats d'intérêt philosophique. Bien que la variété des systèmes que l'on trouve dans la littérature CA soit vaste, on peut générer pratiquement tous les CA en ajustant les quatre paramètres qui définissent leur structure :

    1. Réseau discret de cellules à n dimensions: Nous pouvons avoir une dimension, deux dimensions, &hellip , m-dimensionnel CA. Les composants atomiques du réseau peuvent être de forme différente : par exemple, un réseau 2D peut être composé de triangles, de carrés ou d'hexagones. D'habitude homogénéité est supposé : toutes les cellules sont qualitativement identiques.
    2. États discrets: A chaque pas de temps discret, chaque cellule est dans un et un seul état, (sigma in Sigma, Sigma) étant un ensemble de cardinalité finie (|Sigma| = k).
    3. Interactions locales: Le comportement de chaque cellule ne dépend que de ce qui se passe dans son local quartier de cellules (qui peuvent inclure ou non la cellule elle-même). Les treillis avec la même topologie de base peuvent avoir des définitions différentes du voisinage, comme nous le verrons ci-dessous. Il est cependant crucial de noter que les &ldquoactions à distance&rdquo ne sont pas autorisées.
    4. Dynamique discrète: A chaque pas de temps, chaque cellule met à jour son état courant selon une fonction de transition déterministe (phi: Sigma^n ightarrow Sigma) mappant les configurations de voisinage (m-uplets d'états de (Sigma)) à (Sigma). Il est également généralement, mais pas nécessairement, supposé que (i) la mise à jour est synchrone, et (ii) (phi) prend en entrée au pas de temps t le quartier déclare immédiatement précédent pas de temps (t - 1).

    On peut décrire de manière exhaustive, par exemple, l'automate de notre exemple de classe :

    1. Réseau unidimensionnel de cellules carrées sur une ligne.
    2. (Sigma = <1, 0>) (1 = noir ou chapeau, 0 = blanc ou chapeau), donc (|Sigma| = 2).
    3. Chaque quartier de cellule est composé des deux cellules les plus proches. Si nous indexons les cellules par les entiers, de sorte que (c_i) est le numéro de cellule je, alors le voisinage de (c_i) est (N(c_i) = langle c_, c_ angle).
    4. La règle de transition (phi) est simple : A chaque pas de temps t, un état de cellule est 1 si exactement une des cellules voisines était 1 à (t - 1, 0) sinon.

    Une règle pour une CA peut être exprimée sous la forme d'une instruction conditionnelle : &ldquoSi le voisinage est ceci-et-cela, alors passez à l'état s& rdquo. On peut écrire la forme générale de la règle pour l'AC unidimensionnelle :

    [étiqueter sigma_i (t + 1) = phi(sigma_ (t), sigma_ (t), ldots, sigma_ (t), sigma_ (t)) ]

    Où (sigma_(t) in Sigma = <0, 1, ldots, k - 1>) est l'état du numéro de cellule je au pas de temps t r précise le intervalle, c'est-à-dire combien de cellules de n'importe quel côté comptent comme voisines pour une cellule donnée et (phi) est défini explicitement en attribuant des valeurs dans (Sigma) à chacun des (k^ <2r+1> (2r + 1))-uplets représentant toutes les configurations de voisinage possibles. Par exemple, avec (r = 1, Sigma = <1, 0>), une règle de transition possible (phi) peut être exprimée comme dans la figure 4 (avec 1 étant représenté par noir, 0 comme blanc):

    Pour une cellule donnée, chaque triple au sommet représente une configuration de voisinage possible à t, la cellule en cause étant celle du milieu : pour chaque configuration, le carré du bas précise l'état de la cellule à (t + 1). Voici notre exemple en classe : vous aurez une cellule noire au cas où précisément l'un des voisins serait noir.

    2.2 Le système de classification Wolfram

    Cette représentation simple est également au cœur du code Wolfram largement adopté (Wolfram 1983), attribuant à chaque règle un numéro : avec noir = 1 et blanc = 0, la ligne du bas peut être lue comme un nombre binaire (01011010) la conversion en décimal vous donne le nom de la règle (dans ce cas, Règle 90). Étant donné que les règles pour CA avec (r = 1) et (k = 2) diffèrent juste dans la rangée inférieure du diagramme, ce schéma de codage identifie efficacement chaque règle possible dans la classe. Les AC unidimensionnelles avec (r = 1) et (k = 2) sont parmi les AC les plus simples que l'on puisse définir, mais leur comportement est parfois assez intéressant. Lorsque Stephen Wolfram a commencé à explorer ce domaine dans les années 80, cette classe semblait parfaitement adaptée. Avec (r = 1), il y a 8 voisins possibles (voir Fig. 4 ci-dessus) à mapper sur (<1, 0>), donnant un total de (2^8 = 256) règles. En commençant par des conditions initiales aléatoires, Wolfram a ensuite observé le comportement de chaque règle dans de nombreuses simulations. En conséquence, il a pu classer le comportement qualitatif de chaque règle dans l'une des quatre classes distinctes. En répétant l'expérience originale, nous avons simulé l'évolution de deux règles pour chaque classe de schéma de Wolfram&rsquos.

    2.3 Les Classes des 256 Règles

    Classer1 règles conduisant à des états homogènes, toutes les cellules aboutissant de manière stable à la même valeur :

    Classer2 règles conduisant à des structures stables ou à des motifs périodiques simples :

    Classer3 règles conduisant à un comportement apparemment chaotique et non périodique :

    Classer4 règles conduisant à des motifs et structures complexes se propageant localement dans le réseau :

    Classer1 comprend les règles qui produisent rapidement des configurations uniformes. Règles en classe2 produire un motif final uniforme, ou un cycle entre les motifs finaux, selon les configurations initiales. Les configurations produites par les membres de la classe3 sont assez aléatoires, bien que certains modèles et structures réguliers puissent être présents.

    Classer4 mérite une attention particulière. Si nous observons l'univers généré par Règle 110 nous voyons des modèles réguliers (bien que pas aussi réguliers que dans Règle 108) ainsi qu'un comportement chaotique (bien que pas aussi bruyant que dans Règle 90). Maintenant, la caractéristique de base dont une AC a besoin pour effectuer des calculs est la capacité de sa règle de transition à produire des « modèles de propagation persistants semblables à des particules » (Ilachinski 2001 : 89), c'est-à-dire des configurations localisées, stables mais non périodiques de groupes de cellules, parfois appelé solitons dans la littérature, qui peuvent préserver leur forme. Ces configurations peuvent être vues comme codage paquets d'informations, conservation eux à travers le temps, et en mouvement d'un endroit à un autre : l'information peut se propager dans le temps et dans l'espace sans subir de dégradation importante. Le degré d'imprévisibilité dans le comportement de Class4 Les règles font également allusion à des caractéristiques intéressantes du point de vue informatique : par le théorème d'arrêt (voir la section dans l'entrée sur les machines de Turing), c'est une caractéristique clé du calcul universel que l'on ne peut pas en principe prédire si un calcul donné s'arrêtera étant donné une certaine entrée. Ces idées ont conduit Wolfram à conjecturer que la classe4 CA étaient (les seuls) capables de calcul universel. Intuitivement, si nous interprétons la configuration initiale d'une classe4 CA comme données d'entrée, une classe universelle4 CA peut évaluer n'importe quelle fonction calculable efficacement et émuler une machine de Turing universelle. Comme nous l'avons mentionné ci-dessus, Règle 110 s'est en effet avéré être informatiquement universel.

    (Voir le document complémentaire Les 256 règles.)

    2.4 Le bord du chaos

    La nature intermédiaire de la classe4 règles est liée à l'idée que intéressant la complexité, telle que celle affichée par les entités biologiques et leur dynamique, se situe dans une zone intermédiaire entre les deux extrêmes des régularités ennuyeuses et du chaos bruyant :

    Peut-être l'implication la plus excitante [de la représentation CA des phénomènes biologiques] est la possibilité que la vie ait son origine à proximité d'une transition de phase et que l'évolution reflète le processus par lequel la vie a acquis un contrôle local sur un nombre de plus en plus grand de paramètres environnementaux affectant sa capacité à se maintenir à un point d'équilibre critique entre l'ordre et le chaos. (Langton 1990 : 13)

    L'AC a fourni non seulement l'intuition, mais un cadre formel pour étudier l'hypothèse. À la fin des années 80, l'image du « bord du chaos » a suscité un intérêt considérable de la part des praticiens de l'AC. Packard 1988 et Langton 1990 ont été les premières études à donner à Edge of Chaos une interprétation désormais bien connue dans le contexte de l'AC. Comme Miller et Page l'ont dit, « ces premières expériences suggéraient que les systèmes en équilibre au bord du chaos avaient la capacité de calcul émergent » (Miller et amp Page 2007 : 129). L'idée est assez simple : que se passe-t-il si on prend une règle comme Règle 110 et introduire une petite perturbation ? Si nous devons croire l'hypothèse Edge of Chaos, nous devrions nous attendre à ce que les règles obtenues par de petits changements dans Règle 110 présenter un comportement simple ou chaotique. Considérons un seul passage de 1 à 0 ou de 0 à 1 dans la cartographie caractéristique de Règle 110. Les résultats sont les huit règles voisines suivantes, chacune différant de Règle 110 par un seul bit (la diagonale dans le tableau, avec les nombres en italique) :

    110 111 108 106 102 126 78 46 228
    000 0 1 0 0 0 0 0 0 0
    001 1 1 0 1 1 1 1 1 1
    010 1 1 1 0 1 1 1 1 1
    011 1 1 1 1 0 1 1 1 1
    100 0 0 0 0 0 1 0 0 0
    101 1 1 1 1 1 1 0 1 1
    110 1 1 1 1 1 1 1 0 1
    111 0 0 0 0 0 0 0 0 1
    Classer 4 2 2 3 3 3 1 2 1

    En première approximation, l'hypothèse Edge of Chaos est confirmée : trois des huit voisins sont de classe3, trois sont de classe2, deux sont de classe1: Règle 110 est la seule classe4 dans la table. Pour généraliser ces résultats à l'ensemble de la classe de règles pour l'AC unidimensionnelle, Langton a introduit un paramètre, (lambda), qui s'applique à chaque (phi) : pour (k = 2), ( r = 1) (binary-state, unary-range) CA, (lambda(phi)) peut être calculé comme la fraction des entrées de la table de règles de transition qui sont mappées sur une sortie non nulle (voir Langton 1990 : 14 pour la définition générale). Dans notre cas, cela signifie : (lambda(phi)) sera égal au nombre de uns dans la colonne de règle&mdashe.g., (lambda(phi) = 5/8) pour ( phi) = Règle 110 et (lambda(phi) = 1/2) pour (phi) = Règle 46. La principale découverte de Langton était qu'une mesure simple telle que (lambda) est en corrélation avec le comportement du système : lorsque (lambda) passe de 0 à 1, le comportement moyen des systèmes passe du gel aux modèles périodiques au chaos. Langton a choisi 1/2 comme valeur de (lambda) à laquelle le comportement moyen montre d'abord des signes de chaos : règles (phi) avec (lambda(phi) sim 1/2) ont été mis en évidence comme étant à la limite (voir Miller & Page 2001 : 133).

    (lambda) Toutes les règles Règles chaotiques Règles complexes
    0 1 0 0
    1/8 8 0 0
    1/4 28 2 0
    3/8 56 4 1
    1/2 70 20 4
    5/8 56 4 1
    3/4 28 3 0
    7/8 8 0 0
    1 1 0 0

    Les règles chaotiques et complexes ont une valeur moyenne (lambda) d'environ 1/2, soutenant ainsi apparemment l'hypothèse Edge of Chaos. Il est juste de dire, cependant, que certains ont mis en doute le rôle explicatif du paramètre (lambda) et les inférences qui en sont tirées. En particulier, la région de transition du Bord du Chaos semble être elle-même complexe. Miller et Page notent que &ldquothere sont des arêtes multiples, pas seulement une&rdquo (Miller & Page 2007 : 133). Les résultats agrégés ne tiennent pas lorsque nous analysons des règles individuelles, même paradigmatiques :

    110 111 108 106 102 126 78 46 228
    (lambda) 5/8 3/4 1/2 1/2 1/2 3/4 1/2 1/2 3/4

    Comme le montre le tableau, parmi les Règle 110 voisins, certaines règles chaotiques (phi) ont (lambda(phi) = 3/4), certaines règles cycliques ont (lambda(phi) = 1/2) et, en effet,

    every one of the rules classified as complex in this space has at least one chaotic neighbor with a lower (lambda) value and one with higher value. (Miller & Page 2007: 135)

    Melanie Mitchell, Peter Hraber and James Crutchfield replicated Langton and Packard&rsquos experiments, reporting very different results (Mitchell, Hraber, & Crutchfield 1994). In particular, they report that serious computational phenomena take place much closer to a chaotic (lambda(phi) = 1/2) than it was previously thought. Apart from technical points, a conceptual flaw in the original findings is the use of aggregate statistics, which are difficult to interpret in a high variance context:

    if, instead, the hypotheses are concerned with generic, statistical properties of CA rule space&mdashthe &ldquoaverage&rdquo behavior of an &ldquoaverage CA&rdquo at a given (lambda)&mdashthen the notion of &ldquoaverage behavior&rdquo must be better defined. (Mitchell, Hraber, & Crutchfield 1994: 14).

    While it is fair to conclude that complex behavior does not lie at the Edge of Chaos taken in a simplistic sense (i.e., it is not straightforwardly correlated with the simple (lambda)), the interest in the connection between computational capabilities and phase transitions in the CA rule space has been growing since then. We will consider such developments below, specifically in the context of CA and the philosophy of computation.

    2.5 CA in More Dimensions: the Game of Life

    Notwithstanding the computational interest of one-dimensional CA, philosophical issues have been discussed more often in connection with two-dimensional CA. The first CA, von Neumann&rsquos self-reproducing automaton, inhabited a two-dimensional grid. Besides, two-dimensional CA are suitable for representing many physical, biological, and even human phenomena, ranging from the dynamics of perfect gases to the movements of birds in a storm and soldiers on a battlefield. The most common configurations have either square or hexagonal cells, given their translational and rotational symmetries. Moving to two dimensions, of course, also expands the possibly interesting combinations of rules and neighborhoods. As for the latter, the two most common options in a grid of squares are the von Neumann neighborhood, where each cell interacts only with its four horizontal and vertical adjacent mates, and the Moore neighborhood, comprising all the eight immediately adjacent cells.

    By way of example, we introduce the famous Game of Life (or, more briefly, Life) by John Conway (see Berkelamp, Conway, & Guy 1982). Life fits well with our usual schema:

    1. 2-dimensional lattice of square cells in an orthogonal grid.
    2. (Sigma = <1, 0>), so (|Sigma| = 2) (for reasons we are about to see, we can picture 1 as the state of being alive for a given cell, 0 as the state of being dead).
    3. Each cell&rsquos neighborhood is composed of all its eight neighboring cells (the Moore neighborhood).
    4. Life&rsquos transition rule goes as follows. At each time step t exactly one of three things can happen to a cell:
      1. Birth: If the cell state at (t - 1) was 0 (dead), the cell state becomes 1 (alive) if exactly three neighbors were 1 (alive) at (t - 1)
      2. Survival: If the cell state at (t - 1) was 1 (alive), the cell state is still 1 if either two or three neighbors were 1 (alive) at (t - 1)
      3. Death: If the cell state at (t - 1) was 1 (alive), the cell state becomes 0 (dead) if either fewer than two or more than three neighbors were 1 (alive) at (t - 1) (cells can die of &ldquoloneliness&rdquo or &ldquooverpopulation&rdquo).

      Life would definitely be considered a Class4 CA by Wolfram&rsquos taxonomy. In this simple setting, periodic structures, stable blocks and complex moving patterns come into existence, even starting from a very simple initial configuration. Conway remarked:

      It&rsquos probable, given a large enough Life space, initially in a random state, that after a long time, intelligent, self-reproducing animals will emerge and populate some parts of the space. (cited in Ilachinski 2001: 131)

      Life-fans explored the CA&rsquos possible patterns of evolution, and shared their findings in what has been called Life&rsquos zoology (Dennett 2003: 41). Here is a small gallery of samples together with snapshots of a typical simulation (for more pictures and animations, see Other Internet Resources at the end). Gliders are the most popular among the basic Life inhabitants: a simple 5-bit structure, a glider can travel the Life grid in a 4-time step cycle:

      Toads are period 2 blinking configurations: together with Blinkers et Beacons they are the simplest oscillators of the universe.

      Eaters have the feature of devouring other configurations, e.g., gliders, maintaining intact their own form (because of this, they play an important role for Life&rsquos computational abilities).

      An Eater devouring a Glider

      A typical evolution of Life starting from random initial conditions may contain all of the above notable figures and much more. Some initial configuration may end up, even after few time steps, into static or simple periodic structures. Other configurations, though, can produce non-periodic, increasingly complex environments whose development can be unpredictable (even in the computational sense we are about to explore). As Ilachinski has suggestively conjectured from this:

      Upon observing the seemingly unlimited complexity and variety of Life&rsquos evolving patterns, it becomes almost impossible to refrain from imagining, along with Conway, that, were the game really to be played on an infinite lattice, there must surely arise true living &ldquolife-forms&rdquo, perhaps themselves evolving into more complex, possibly sentient, &ldquoorganisms&rdquo. (Ilachinski 2001: 133)

      The mathematical literature on CA does not refrain from describing the Life configurations using the same imaginative vocabulary we used: items are born, live, move around, eat other figures, die, etc. The universe these patterns inhabit may also be described, though, as a collection of individual cells, each of which does not directly depend on what is happening on the macro-scale. And the life on Life can also be described in the simple mathematical language of matrices and discrete sequences. But if one is only told the basic Life rule, one could hardly imagine the complexity it can generate&mdashuntil one sees it. Life&rsquos reputation among scientists and philosophers arguably comes from its challenging naive intuitions about complexity, pattern formation and reality, persistence, and continuity: as a toy universe we ourselves built, we feel we should know in advance what dynamics are allowed. This has been shown to be impossible, in a mathematically precise sense.

      2.6 Life as a Universal Turing Machine

      Like any other CA, Life can be considered a computational device: an initial configuration of the automaton can encode an input string. One can let the system run and, at some point, read the current configuration as the result of the computation performed so far, decoding it into an output string. But exactly what can Life compute? It turns out that Life can compute everything a universal Turing machine can and therefore, taking on board Turing&rsquos Thesis, function as a general purpose computer: a suitable selection of initial conditions can ensure that the system carry out arbitrary algorithmic procedures.

      The proof of the universal computational capacities of Life presented in Berkelamp, Conway, and Guy 1982 consists in showing that the basic building blocks or primitives of standard digital computation can be emulated by appropriate patterns generated by Life&mdashin particular: (a) data storage or memorization, (b) data transmission requiring wires and an internal clock, and (c) data processing requiring a universal set of logic gates, like negation, conjunction and disjunction&mdashan actual Turing machine was later explicitly implemented in Life by Paul Rendell (see Other Internet Resources).

      This finding is not of great engineering importance (no one would spend their time translating &ldquo(24 + 26 / 13)&rdquo into Life). However, it raises a conceptual issue about any universe sharing the capacity of producing and hosting universal computers: because of the aforementioned Halting Theorem, no general algorithm is to decide whether, given some initial configuration as input, Life will eventually die out or halt. It is in this sense that the evolution of the automaton is unpredictable. Given that the development of CA that are computationally universal cannot be predicted by direct mathematical analysis alone, it is no surprise that CA practitioners have adopted the language of philosophy and talked of phenomenological studies of CA (we will come back to this terminology in more detail in Section 3.4 below, discussing how CA model whatever they can model). Here the automaton is realized as a computer software, and the observable emergent properties of its evolution are empirically registered as the computer simulation advances. In Wolfram&rsquos turn of phrase, Life est algorithmically irreducible: no algorithmic shortcut is available to anticipate the outcome of the system given its initial input. &ldquoLife&mdashlike all computationally universal systems&mdashdefines the most efficient simulation of its own behavior&rdquo (Ilachinski 2001: 15). This raises the important philosophical question of the limits of the predictability of any universe capable, just as Life is, of producing and hosting universal computers.

      2.7 Further CA

      Notwithstanding the historical and conceptual centrality of the CA described in this section, many important developments in the field could not be presented in the space allowed for this entry. One can relax some of the assumptions in the general characterization of CA provided in Section 2.1 and get interesting results. The transition rule can be probabilistic and take into consideration more than just one time step (see Richards, Meyer, & Packard 1990: probabilistic automata are widely used to represent the stochastic dynamics of microphysical systems) the cell state updating can be asynchronous (see Ingerson & Buvel 1984) the lattice can be made of non-homogenous cells following different transition rules (see Kauffman 1984) even the discreteness constraint can be relaxed by having the set of states be the set of nombres réels (see Wolfram 2002: 155&ndash157).

      CA are also being fruitfully used in connection to the issue of the thermodynamic limits of computation: is there a minimum amount of energy needed to perform a logical operation? Landauer (1961) argued that irreversible logical operations (i.e., operations that, not corresponding to bijections, cannot be run backwards as they entail some information loss) necessarily dissipate energy. The invention of the Fredkin reversible logical gate and of the Billiard Ball Model of reversible computation (Fredkin & Toffoli 1982) strengthened the importance of the link between universal reversible automata and the physical properties of computation (for an overview, see Ilachinski 2001: 309&ndash323 for a sample reversible CA, see Berto, Rossi, & Tagliabue 2016).

      Finally, it is worth mentioning that genetic algorithms have been used with CA to study how evolution creates computation (for a survey of important results, see Mitchell, Crutchfield, & Das 1996). While the aforementioned sources further explore these possibilities, the sample CA models discussed so far will be sufficient for the philosophical arguments we are going to address henceforth.


      Liens connexes

      Take advantage of the Wolfram Notebook Emebedder for the recommended user experience.

      • Radius-1/2 Cellular Automata
        Daniel de Souza Carvalho
      • Sorted Evolutions of Cellular Automata
        Michael Schreiber
      • General Additive Cellular Automata
        Stephen Wolfram
      • Classifying the Complexity and Information of Cellular Automata
        Daniel de Souza Carvalho
      • 3-Color Left/Right Mobile Automata
        Narine Manukyan
      • Totalistic Cellular Automaton with Rule 935912 r = 1, k = 4
        Daniel de Souza Carvalho
      • Five-Neighbor 2D Totalistic Cellular Automata
        Daniel de Souza Carvalho
      • Examples of 1D Three-Color Totalistic Cellular Automata
        Abigail Nussey
      • Circular View of the Means of Two-Color Totalistic 2D Cellular Automata
        Daniel de Souza Carvalho
      • Patterns from the Mean of Two-Color Totalistic 2D Cellular Automata
        Daniel de Souza Carvalho
      • Expected Returns of the Dow Industrials, Beta Model
        Jason Cawley
      • Comparing Data on Countries
        Jason Cawley
      • Rank Plots for Countries
        Jason Cawley
      • Country Groups
        Jason Cawley
      • Country Data and Benford&aposs Law
        Jason Cawley
      • Cellular Automata with Global Control
        Jason Cawley
      • Simulating the 2008 U.S. Presidential Election
        Jason Cawley
      • Exploring Social Choice Theory
        Jason Cawley
      • Fully Random, Five-Rule Interactive Cellular Automata (ICA)
        Jason Cawley
      • Algorithmic Architecture with Cellular Automata
        Jason Cawley
      • Modeling Return Distributions
        Jason Cawley
      • Expected Returns of the Dow Industrials, Fama-French Model
        Jason Cawley
      • Credit Risk
        Jason Cawley
      • Highlighting Patterns in Cellular Automata
        Jason Cawley
      • Markov Volatility Random Walks
        Jason Cawley
      • Asset Allocation
        Jason Cawley
      • Mean-Reverting Random Walks
        Jason Cawley
      • An Amoeba Problem
        Jason Cawley
      • Totalistic K3 R 1/2 Cellular Automata
        Jason Cawley
      • Cellular Automaton Model of Pine Savanna Dynamics in Response to Fire and Hurricanes
        Jason Cawley


      Voir la vidéo: Automates cellulaires (Décembre 2021).