Computing Inside the Billiard Ball Model

International audienceThe chapter studies relations between billiard ball model, reversible cellular automata, conservative and reversible logics and Turing machines. At first we introduce block cellular automata and consider the automata reversibility and simulation dependencies between the block cellular automata and classical cellular automata. We prove that there exists a universal, i.e. simulating any Turing machine, block cellular automaton with eleven states, which is geometrically minimal. Basics of the billiard ball model and presentation of an information in the model are discussed then. We demonstrate how to implement ball movement, reflection of a signal, delays and cycles, collision of signals in configurations of the cellular automaton with Margolus neighborhood. Realizations of Fredkin gate and NOT gate with dual signal encoding are offered. The rest of the chapter deals with a Turing and an intrinsic universality, and uncomputable properties of the billiard ball model. The Turing universality is proved via simulation of a two-counter automaton, which itself is Turing universal. We demonstrate that the billiard ball model is intrinsically universal, or complete, in a class of reversible cellular automata, i.e. the model can simulate any reversible automaton over finite or infinite configurations. A novel notion of space-time simulation, that employs whole space-time diagrams of automaton evolution, is brought up. It is proved that the billiard ball model is also able to space-time simulate any (ir)reversible cellular automaton. Since the billiard ball model possesses the Turing computation power we can project a Turing machine’s halting problem to development of cellular automaton simulating the billiard ball model. Namely, we uncover a connection between undecidability of computation and high unpredictability of configurations of the billiard ball model