When--and how--can a cellular automaton be rewritten as a lattice gas?

Tommaso Toffoli, Silvio Capobianco, Patrizia Mentrasti

Both cellular automata (CA) and lattice-gas automata (LG) provide finite algorithmic presentations for certain classes of infinite dynamical systems studied by symbolic dynamics; i…