Lattice-Gas vs Cellular Automata: The Whole Story at Last

摘要

Cellular automata (CA) and lattice-gas automata (LG) are two distinct "crystalline computation" schemes; each allows one to deal with a certain class of dynamical systems. CA provide a quick modeling route to phenomeno-logical aspects of nature - especially the emergence of complex behavior in dissipative systems - while LG are unmatched as a source of fine-grained models of fundamental aspects of physics - especially for expressing the dynamics of conservative systems. As in all polarized scientific debates, partisans of one approach may be tempted to disparage the other or - what is worse - in effect choose to remain ignorant of it. To which side is a poor entry-level researcher supposed to listen? This paper is intended to be a "Guide to the Perplexed." Today, thanks to very recent results, we are in a position to defuse the argument. Even though CA and LG are somewhat different programming languages (different primitives and constructs), it has emerged that their respective expressive ranges - the classes of dynamical systems they can model - virtually coincide! This renders moot the what-they-can do aspect of the contrast, and put the stress instead on how-they-do-it. Depending on the audience and the application, there are sound reasons - technical and pedagogical - for treating CA and LG at least as distinct modeling schools. Should it be a surprise that "What is ox in the stable is beef on the table?" The non-ignorable message is that these two styles of parallel computation embody (and impose on the researcher) opposite tradeoffs between the structural complexity of the computing machinery on which we choose to run a model and its thermodynamic efficiency.