Research Associate EPSCR

Unconventional Computing Group ( and Artificial Intelligence Group

Introduction and definition:

Cellular automaton : a regular lattice of uniform cells. Each cell is a finite automaton which updates its states depending on states of its closest neighbours. All cells of the lattice update their states simultaneously in discrete time.

Turing Machine : A MODEL OF COMPUTATION that uses an underlying FINITE-STATE AUTOMATON but also has a infinite tape to use as memory. Turing machines are capable of UNIVERSAL COMPUTATION.

Universal Computer: A computer that is capable of UNIVERSAL COMPUTATION, which means that given a description of any other computer or PROGRAM and some data, it can perfectly emulate this second computer or program. Strictly speaking, home PCs amd Macintoshes are not universal computers because they have only a finite amount of memory.

The Game of Life : 2D cellular automata in which a living cell dies iff it has two or three neighbors and a dead cell comes alive iff it has three neighbors.

Our goal:

Find other universal automata than the Game of Life.

Our rational:

Use Stochatisc algorithms of local search named evolutionary algorithms.

Set of automata:

Space I of isotropic two states 2D automata, with transition rules that take into account t thhe placement of the eight neighbors of a cell, to determine the cell’s state at the next generation.

Evolutionary Algorithm n°1:

-The algorithm try to maximize the number of gliders and the number of periodic patterns that appear after the evolution of a random configuration of cells.

Subset of Automata Accepting Gliders:

This algorithm provided several automata accepting gliders

Small sample of discovered gliders : download

R Automaton Shown Universal:

In order to show the universality of R we simulate the Game of Life with R:

-The first step is to simulate a cell Sn and

-The second step is to tile a surface with any number of interconnected cells.

Simulation of a cell of the Game of Life:

download in lif format

A tiling of a surface of with interconnected cells


February 2006: E. Sapin. Approche évolutionniste de la recherche d’automates cellulaires universels. In TSI (Technique et Science Informatiques). To be published.

Novembre 2005: E. Sapin, O. Bailleux, J.J. Chabrier and P. Collet. Demonstration of the Universality of a New Cellular Automaton. In IJUC (International Journal of Unconventional Computing). To be published.

June 2004: E. Sapin, O. Bailleux, J.J. Chabrier and P. Collet. A New Universal Cellular Automaton Discovered by Evolutionary Algorithms. In GECCO04. Lecture Notes in Computer Science, 3102: 175-187, 2004.

October 2003: E. Sapin, O. Bailleux, and J.J. Chabrier. Research of complex forms in the cellular automata by evolutionary algorithms. In EA03. Lecture Notes in Computer Science, 2936: 357-367, 2003.

June 2003: E. Sapin, O. Bailleux, and J.J. Chabrier. A New Approach of Stream Duplication in 2D Cellular Automata. In SCI2003.

April 2003: E. Sapin, O. Bailleux, and J.J. Chabrier. Research of a cellular automaton simulating logic gates by evolutionary algorithms. In EuroGP03. Lecture Notes in Computer Science, 2610:414–423, 2003.