Article

Evolution in asynchronous cellular automata

Author:

Chrystopher L. NehanivAuthors Info & Claims

ICAL 2003: Proceedings of the eighth international conference on Artificial life

Pages 65 - 73

Published: 09 December 2002 Publication History

Abstract

Building on the work of Von Neumann, Langton, and Sayama among others, we introduce the first examples of evolution in populations of self-reproducing configurations in asynchronous cellular automata. Reliance on a global synchronous update signal has been a limitation of all solutions since the problem of achieving self-production in cellular automata was first attacked by Von Neumann half a century ago. Results of the author obviate the need for this restriction.We review our simple constructive mechanism to transform any cellular automata network with synchronous update into one with essentially the same behavior but whose cells may be updated randomly and asynchronously. The generality of this mechanism is guaranteed by a general mathematical theorem that any synchronous cellular automata configuration and rule can be realized asynchronously in such a way that the behavior of the original synchronous cellular automata can be completely recovered from that of the corresponding asynchronous cellular automaton, in which temporal synchronization locally stays within small tolerances.It follows that most results on self-reproduction, universal computation and construction, and evolution in populations of self-reproducing configurations in cellular automata that have been obtained in the past carry over to the asynchronous domain using the method described here.Here we discuss requirements for evolutionary systems in cellular automata and describe implemented examples of our procedure applied to a variety of self-reproducing systems (Byl, Reggia et al., Langton, Sayama).In particular, we have implemented Sayama's evo-loop system asynchronously, giving the first example of evolution in asynchronous cellular automata.

References

[1]

Bachmutsky, E. Self-replicating Loops and Ant Java Applet, applet and source code available on-line at: http://necsi.org/postdocs/sayama/sdsr/java/, 1999.

[2]

Byl, J. "Self-Reproduction in Small Cellular Automata", Physica D, Vol. 34, pp. 295-299, 1989.

[3]

Burks, A. W. (ed.), Essays on Cellular Automata, University of Illinois Press, Urbana, Illinois, 1970.

[4]

Codd, E. F. Cellular Automata. Academic Press, New York, 1968.

Digital Library

[5]

Conrad, M. "The Geometry of Evolution", BioSystems, Vol. 24, 61-81, 1990.

[6]

Freitas, R. A., Jr., and Gilbreath, W. P. (eds.) Advanced Automation for Space Missions, Proceedings of the 1980 NASA/ASEE Summer Study; sponsored by the National Aeronautics and Space Administration and the American Society for Engineering Education. NASA Conference Publication 2255. On-line extracts at http://www.zyvex.com/nanotech/selfRepNASA.html and http://www.islandone.org/MMSG/aasm/.

[7]

Kirschner, M. and Gerhart, J. "Evolvability", Proc. National Academy of Sciences, Vol. 95, pp. 8420-8427, July 1998.

[8]

Langton, C. G. "Self-reproduction in Cellular Automata", Physica D, Vol. 10, pp. 135-144, 1984.

[9]

Langton, C. G. "Studying Artificial Life with Cellular Automata", Physica D, Vol. 22, pp. 120-149, 1986.

Digital Library

[10]

Lohn, J.D. "Self-replicating Systems in Cellular Space Models". In C. L. Nehaniv (ed.), Mathematical and Computational Biology: Computational Morphogenesis, Hierarchical Complexity, and Digital Evolution. Vol. 26 in Lectures on Mathematics in the Life Sciences, Providence, Rhode Island, American Mathematical Society, pp. 11-30, 1999.

[11]

Lohn, J. D. and Reggia, J. A. "Automatic Discovery of Self Replicating Structures in Cellular Automata", IEEE Transactions on Evolutionary Computation, Vol. 1 No. 3, pp. 165-178, 1997.

Digital Library

[12]

McMullin, B. "John von Neumann and the Evolutionary Growth of Complexity: Looking Backwards, Looking Forwards.". In M. A. Bedau, J. S. McCaskill, N. H. Packard, and S. Rasmussen (eds.), Artificial Life VII, MIT Press, 467-476, 2000.

[13]

Nakamura, K. "Asynchronous Cellular Automata and their Computational Ability", Systems, Computers, Controls, Vol. 5, No. 5, 1974, pp. 58-66, translated from Denshi Tsushin Gakkai Ronbunshi, Vol. 57-D, No. 10, Oct 1974, pp. 573-580.

[14]

Nehaniv, C. L. "Self-Reproduction in Asynchronous Cellular Automata", Proc. 2002 NASA/DoD Conference on Evolvable Hardware (15-18 July 2002, Alexandria, Virginia, USA), IEEE Computer Society Press, pp. 201-209, 2002.

Digital Library

[15]

Nehaniv, C. L. "Asynchronous Automata Networks Can Emulate Any Synchronous Automata Network", International Workshop on Semigroups, Automata, and Formal Languages (June 2002 - Crema, Italy), 2002 (accepted). journal version in preparation.

[16]

Reggia, J. A., Armentrout, S., Chou, H. H., Peng, Y., "Simple Systems that Exhibit Self-Directed Replication", Science, Vol. 259, pp. 1282-1288, 1993.

[17]

Sayama, H. Constructing Evolutionary Systems on a Simple Deterministic Cellular Automata Space, Ph.D. Dissertation, Department of Information Science, Graduate School of Science, University of Tokyo, December 1998.

[18]

Sayama, H., "Introduction of Structural Dissolution into Langton's Self-Reproducing Loop", Artificial Life VI: Proceedings of the Sixth International Conference on Artificial Life, C. Adami, R. K. Belew, H. Kitano, and C. E. Taylor, eds., pp. 114-122, 1998, MIT Press. On-line material at: http://necsi.org/postdocs/sayama/sdsr/

Digital Library

[19]

Sayama, H. "A New Structurally Dissolvable Self-Reproducing Loop Evolving in a Simple Cellular Automata Space", Artificial Life, Vol. 5, no. 4, pp. 343-365, 1999.

Digital Library

[20]

Schönfisch, B. and de Roos, A. "Synchronous and Asynchronous Updating in Cellular Automata", BioSystems, Vol. 51, 123-143, 1999.

[21]

Sipper, M. The Artificial Self-Replication Page http://www.cs.bgu.ac.il/~sipper/selfrep/

[22]

Szathmáry, E. "Chemes, Genes, Memes: A Classification of Replicators". In C. L. Nehaniv (ed.), Mathematical and Computational Biology: Computational Morphogenesis, Hierarchical Complexity, and Digital Evolution. Vol. 26 in Lectures on Mathematics in the Life Sciences, Providence, Rhode Island, American Mathematical Society, pp. 1-10, 1999.

[23]

Toffoli, T. "Integration of the Phase-Difference Relations in Asynchronous Sequential Networks", in Automata, Languages and Programming (Fifth Colloquium, Udine, July 1978), G. Ausiello and C. Bohm (eds.), LNCS 62, Springer Verlag, pp. 457-463, 1978.

Digital Library

[24]

Toffoli, T. and Margolus, N. Cellular Automata Machines, MIT Press, 1987.

Digital Library

[25]

Von Neumann, J. Theory of Self-Reproducing Automata. Edited and completed by A. W. Burks, University of Illinois Press, Illinois, 1966.

Digital Library

Cited By

Chandesris JDennunzio AFormenti EManzoni L(2011)Computational aspects of asynchronous cellular automataProceedings of the 15th international conference on Developments in language theory10.5555/2032178.2032222(466-468)Online publication date: 19-Jul-2011
https://dl.acm.org/doi/10.5555/2032178.2032222
Bandini SBonomi AVizzari GAcconci V(2010)A cellular automata-based modular lighting systemProceedings of the 9th international conference on Cellular automata for research and industry10.5555/1927432.1927473(334-344)Online publication date: 21-Sep-2010
https://dl.acm.org/doi/10.5555/1927432.1927473
Lee JAdachi SPeper F(2007)Reliable Self-Replicating Machines in Asynchronous Cellular AutomataArtificial Life10.1162/artl.2007.13.4.39713:4(397-413)Online publication date: 1-Oct-2007
https://dl.acm.org/doi/10.1162/artl.2007.13.4.397
Show More Cited By

Index Terms

Evolution in asynchronous cellular automata

Recommendations

Asynchronous automata versus asynchronous cellular automata

In this paper we compare and study some properties of two mathematical models of concurrent systems, asynchronous automata (Zielonka, 1987) and asynchronous cellular automata (Zielonka, 1989). First, we show that these models are "polynomially" related, ...
On Completeness and Decidability of Phase Space Invertible Asynchronous Cellular Automata
Cellular Automata and Models of Computation

While for synchronous deterministic cellular automata there is an accepted definition of reversibility, this is not the case for asynchronous cellular automata. We first discuss a few possibilities and then investigate what we call phase space ...
Construction universality in purely asynchronous cellular automata

Universality in cellular automata (CAs), first studied by von Neumann, has attracted much research efforts over the years, especially for CA employing synchronous timing. This paper proposes a computation- and construction-universal CA with a von ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

ICAL 2003: Proceedings of the eighth international conference on Artificial life

December 2002

428 pages

ISBN:0262692813

Publisher

MIT Press

Cambridge, MA, United States

Publication History

Published: 09 December 2002

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chandesris JDennunzio AFormenti EManzoni L(2011)Computational aspects of asynchronous cellular automataProceedings of the 15th international conference on Developments in language theory10.5555/2032178.2032222(466-468)Online publication date: 19-Jul-2011
https://dl.acm.org/doi/10.5555/2032178.2032222
Bandini SBonomi AVizzari GAcconci V(2010)A cellular automata-based modular lighting systemProceedings of the 9th international conference on Cellular automata for research and industry10.5555/1927432.1927473(334-344)Online publication date: 21-Sep-2010
https://dl.acm.org/doi/10.5555/1927432.1927473
Lee JAdachi SPeper F(2007)Reliable Self-Replicating Machines in Asynchronous Cellular AutomataArtificial Life10.1162/artl.2007.13.4.39713:4(397-413)Online publication date: 1-Oct-2007
https://dl.acm.org/doi/10.1162/artl.2007.13.4.397
Javid Mte Boekhorst R(2006)Cell dormancy in cellular automataProceedings of the 6th international conference on Computational Science - Volume Part III10.1007/11758532_50(367-374)Online publication date: 28-May-2006
https://dl.acm.org/doi/10.1007/11758532_50
Nehaniv C(2005)Self-replication, evolvability and asynchronicity in stochastic worldsProceedings of the Third international conference on StochasticAlgorithms: foundations and applications10.1007/11571155_13(126-169)Online publication date: 20-Oct-2005
https://dl.acm.org/doi/10.1007/11571155_13
Hallinan JWiles J(2004)Evolving genetic regulatory networks using an artificial genomeProceedings of the second conference on Asia-Pacific bioinformatics - Volume 2910.5555/976520.976559(291-296)Online publication date: 1-Jan-2004
https://dl.acm.org/doi/10.5555/976520.976559

View Options

View options

Figures

Tables

Media

View Table of Conten