Complex Systems

Two-Dimensional FHP Lattice Gases Are Computation Universal Download PDF

Richard K. Squier
Computer Science Department, Georgetown University,
Washington, DC 20057, USA

Kenneth Steiglitz
Computer Science Department, Princeton University,
Princeton, NJ 08544, USA

Abstract

We show that the FHP lattice gases are computation universal, implying that general questions about their behavior are undecidable. The proof embeds a universal one-dimensional cellular automaton in the two-dimensional FHP lattice gas. This provides evidence that general questions about fluid behavior are undecidable.