Luca
Roversi
https://link.springer.com/10.1007%2Fs00354-018-0039-1
https://scigraph.springernature.com/explorer/license/
articles
false
2019-04-11T09:49
On a Class of Reversible Primitive Recursive Functions and Its Turing-Complete Extensions
233-256
2018-07
research_article
Reversible computing is both forward and backward deterministic. This means that a uniquely determined step exists from the previous computational configuration (backward determinism) to the next one (forward determinism) and vice versa. We present the reversible primitive recursive functions (RPRF), a class of reversible (endo-)functions over natural numbers which allows to capture interesting extensional aspects of reversible computation in a formalism quite close to that of classical primitive recursive functions. The class RPRF can express bijections over integers (not only natural numbers), is expressive enough to admit an embedding of the primitive recursive functions and, of course, its evaluation is effective. We also extend RPRF to obtain a new class of functions which are effective and Turing complete, and represent all Kleene’s μ-recursive functions. Finally, we consider reversible recursion schemes that lead outside the reversible endo-functions.
2018-07-01
en
pub.1106124144
dimensions_id
Mauro
Piccolo
Paolini
Luca
readcube_id
48517fa6d7daf5ccf62b19e1b18ac65c8406def66d827975c2446188c7d44374
University of Turin
Dipartimento di Informatica, Università di Torino, Corso Svizzera 185, 10149, Torino, Italy
3
doi
10.1007/s00354-018-0039-1
0288-3635
1882-7055
New Generation Computing
36
Information and Computing Sciences
Computation Theory and Mathematics
Springer Nature - SN SciGraph project