Caractériser l’analogie entre automates cellulaires déterministes et systèmes physiques
DOI :
https://doi.org/10.20416/LSRSPS.V5I2.2Mots-clés :
classification de Wolfram, analogie, transition de phase, automates cellulairesRésumé
La classification de Wolfram des automates cellulaires déterministes repose sur l’analogie entre le comportement dynamique des automates et celui de systèmes physiques au cours d’une transition de phase. Pour évaluer la valeur scientifique de la classification, longuement débattue, on doit s’interroger sur les caractéristiques de cette analogie. Nous établissons ici quels éléments, présents dans les transitions de phase, n’ont pas d’équivalent dans le domaine des automates. Ensuite, nous discutons la notion de potentiel d’une analogie en la comparant à deux autres exemples de la littérature.
Références
BALDWIN, John T., SHELAH, Saharon. 2000. On the classifiability of cellular automata. Theoretical computer science, 230(1-2), 117-129.
BARTHA, Paul. 2010. By parallel reasoning. Oxford University Press.
BARTHA, Paul. 2013. Analogy and analogical reasoning. In ZALTA, Edward (éd.). The Stanford Encyclopedia of Philosophy.
BEDAU, Mark A. 1997. Weak emergence. Noûs, 31(s11), 375-399.
BERLEKAMP, Elwyn R., CONWAY, John Horton, GUY, Richard K. 2001. Winning Ways for your Mathematical Plays, Volume 4. Wellesley, MA : A.K. Peters.
BOHR , Niels. 2016. On the constitution of atoms and molecules. In DARRIGOL, Olivier, DUPLANTIER, Bertrand, RAIMOND, Jean-Michel et al. (eds). Niels Bohr, 1913-2013. Progress in Mathematical Physics. Cham : Birkhäuser.
BRAGA, G., CATTANEO, Gianpiero, FLOCCHINI, Paola, QUARANTA VOGLIOTTI, C. 1995. Pattern growth in elementary cellular automata. Theoretical computer science, 145(1-2), 1-26.
BRUSH, Stephen G. 1967. History of the lenz-ising model. Reviews of Modern Physics, 39(4), 883-893.
CALLEN, Herbert B. 1985. Thermodynamics and an introduction to thermostatistics. 2nde édition. New York : Wiley & Sons.
COOK, Matthew. 2004. Universality in elementary cellular automata. Complex Systems, 15(1), 1-40.
CREUTZ, Michael. 1983. Microcanonical monte-carlo simulation. Physical Review Letters, 50(19), 1411-1414.
CREUTZ, Michael. 1986. Deterministic Ising dynamics. Annals of Physics, 167(1), 62-72.
CRUTCHFIELD, James P., MITCHELL, Melanie. 1995. The evolution of emergent computation. Proceedings of the National Academy of Sciences, 92(23), 10742-10746.
CULIK II, Karel, YU, Sheng. 1988. Undecidability of CA classification schemes. Complex Systems, 2(2), 177-190.
DHAR, Avinash, LAKDAWALA, Porus, MANDAL, Gautam, WADIA, Spenta R. 1995. Role of initial conditions in the classification of the rule space of cellular automata dynamics. Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics, 51(4), 3032-3037.
DOMANY, Eytan, KINZEL, Wolfgang. 1984. Equivalence of cellular automata to ising models and directed percolation. Physical review letters, 53(4), 311-314.
GILMAN, Robert H. 1987. Classes of linear automata. Ergodic Theory and Dynamical Systems, 7(1), 105-118.
GRAY, Lawrence. 2003. A mathematician looks at wolfram’s new kind of science. Notices of the American Mathematical Society, 50(2), 200-211.
GUTOWITZ, Howard, LANGTON, Christopher G. 1995. Mean field theory of the edge of chaos. Advances in Artificial Life, 52-64.
HESSE, Mary. 1964. Analogy and confirmation theory. Philosophy of Science, 31(4), 319-327.
HURLEY, Mike. 1990. Attractors in cellular automata. Ergodic Theory and Dynamical Systems, 10(1), 131-140.
ISHII, Shin’ichirou. 1992. Measure theoretic approach to the classification of cellular automata. Discrete applied mathematics, 39(2),125-136.
ISING, Ernst. 1925. Beitrag zur Theorie des Ferromagnetismus. Zeitschrift für Physik, 31, 253-258.
LANDAU, Lev Davidovich. 1937. On the theory of phase transitions. Ukrainian Journal of Physics, 11, 19-32.
LANGTON, Christopher G. 1990. Computation at the edge of chaos : phase transitions and emergent computation. Physica D, 42(1-3), 12-37.
LI, Wentian, PACKARD, Norman H. 1990. The structure of the elementary cellular automata rule space. Complex Systems, 4(3), 281-297.
LI, Wentian, PACKARD, Norman H., LANGTON, Christopher G. 1990. Transition phenomena in cellular automata rule space. Physica D, 45(1-3), 77-94.
MARTIN, Bruno. 2001. Automates cellulaires, information et chaos. Thèse de doctorat, Laboratoire de l’Informatique du Parallelisme, ENS Lyon.
MILNOR, John W. 2006. Attractor.
MITCHELL, Melanie. 1998. Computation in Cellular Automata: A Selected Review. In GRAMSS T., et al. Nonstandard Computation. Weinheim : VCH Verlagsgesellschaft. 95-140.
MITCHELL, Melanie, CRUTCHFIELD, James P., HRABER, Peter T. 1993. Dynamics, computation, and the “edge of chaos” : A re-examination. arXiv:adap-org/9306003.
NORTON, John D. 2011. Analogy. Pittsburg University preprint.
PACKARD, Norman H. 1988. Adaptation Toward the Edge of Chaos. University of Illinois at Urbana-Champaign, Center for Complex Systems Research.
SARKAR, Palash. 2000. A brief history of cellular automata. ACM Computing Surveys (CSUR), 32(1), 80-107.
SIPSER, Michael. 2006. Introduction to the Theory of Computation. 2nde édition. Boston : Thomson Course Technology.
STANLEY, Eugene H. 1987. Introduction to phase transitions and critical phenomena. Oxford University Press.
TURING, Alan Mathison, GIRARD, Jean-Yves. 1995. La machine de Turing. Editions du Seuil.
VAN ALBADA, Tjeerd Sicco. 1968. Numerical integrations of the n-body problem. Bulletin of the Astronomical Institutes of the Netherlands, 19, 479-499.
VICHNIAC, Gérard Y. 1984. Simulating physics with cellular automata. Physica D Nonlinear Phenomena, 10, 96-116.
WOLFRAM, Stephen. 1983. Statistical mechanics of cellular automata. Reviews of modern physics, 55(3), 601-644.
WOLFRAM, Stephen. 1984. Universality and complexity in cellular automata. Physica D, 10(1), 1-35.
WOLFRAM, Stephen. 1985. Twenty problems in the theory of cellular automata. Physica Scripta, 1985, 170-183.
WOLFRAM, Stephen. 1986. Random sequence generation by cellular automata. Advances in applied mathematics, 7(2), 123-169.
WOOTTERS, William K., LANGTON, Christopher G. 1990. Is there a sharp phase transition for deterministic cellular automata. Physica D: Nonlinear Phenomena, 45 (1-3), 95-104.
WUENSCHE, Andrew. 1999. Classifying cellular automata automatically. Complexity, 4(3), 47-66.
ZWIRN, Hervé P. 2006. Les systems complexes : mathématiques et biologie. Paris : Odile Jacob.
Téléchargements
Publiée
Comment citer
Numéro
Rubrique
Licence
(c) Tous droits réservés Lionel Tabourier 2018
Ce travail est disponible sous licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Pas de Modification 4.0 International.
Les auteurs conservent le droit d'auteur et accordent à la revue le droit de première publication, l'ouvrage étant alors disponible simultanément, sous la licence Licence d’attribution Creative Commons permettant à d'autres de partager l'ouvrage tout en en reconnaissant la paternité et la publication initiale dans cette revue.
