Abstract & Keywords |
We focus on total functions in the theory of reversible computational models. We define a class of recursive permutations, dubbed Reversible Primitive Permutations (RPP) which are computable invertible total endo-functions on integers, so a subset of total reversible computations. RPP is generated from five basic functions (identity, sign-change, successor, predecessor, swap), two notions of composition (sequential and parallel), one functional iteration and one functional selection. RPP is closed by inversion and it is expressive enough to encode Cantor pairing and the whole class of Primitive Recursive Functions.
Keywords: Reversible computation, Unconventional computing models, Computable permutations, Primitive recursive functions, Recursion theory
|
@article{paolini2020tcs,
volume = {813},
author = {Luca Paolini and Mauro Piccolo and Luca Roversi},
issn = {0304-3975},
keywords = {Reversible computation, Unconventional computing models,
Computable permutations, Primitive recursive functions, Recursion
theory},
url = {http://www.sciencedirect.com/science/article/pii/S0304397519307558},
abstract = {We focus on total functions in the theory of reversible
computational models. We define a class of recursive permutations,
dubbed Reversible Primitive Permutations (RPP) which are
computable invertible total endo-functions on integers, so a
subset of total reversible computations. RPP is generated from
five basic functions (identity, sign-change, successor,
predecessor, swap), two notions of composition (sequential and
parallel), one functional iteration and one functional selection.
RPP is closed by inversion and it is expressive enough to encode
Cantor pairing and the whole class of Primitive Recursive
Functions.},
title = {A class of Recursive Permutations which is Primitive Recursive
complete},
pages = {218 - 233},
journal = {Theoretical Computer Science},
doi = {https://doi.org/10.1016/j.tcs.2019.11.029},
year = {2020},
}
This document was generated by bib2html 3.3.
(Modified by Luca Paolini, under the GNU General Public License)