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

Abstract

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 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