Complex Systems

Bilinear Cellular Automata Download PDF

Ron Bartlett
Mathematical Sciences,
Denison University,
Granville, Ohio 43023 USA

Max Garzon
Mathematical Sciences,
The University of Memphis,
Memphis, Tennessee 38152 USA,


Bilinear cellular automata (CA) are those whose next state may be expressed as a bilinear form (inner product) of the neighboring states. In this paper it is shown that, unlike linear CA, the bilinear CA over are -universal, that is, capable of simulating any CA of the same dimension, and hence also capable of simulating any (universal) Turing machine. Evidence is given that the bilinear CA over , the integers modulo , may be universal as well. (Although, like Conway's Game of Life, this appears to be difficult to establish, even for a prime number of states.) A fairly complete Wolfram classification of the bilinear CA over is also given.