Concurrency vs. sequential interleavings in 1-D threshold cellular automata
Predrag T. Tošić, Gul Agha · 2004
Summary form only given. Cellular automata (CA) are an abstract model of fine-grain parallelism: the individual node update operations are rather simple, and therefore comparable to the basic operations of the computer hardware, yet the power of the model stems from the interaction and synergy of these simple local node computations that can often generate highly complex global behavior. In classical CA, all the nodes execute their operations in parallel, that is, (logically) simultaneously. We consider herein the sequential version of CA, or SCA, and compare and contrast SCA with the classical, parallel CA. We show that there are 1D CA with simple nonlinear node state update rules that cannot be simulated by any comparable SCA, irrespective of the node update ordering. While the result is trivial if one considers a single automaton's computations, we find this property quite interesting and having important implications when applied to all possible computations of entire nontrivial classes of CA (SCA). We also share some thoughts on how to extend the results herein, and, in particular, we try to motivate the study of genuinely asynchronous cellular automata.