**paolini17sub (Technical report)
** |

Author(s) | Luca Paolini, Mauro Piccolo and Roversi Luca |

Title | « *A class of Recursive Permutations which is Primitive Recursive complete »* |

Institution | Rapporto dell'Università di Torino |

Year | 2017 |

Note | Submitted to TCS. |

**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, negation, successor, predecessor, swap), two notions of composition (sequential and parallel), one functional iteration and one functional selection. Also, RPP is closed by inversion, is expressive enough to encode Cantor pairing and the whole class of Primitive Recursive Functions. |

Download the complete article:

```
@techreport{paolini17sub,
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, negation, successor, predecessor,
swap), two notions of composition (sequential and parallel), one
functional iteration and one functional selection. Also, RPP is
closed by inversion, is expressive enough to encode Cantor pairing
and the whole class of Primitive Recursive Functions.},
localfile = {http://www.di.unito.it/~paolini/papers/2017rpp.pdf},
title = {A class of Recursive Permutations which is Primitive Recursive
complete},
author = {Paolini, Luca and Piccolo, Mauro and Roversi Luca},
note = {Submitted to {TCS}.},
year = 2017,
institution = {Rapporto dell'Universit\`a di Torino},
}
```

This document was generated by bib2html 3.3.

(Modified by Luca Paolini, under the GNU General Public License)