Reversible computing is bi-deterministic which means that its execution is both forward and backward deterministic, i.e. next/previous computational step is uniquely determined. Various approaches exist to catch its extensional or intensional aspects and properties. We present a class RPRF of reversible functions which holds at bay intensional aspects and emphasizes the extensional side of the reversible computation by following the style of Dedekind-Robinson Primitive Recursive Functions. The class RPRF is closed by inversion, can only express bijections on integers — not only natural numbers —, is expressive enough to embed Primitive Recursive Functions and, of course, its evaluation is effective.

A Class of Reversible Primitive Recursive Functions

PAOLINI, LUCA LUIGI;PICCOLO, Mauro;ROVERSI, Luca
2016-01-01

Abstract

Reversible computing is bi-deterministic which means that its execution is both forward and backward deterministic, i.e. next/previous computational step is uniquely determined. Various approaches exist to catch its extensional or intensional aspects and properties. We present a class RPRF of reversible functions which holds at bay intensional aspects and emphasizes the extensional side of the reversible computation by following the style of Dedekind-Robinson Primitive Recursive Functions. The class RPRF is closed by inversion, can only express bijections on integers — not only natural numbers —, is expressive enough to embed Primitive Recursive Functions and, of course, its evaluation is effective.
ICTCS2015
Milano
2015
322
227
242
http://dx.doi.org/10.1016/j.entcs.2016.03.016
Reversible computing, Recursive permutations, Primitive Recursive Functions.
Paolini, Luca; Piccolo, Mauro; Roversi, Luca
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S157106611630024X-main.pdf

Accesso aperto

Tipo di file: PDF EDITORIALE
Dimensione 319.04 kB
Formato Adobe PDF
319.04 kB Adobe PDF Visualizza/Apri

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/1558982
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 16
  • ???jsp.display-item.citation.isi??? 12
social impact