Abstract
We aim to construct an automatic system for the discovery of collision-based universal cellular automata that simulate Turing machines in their space-time dynamics using gliders and glider guns.
In this paper, an evolutionary search for glider guns with different parameters is described and other search techniques are also presented as benchmark. We demonstrate the spontaneous emergence of an important number of novel glider guns discovered by genetic algorithms.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Wolfram, S.: A New Kind of Science. Wolfram Media, Inc., Illinois, USA (2002)
Von Neumann, J.: Theory of Self-Reproducing Automata. University of Illinois Press, Urbana, Ill (1966)
Wolfram, S.: Universality and complexity in cellular automata. Physica D 10, 1–35 (1984)
Banks, E.R.: Information and transmission in cellular automata. PhD thesis, MIT (1971)
Margolus, N.: Physics-like models of computation. Physica D 10, 81–95 (1984)
Lindgren, K., Nordahl, M.: Universal computation in simple one dimensional cellular automata. Complex Systems 4, 299–318 (1990)
Morita, K., Tojima, Y., Katsunobo, I., Ogiro, T.: Universal computing in reversible and number-conserving two-dimensional cellular spaces. In: Adamatzky, A. (ed.) Collision-Based Computing, pp. 161–199. Springer, Heidelberg (2002)
Adamatzky, A.: Universal dymical computation in multi-dimensional excitable lattices. International Journal of Theoretical Physics 37, 3069–3108 (1998)
Gardner, M.: The fantastic combinations of john conway’s new solitaire game ”life”. Scientific American 223, 120–123 (1970)
Berlekamp, E., Conway, J.H., Guy, R.: Winning ways for your mathematical plays. Academic Press, New York (1982)
Adamatzky, A., Martinez, G.J., McIntosh, H.V.: Phenomenology of glider collisions in cellular automaton rule 54 and associated logical gates chaos. Fractals and Solitons 28, 100–111 (2006)
Wuensche, A.: Discrete dinamics lab (ddlab) (2005), http://www.ddlab.org
Eppstein, D., http://www.ics.uci.edu/~eppstein/ca/
Sapin, E., Bailleux, O., Chabrier, J.J., Collet, P.: A new universel automata discovered by evolutionary algorithms. In: Deb, K., al., e. (eds.) GECCO 2004. LNCS, vol. 3102, pp. 175–187. Springer, Heidelberg (2004)
Wolfram, S., Packard, N.H.: Two-dimensional cellular automata. Journal of Statistical Physics 38, 901–946 (1985)
Glover, F.: Future paths for integer programming and links to artificial intelligence. Computers and Operations Research 13, 533–549 (1986)
Holland, J. H. : Adaptation in natural and artificial systems. University of Michigan (1975)
Packard, N.H.: Adaptation toward the edge of chaos. In: Kelso, J.A.S., Mandell, A.J., Shlesinger, M.F. (eds.) Dynamic Patterns in Complex Systems, pp. 293–301. World Scientific, Singapore (1988)
Mitchell, M., Crutchfield, J.P., Hraber, P.T.: Evolving cellular automata to perform computations: Mechanisms and impediments. Physica D 75, 361–391 (1994)
Hraber, P.T., Mitchell, M., Crutchfield, J.P.: Revisiting the edge of chaos: Evolving cellular automate to perform computations. Complex systems 7, 89–130 (1993)
Hordijk, W., Crutchfield, J.P., Mitchell, M.: Mechanisms of emergent computation in cellular automata. In: Eiben, A.E., Bäck, T., Schoenauer, M., Schwefel, H.-P. (eds.) Parallel Problem Solving from Nature-V, vol. 866, pp. 344–353. Springer, Heidelberg (1998)
Das, R., Crutchfield, J.P., Mitchell, M., Hanson, J.E.: Evolving globally synchronized cellular automata. In: Proceedings of the Sixth International Conference on Genetic Algorithms, pp. 336–343 (1995)
Sipper, M.: Evolution of parallel cellular machines. In: Stauffer, D. (ed.) Annual Reviews of Computational Physics, vol. V, pp. 243–285. World Scientific, Singapore (1997)
Andre, D., Koza, J.R., Bennett III, F.H., Keane, M.A.: Genetic programming iii: Darwinian invention and problem solving. Morgan Kaufmann, San Francisco (1999)
Koza, J.R.: Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge (1992)
Sapin, E., Bailleux, O., Chabrier, J.J.: Research of Complex Forms in Cellular Automata by Evolutionary Algorithms. In: Liardet, P., Collet, P., Fonlupt, C., Lutton, E., Schoenauer, M. (eds.) EA 2003. LNCS, vol. 2936, pp. 357–367. Springer, Heidelberg (2004)
Bays, C.: Candidates for the game of life in three dimensions. Complex Systems 1, 373–400 (1987)
Sapin, E., Bailleux, O., Chabrier, J.J.: Research of a cellular automaton simulating logic gates by evolutionary algorithms. In: Ryan, C., Soule, T., Keijzer, M., Tsang, E.P.K., Poli, R., Costa, E. (eds.) EuroGP 2003. LNCS, vol. 2610, pp. 414–423. Springer, Heidelberg (2003)
Sapin, E.: http://uncomp.uwe.ac.uk/sapin/ea/gun
Langton, C.L.: Computation at the edge of chaos. Physica D 42 (1990)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sapin, E., Bull, L. (2008). Searching for Glider Guns in Cellular Automata: Exploring Evolutionary and Other Techniques. In: Monmarché, N., Talbi, EG., Collet, P., Schoenauer, M., Lutton, E. (eds) Artificial Evolution. EA 2007. Lecture Notes in Computer Science, vol 4926. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-79305-2_22
Download citation
DOI: https://doi.org/10.1007/978-3-540-79305-2_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-79304-5
Online ISBN: 978-3-540-79305-2
eBook Packages: Computer ScienceComputer Science (R0)