Reversible conservative rational abstract geometrical computation is Turing-universal

Abstract : In 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.
Type de document :
Communication dans un congrès
2nd Conference on Computability in Europe (CiE '06), Jun 2006, Swansea, United Kingdom. Springer, Lecture Notes in Computer Science, pp.163-172, 2006, Logical Approaches to Computational Barriers Second Conference on Computability in Europe, CiE 2006, Swansea, UK, June 30-July 5, 2006. Proceedings. 〈10.1007/11780342_18〉
Liste complète des métadonnées

Littérature citée [32 références]  Voir  Masquer  Télécharger

https://hal.archives-ouvertes.fr/hal-00079687
Contributeur : Jérôme Durand-Lose <>
Soumis le : dimanche 12 février 2017 - 20:27:54
Dernière modification le : vendredi 17 février 2017 - 01:02:35
Document(s) archivé(s) le : samedi 13 mai 2017 - 12:24:02

Fichier

2006_CiE.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Jérôme Durand-Lose. Reversible conservative rational abstract geometrical computation is Turing-universal. 2nd Conference on Computability in Europe (CiE '06), Jun 2006, Swansea, United Kingdom. Springer, Lecture Notes in Computer Science, pp.163-172, 2006, Logical Approaches to Computational Barriers Second Conference on Computability in Europe, CiE 2006, Swansea, UK, June 30-July 5, 2006. Proceedings. 〈10.1007/11780342_18〉. 〈hal-00079687〉

Partager

Métriques

Consultations de
la notice

92

Téléchargements du document

35