The Topological Skeleton of Cellular Automaton Dynamics


next up previous
Next: Introduction

The Topological Skeleton of Cellular Automaton Dynamics

Howard Gutowitz and Christophe Domain
Ecole Supérieure de Physique
et Chimie Industrielles
10 rue Vauquelin
75005 Paris
and
The Santa Fe Institute
1399 Hyde Park Road
Santa Fe, NM 87501

Abstract:

We have developed statistical techniques to study the structure the state-transition graphs of cellular automata with periodic boundary conditions, in the limit of large system size. We organize our results around the concept of a topological skeleton. The topological skeleton is the set of physically relevant states. Covering this skeleton is a surface, typically thin and dense, which contains the bulk of the set of states. States in the skeleton have some long histories. States on the surface, by contrast, have only short histories; they are reached only near the beginning of cellular automaton evolution. We study in detail a sequence of rules which exhibit mostly skeletal to mostly surface structure.




Wed Apr 17 13:31:15 BST 1996