Computability in Europe 2006
Logical Approaches to Computational Barriers

Regular Talk:
Reversible conservative rational abstract geometrical computation is Turing-universal

Speaker: Jérôme Durand-Lose
Slot: Array, 17:00-17:20, col. 5


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.
the present paper, we prove  the Turing computing capability
of reversible conservative abstract geometrical computation.
allows backtracking as well as saving energy; it corresponds here to
the local reversibility of collisions.
corresponds to the preservation of some other energy 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 prove that they can be simulated by reversible conservative
signal machines. 

websites: Arnold Beckmann 2006-04-19