Making Programs Reversible with Minimal Extra Data
Making Programs Reversible with Minimal Extra Data
复制标题
使用最少的额外数据使程序可逆
DOI：
10.1007/s00354-022-00169-z
复制
发表时间：
2022
影响因子：
2.6
通讯作者：
Yokoyama Tetsuo
中科院分区：
文献类型：
--
作者：
Glueck Robert;Yokoyama Tetsuo
可逆计算是一种非传统的计算范式，具有特定的挑战。其中一个重要的问题是存在具有最小额外输出（垃圾数据）的可逆程序。为了回答这个问题的程序，实现部分功能的可数域，我们介绍了一个无限垃圾集的顺序和极小的概念。为此，我们提出了两种方法指定的可判定和半判定谓词的功能。这两种方法都是通用的，这意味着它们适用于谓词指定的所有程序。他们涵盖了班尼特的经典输入擦除可逆计算内射函数。因此，任何用图灵完备编程语言编写的程序都可以在r-图灵完备可逆编程语言中用g-最小垃圾实现。这种通用性是以生成和测试方法带来的大量运行时间为代价的。
Reversible computing is an unconventional computing paradigm that comes with specific challenges. One of the important questions is the existence of reversible programs with minimal extra output (garbage data). To answer this question for programs that implement partial functions over countable domains, we introduce an order on infinite garbage sets and a notion of minimality. To this end, we present two methods for functions specified by decidable and semi-decidable predicates. Both methods are universal, which means they work for all programs specified by the predicates. They cover Bennett’s classic input-erasing reversible computation of injective functions. Hence, any program written in a Turing-complete programming language can be implemented with g-minimal garbage in an r-Turing-complete reversible programming language. This generality comes at the cost of a considerable runtime due to the generate-and-test approach.