Bilinear Cellular Automata
Ron Bartlett
Mathematical Sciences,
Denison University,
Granville, Ohio 43023 USA
Max Garzon
Mathematical Sciences,
The University of Memphis,
Memphis, Tennessee 38152 USA,
Abstract
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.
