Computability in Europe 2006
Logical Approaches to Computational Barriers
Logical Approaches to Computational Barriers
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
|