Reversible Conservative Rational Abstract Geometrical Computation Is Turing-Universal | Zendy

Jérôme Durand-Lose | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Reversible Conservative Rational Abstract Geometrical Computation Is Turing-Universal

Author(s) -

Jérôme Durand-Lose

Publication year - 2006

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

ISBN - 3-540-35466-2

DOI - 10.1007/11780342_18

Subject(s) - computer science , turing machine , computation , turing , universal turing machine , time hierarchy theorem , super recursive algorithm , theoretical computer science , algebra over a field , algorithm , programming language , mathematics , pure mathematics

International audienceIn Abstract geometrical computation for black hole computation (MCU '04, LNCS 3354), the author provides a setting based on rational numb ers, 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

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research