Cogprints

Implementation of Logical Functions in the Game of Life

Rennard, Jean-Philippe (2002) Implementation of Logical Functions in the Game of Life. [Book Chapter]

Full text available as:

[img]
Preview
 PDF
574Kb

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.

Item Type:Book Chapter
Keywords:cellular automata, universal Turing machine, Game of Life, collision-based computing, Boolean algebra
Subjects:Computer Science > Complexity Theory
ID Code:4115
Deposited By: Rennard, Dr. Jean-Philippe
Deposited On:08 Mar 2005
Last Modified:11 Mar 2011 08:55

References in Article

Select the SEEK icon to attempt to find the referenced article. If it does not appear to be in cogprints you will be forwarded to the paracite service. Poorly formated references will probably not work.

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.

Metadata

Repository Staff Only: item control page

Cogprints is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.