A Class of Reversible Primitive Recursive Functions

详细信息    查看全文

• 作者：Luca Paolini¹ ; ^{luca.paolini@unito.it" class="auth_mail" title="E-mail the corresponding author} ; Mauro Piccolo¹ ; ^{mauro.piccolo@unito.it" class="auth_mail" title="E-mail the corresponding author} ; Luca Roversi¹ ; ^{luca.roversi@unito.it" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Reversible computing ; Recursive permutations ; Primitive Recursive Functions
• 刊名：Electronic Notes in Theoretical Computer Science
• 出版年：2016
• 出版时间：18 April 2016
• 年：2016
• 卷：322
• 期：Complete
• 页码：227-242
• 全文大小：319 K

文摘

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 —, and it is expressive enough to simulate Primitive Recursive Functions, of course, in an effective way.