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.

A class of Recursive Permutations which is Primitive Recursive complete

Paolini L.;Piccolo M.;Roversi L.
2020-01-01

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.
813
218
233
http://www.sciencedirect.com/science/article/pii/S0304397519307558
https://doi.org/10.1016/j.tcs.2019.11.029
Reversible computation, Unconventional computing models, Computable permutations, Primitive recursive functions, Recursion theory
Paolini L.; Piccolo M.; Roversi L.
File in questo prodotto:
File Dimensione Formato  
20-03-23-main-caricato-su-IRIS.pdf

Accesso aperto

Descrizione: Author's post-print con data di accettazione 26 11 2019
Tipo di file: POSTPRINT (VERSIONE FINALE DELL’AUTORE)
Dimensione 420.62 kB
Formato Adobe PDF
420.62 kB Adobe PDF Visualizza/Apri
A class of Recursive Permutations which is Primitive Recursive complete - TCS 2020 ori.pdf

Accesso riservato

Tipo di file: PDF EDITORIALE
Dimensione 480.77 kB
Formato Adobe PDF
480.77 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2318/1734163
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 2
social impact