Two-Dimensional FHP Lattice Gases Are Computation Universal
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.
