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 |