Searching for Spaceships

David Eppstein

Professor of Information and Computer Science
University of California, Irvine

Monday, October 16, 2000 at 1 PM
Sierra Hall, room 310

We describe software that searches for spaceships in Conway's Game of Life and related two-dimensional cellular automata. Our program searches through a state space related to the de Bruijn graph of the automaton, using a method that combines features of breadth first and iterative deepening search, and includes fast bit-parallel graph reachability and path enumeration algorithms for finding the successors of each state. Successful results include a new 2c/7 spaceship in Life, found by searching a space with 2126 states.

This lecture series on cellular automata and complex systems is sponsored by the Santa Fe Institues's Fellows-at-Large Program 2000 and taking place at Cal State Northridge.

Department of Mathematics

return to main page