Concurrency vs. sequential interleavings in 1-D threshold cellular automata

Cellular automata (CA) are an abstract model of fine-grain parallelism, as the node update operations are rather simple, and therefore comparable to the basic operations of the computer hardware. In a classical CA, all the nodes execute their operations in parallel, that is, (logically) simultaneously. We consider herewith the sequential version of CA, or SCA, and compare it with the classical, parallel CA. In particular, we show that there are 1-D CA with very simple 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 computation on a chosen input, we find it both non-trivial, and having some important and far-reaching implications when applied to all possible inputs and, moreover, to the entire nontrivial classes of CA (SCA). We also share some thoughts on how to extend our results herein, and we try motivate the study of genuinely asynchronous cellular automata.