creators_name: Rennard, Jean-Philippe editors_name: Adamatzky, Andrew type: bookchapter datestamp: 2005-03-08 lastmod: 2011-03-11 08:55:51 metadata_visibility: show title: Implementation of Logical Functions in the Game of Life ispublished: pub subjects: comp-sci-complex-theory full_text_status: public keywords: cellular automata, universal Turing machine, Game of Life, collision-based computing, Boolean algebra abstract: The Game of Life cellular automaton is a classical example of a massively parallel collision-based computing device. The automaton exhibits mobile patterns, gliders, and generators of the mobile patterns, glider guns, in its evolution. We show how to construct basic logical perations, AND, OR, NOT in space-time configurations of the cellular automaton. Also decomposition of complicated Boolean functions is discussed. Advantages of our technique are demonstrated on an example of binary adder, realized via collision of glider streams. date: 2002 date_type: published publication: Collision Based Computing publisher: Springer pagerange: 419-512 refereed: TRUE referencetext: Berlekamp E.R., Conway J.H. & Guy R. Winning Ways for Your Mathematical Plays, vol 2, Academic Press, 1982. Durand B. & Roka Z. The Game of Life: universality revisited Research Report 98-01, Ecole Normale Supéérieure de Lyon, Laboratoire de l'Informatique du Paralléélisme, 1998. Levy S. Artificial Life. The quest for a new creation Penguin Books, 1992 Morita K. & Imai K. A simple self-reproducing cellular automaton with shape encoding mechanism In: Artificial Life V, MIT Press, Cambridge, 1997, 489-496 von Neumann J. (Burks A., Editor) Theory of Self-Reproducing Automata, University of Illinois Press, 1966 Wolfram S. Universality and complexity in cellular automata Physica D 10, 1984, 1-35. citation: Rennard, Jean-Philippe (2002) Implementation of Logical Functions in the Game of Life. [Book Chapter] document_url: http://cogprints.org/4115/1/CollisionBasedRennard.pdf