Computability in Europe 2006
Logical Approaches to Computational Barriers

Print current page  Print this page

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

Speaker: Jérôme Durand-Lose
Presentation: Expose.pdf
Slot: Sat, 17:00-17:20, Faraday J (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 Valid HTML 4.01! Valid CSS! eXTReMe Tracker hit counters by www.free-counters.net