Algorithmically Expressive, Always-Terminating Model for Reversible Computation

Autor:	Palazzo, Matteo, Roversi, Luca
Rok vydání:	2024
Předmět:	Computer Science - Programming Languages Computer Science - Logic in Computer Science D.3 F.3
Druh dokumentu:	Working Paper
Popis:	Concerning classical computational models able to express all the Primitive Recursive Functions (PRF), there are interesting results regarding limits on their algorithmic expressiveness or, equivalently, efficiency, namely the ability to express algorithms with minimal computational cost. By introducing the reversible programming model Forest, at our knowledge, we provide a first study of analogous properties, adapted to the context of reversible computational models that can represent all the functions in PRF. Firstly, we show that Forest extends Matos' linear reversible computational model MSRL, the very extension being a guaranteed terminating iteration that can be halted by means of logical predicates. The consequence is that Forest is PRF complete, because MSRL is. Secondly, we show that Forest is strictly algorithmically more expressive than MSRL: it can encode a reversible algorithm for the minimum between two integers in optimal time, while MSRL cannot. Comment: 16 pages, 4 figures, 2 listings
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2402.19012 Zobrazit plný text záznamu View this record from Arxiv