2022年7月4日
Making Programs Reversible with Minimal Extra Data
New Generation Computing
- ,
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1007/s00354-022-00169-z
- 出版者・発行元
- Springer Science and Business Media {LLC}
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.
- リンク情報
- ID情報
-
- DOI : 10.1007/s00354-022-00169-z
- ISSN : 0288-3635
- eISSN : 1882-7055
- ORCIDのPut Code : 115377337