Reversible Conservative Rational Abstract Geometrical Computation Is Turing-Universal.

In Abstract geometrical computation for black hole computation (MCU '04, LNCS 3354), the author provides a setting based on rational numbers, abstract geometrical computation, with super-Turing capability. In the present paper, we prove the Turing computing capability of reversible conservative abstract geometrical computation. Reversibility allows backtracking as well as saving energy; it corresponds here to the local reversibility of collisions. Conservativeness corresponds to the preservation of another energy measure ensuring that the number of signals remains bounded. We first consider 2-counter automata enhanced with a stack to keep track of the computation. Then we built a simulation by reversible conservative rational signal machines. Keywords: Abstract geometrical computation, Conservativeness, Rational numbers, Reversibility, Turing-computability, 2-counter automata. [ABSTRACT FROM AUTHOR]