Computing with cellular automata: Three cases for nonuniformity

Recently, there has been a resurgence of interest in the use of cellular automata (CA) as computational devices. This paper demonstrates the advantages of nonuniform CAs, in which cellular rules may be heterogeneous, over the classical, uniform model. We address three problems that require global computation: parity, symmetry, and synchronization, showing that: (1) there does not exist a uniform, radius r=1 CA that effectively computes a solution, while (2) construction of a nonuniform CA is straightforward.