Chapter 2 The automata

Playing with life

The essence of a fluid

Let’s use metaphors

A game of chance

Traffic

Flock dynamics

Automata can be played!

Genetic algorithms

Referencias y comentarios:

· For a detailed description of the concept of a cellular automata and its many applications, see

® Cellular Automata Modeling of Physical Systems, Bastien Chopard and Michel Droz (Cambridge University Press 1998); and

® A New Kind of Science, Stephen Wolfram (Wolfram Media 2002; see also the web site www.wolframscience.com).

El término “algoritmo” en el que descansa este concepto de autómata, se refiere a la receta para resolver un problema paso a paso, de modo que se adapta perfectamente al código usado para realizar cálculos con el ordenador y también al esquema que inspiró ese código. Proviene de Algoritmi, nombre latino del matemático Muhammad ibn Musa al Juarizmi, padre del álgebra e introductor del sistema decimal, que fundó en Bagdad la Casa de la Sabiduría donde se tradujeron obras científicas y filosóficas del griego y del hindú.

· Acerca del juego de la vida:

® “Mathematical Games – The fantastic combinations of John Conway’s new solitaire game life”, Martin Gardner, Scientific American 223, 120 (1970);

® Games of Life – Explorations in Ecology, Evolution and Behaviour, Karl Sigmund (Penguin Books 1995);

® Artificial Life: An Overview, Christopher G. Langton (The MIT Press, Cambridge MA 1997).

® “Emerging properties of financial time series in the Game of Life”, A.R. Hernández-Montoya et al., Physical Review E 84, 066104 (2011).

Los curiosos pero reacios a embarcarse en simulaciones propias, pueden ver los juegos interactivos en www.bitstorm.org/gameoflife, www.radicaleye.com and www.ibiblio.org/lifepatterns/.

· On snowflakes and symmetries, see

® “Snow and ice crystals”, Yoshinori Furukawa and John S. Weltlaufer, Physics Today (December 2007), page 70, including an original comment by Descartes on the matter.

· The first automata of a Navier-Stokes fluid appreared in

® “Lattice-Gas Automata for the Navier-Stokes Equation”, Uriel Frisch, Brosl Hasslacher, and Yves Pomeau, Physical Review Letters 56, 1505 (1986).

® “Lattice Gases Illustrate the Power of Cellular Automata in Physics”, by Bruce Boghosian, Computers in Physics (November/December 1991), page 585, es una divulgación de este modelo y de sus extensiones, y de cómo simular su comportamiento de modo eficaz en un ordenador.

Puede uno recrearse con un autómata similar en ccl.northwestern.edu, donde se detalla el procedimiento y, pulsando en “Run Lattice Gas…”, se entra en la simulación que incluye la visualización de cómo se propagan ondas al variar la densidad del fluido.

En www.realitygrid.org se describen problemas hidrodinámicos complicados resueltos con métodos basados en el uso de autómatas en el ordenador. Más información sobre autómatas y sus aplicaciones, en www.moshesipper.com.

· Un libro relacionado recomendable para lectores con formación matemática es

® The Navier-Stokes Equations – A Classification of Flows and Exact Equations, Philip G. Drazin and Norman Riley, London Mathematical Society Lecture Notes 334 (Cambridge University Press 2006).

· Para modelos reticulares dinámicos puede verse el trabajo pionero en

® “Computer experiments on phase separation in binary alloys”, Kurt Binder, Malvin H. Kalos, Joel L. Lebowitz and J. Marro, Advances in Colloid and Interface Science 10, 173 (1979) y

® “Microscopic observations on a kinetic Ising model”, J. Marro and Raúl Toral, American Journal of Physics 54, 1114 (1986).

Una descripción detallada del modelo de mezcla, incluyendo resultados de su simulación en el ordenador y la discusión de teoría y de observaciones experimentales relacionadas puede encontrarse en el artículo

® “Dinámica de transiciones de fase”, de Joaquín Marro, Serie Universitaria, volumen 127, Fundación Juan March, Madrid 1980.

Para un compendio reciente, que describe mejoras del modelo al considerar nodos vacantes, tensiones elásticas y deformaciones del retículo, véase

® “Using kinetic Monte Carlo simulations to study phase separation in alloys”, Richard Weinkamer, Peter Fratzl, Himadri S. Gupta, Oliver Penrose and Joel L. Lebowitz, Phase Transitions 77, 433 (2004).

· Para modelos con arrrastre:

® “Nonequilibrium discontinuous phase transitions in a fast ionic conductor model: co-existence and spinodal lines”, J. Marro and J. Lorenzo Valles, Journal of Statistical Physics 49, 121 (1987) and 51, 323 (1988);

® “Fast-ionic-conductor behavior of driven lattice-gas models”, J. Marro, Pedro L. Garrido and J. Lorenzo Valles, Phase Transitions 29, 129 (1991).

· El libro clásico sobre le método MC es:

® Monte Carlo Methods, Malvin H. Kalos and Paula A. Whitlock (Wiley−VCH, New York 2009).

· For natural series of random numbers, see www.fourmilab.ch/hotbits/ and www.random.org.

The algorithmic generators of artificial series are well illustrated on www.math.utah.edu/~pa/random/random.html.

Sometimes series with non-uniform distribution are of interest; see www.fortran.com/fm_gauss.html.

For the description of important types of generators and hardware realizations, see en.wikipedia.org.

On generation of random series based on quantum properties, see

® “Random numbers certified by Bell’s theorem”, Chris Monroe et al., Nature 464, 1021 (2010).

· El modelo básico sobre tráfico fue propuesto en

® “A cellular automaton model for freeway traffic”, Kai Nagel and Michael Schreckenberg, Journal de Physique I France 2, 2221 (1992).

The data as presented here are in

® The Physics of Traffic, Boris S. Kerner (Springer-Verlag, Berlin 2005) and

® Introduction to Modern Traffic Flow Theory and Control, Boris S. Kerner (Springer, NY 2009).

See also simulations at vwisb7.vkw.tu-dresden.de/~treiber/microapplet/.

For specific cases, see

® “Realistic multi-lane traffic rules for cellular automata”, Peter Wagner, K. Nagel, and Dietrich E. Wolf, Physica A 234, 687 (1997),

® “Nondeterministic Nagel-Schreckenberg traffic model with open boundary conditions”, S. Cheybani, Janos Kertesz, and M. Schreckenberg, Physical Review E 63, 016108 (2000), and

® “Jamming transitions induced by a slow vehicle in traffic flow on a multi-lane highway”, Shuichi Masukura, Takashi Nagatani, and Katsunori Tanaka, Journal of Statistical Mechanics: Theory and Experiments P04002 (2009).

· Sobre movimiento de animales, ver simulaciones en

www.dcs.shef.ac.uk/~paul/publications/boids/index.html, www.red3d.com/cwr/ boids/, www.lalena.com/ai/flock/, Physics Today, October 2007, and ptonline.aip. org/journals/doc/phtoad-ft/vol_60/iss_10/28_1.shtml?bypassSSO=1 for flocks and their applications;

www.permutationcity.co.uk/alife/termites.html for termites;

iridia.ulb.ac.be/~mdorigo/aco/aco.html and alphard.ethz.ch/Hafner/pps/pps2001/ antfarm/ant_ farm.html for ant colonies.

· El modelo de fuerzas entre organismos simples se introduce en

® “Phase transition in the collective migration of tissue cells: experiment and model”, Balint Szabó, G. Szőlősi, B. Gönci, Zs. Jurányi, D. Selmeczi, and Tamás Vicsek, Physical Rev. E 74, 061908 (2006); there is some interesting supplementary material, including a video, in angel.elte.hu/~bszabo/collectivecells/supplementa rymaterial/supplementarymaterial.html, and a related comment at physicsworld. com/cws/article/news/26485.

· For recent work on animal dynamics showing phenomena which is described in other parts of this book, see

® Celia Anteneodo and Dante R. Chialvo, “Unraveling the fluctuations of animal motor activity”, Chaos 19, 1 (2009);

® Vitaly Belik, Theo Geisel, and Dirk Brockmann, “Natural human mobility patterns and spatial spread of infectious diseases”, Physical Review X 1, 011001 (2011); and

® Filippo Simini, Marta C. González, Amos Maritan, and Albert-László Barabási, “A universal model for mobility and migration patterns”, Nature 486, 96 (2012).

· The life of Turing has been depicted in a novel, together with that of Kurt Gödel, in

® A Madman Dreams of Turing Machines (Knopf, New York 2006) by the astrophysicist Janna Levin, and the works of Turing have been compiled in www.alanturing.net.

· The first popularisation of von Neumann’s ideas appeared in

® “Man viewed as a machine”, John G. Kemeny, Scientific American 192, 58 (1955).

More recently:

® “An implementation of von Neumann’s self-reproducing machine”, Umberto Pesavento, Artificial Life 2, 337 (1995);

® “Self-replicating loop with universal construction”, Daniel Mange et al., Physica D 191, 178 (2004);

® “Self-reproducing machines”, V. Zykov et al., Nature 435, 163 (2005).

· The concept of genetic algorithm was introduced explicitly by

® John Holland (1929); see his book Adaptation in natural and artificial systems (MIT Press Cambridge, MA 1992). A classic book on the subject is

® Introduction to Genetic Algorithms, by Melanie Mitchell (MIT Press, Cambridge, MA, 1996).

® Tim J. Hutton describes a DNA automaton that shows evolution in “Evolvable self-replicating molecules in an artificial chemistry”, Artificial Life 8, 341 (2002).

Nota: véanse las referencias y enlaces que se incluyen en las dispositivas del curso, que a menudo completan las anteriores.