Back to the universality of the billiard ball model. (English) Zbl 1007.68124
Summary: A full construction of the universality of the billiard ball model, a lattice gas model introduced by Margolus in 84 is provided. The BBM is a reversible two-dimensional block cellular automaton with two states. Fredkin’s gate and reversible logic can be emulated inside the billiard ball model. They are use to embed two-counters automata, a model universal for computation.
In the one-dimensional case, there exists a universal block cellular automaton with 11 states.
In the one-dimensional case, there exists a universal block cellular automaton with 11 states.
MSC:
| 68Q80 | Cellular automata (computational aspects) |
| 37B99 | Topological dynamics |
| 37N99 | Applications of dynamical systems |
| 82C20 | Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics |
