Dissipative CA Computation Without Power Sources?

Silvio Capobianco and Tommaso Toffoli

Usual implementations of cellular automata employ both power-thirsty fanout operations and local, many-to-one, entropy-spilling transformations. We study the possibility of rewriting cellular automata as lattice-gas automata, and show how their propagation-collision discipline removes the requirement for fanout—and thus, in principle, for a power source.

Keywords: cellular automaton, lattice-gas automaton, rewriting