Complexity Classes in the Two-dimensional Life Cellular Automata Subspace
Michael Magnier
Claude Lattaud
Electronic mail address: Lattaud.Claude@math-info.univ-paris5.fr.
Laboratoire d'Intelligence Artificielle de Paris V,
Université René Descartes,
45 rue des Saints Péres - 75006 Paris, France
Jean-Claude Heudin
Electronic mail address: Jean-Claude.Heudin@devinci.fr.
International Institute of Multimedia,
Pôle Universitaire Léonard de Vinci,
92916 Paris La Défense Cedex, France
Abstract
This paper presents results from a systematic exploration of a two-dimensional cellular automata subspace based on Conway's "Game of Life.'' A qualitative study of its dynamics has led to a refinement of Wolfram's classification. Evidence that rules supporting gliders are located in the vicinity of a phase transition between order and chaos are found.
