Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
New Generation Computing
Published in: New Generation Computing 2/2022

04-07-2022

Making Programs Reversible with Minimal Extra Data

Authors: Robert Glück, Tetsuo Yokoyama

Published in: New Generation Computing | Issue 2/2022

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

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.
previous article Codensity Games for Bisimilarity
next article Embedding Non-linear Pattern Matching with Backtracking for Non-free Data Types into Haskell

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
Footnotes
1
The number of garbage lines is minimized to \(\lceil \log _2 k\rceil \), where k is the largest number of identical output bit patterns in the truth table of the given reversible circuit.
 
2
We abbreviate argument parentheses, e.g., we write \({ fst }(\texttt {x.y})\) instead of \({ fst }(\texttt {(x.y)})\) [14].
 
3
We have \(|\texttt {nil}|=1\), and hence \(|\{\texttt {nil}\}| \ne |\{\}|\). The size differs from [14], where \(|\texttt {nil}|=0\).
 
4
In general, \(\texttt {chk2}\) can be any program such that \(\texttt {(x.y)} \in \mathrm {dom}([\![\texttt {chk2}]\!]^\texttt {L}) \Leftrightarrow (\texttt {x},\texttt {y})\in S\).
 
Literature
1.
Abramov, S.M., Glück, R.: The universal resolving algorithm and its correctness: inverse computation in a functional language. Sci. Comput. Program. 43(2–3), 193–229 (2002)MathSciNetCrossRef
2.
Axelsen, H.B., Yokoyama, T.: Programming techniques for reversible comparison sorts. In: Feng, X., Park, S. (eds.) Programming Languages and Systems. Proceedings, vol. 9458. Lecture Notes in Computer Science, pp. 407–426. Springer, Berlin (2015)
3.
4.
5.
6.
Dijkstra, E.W.: Program inversion. In: Bauer, F.L., Broy, M. (eds.) Program Construction: International Summer School, vol. 69. Lecture Notes in Computer Science, pp. 54–57. Springer, Berlin (1979)
7.
Feynman, R.P.: Feynman Lectures on Computation. Addison-Wesley, Boston (1996)
8.
Frank, M.P.: Reversibility for efficient computing. PhD thesis, Massachusetts Institute of Technology (1999)
9.
Futamura, Y., Konishi, Z., Glück, R.: Program transformation system based on generalized partial computation. New Gener. Comput. 20(1), 75–99 (2002)CrossRef
10.
Glück, R., Kawada, Y., Hashimoto, T.: Transforming interpreters into inverse interpreters by partial evaluation. In: Partial Evaluation and Semantics-Based Program Manipulation. Proceedings, pp. 10–19. ACM Press, New York (2003)
11.
Glück, R., Yokoyama, T.: A linear-time self-interpreter of a reversible imperative language. Comput. Softw. 33(3), 108–128 (2016)
12.
Glück, R., Yokoyama, T.: Reversible computing from a programming language perspective. Theor. Comput. Sci. (2022, in preparation)
13.
Hagiya, M., et al.: On DNA-based gellular automata. In: Ibarra, O.H., Kari, L., Kopecki, S. (eds.) Unconventional Computation and Natural Computation. Proceedings, vol. 8553. Lecture Notes in Computer Science, pp. 177–189. Springer, Berlin (2014)
14.
15.
Kawabe, M., Glück, R.: The program inverter LRinv and its structure. In: Hermenegildo, M., Cabeza, D. (eds.) Practical Aspects of Declarative Languages. Proceedings, vol. 3350. Lecture Notes in Computer Science, pp. 219–234. Springer, Berlin (2005)
16.
17.
Landauer, R.: Irreversibility and heat generation in the computing process. IBM J. Res. Dev. 5(3), 183–191 (1961)MathSciNetCrossRef
18.
Lange, K.-J., McKenzie, P., Tapp, A.: Reversible space equals deterministic space. J. Comput. Syst. Sci. 60(2), 354–367 (2000)MathSciNetCrossRef
19.
Levin, L.A.: Universal sequential search problems. Probl. Inf. Transm. 9(3), 265–266 (1975). Translated from Probl. Peredachi Inf. 9(3), 115–116 (1973)
20.
Maslov, D., Dueck, G.W.: Reversible cascades with minimal garbage. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 23(11), 1497–1509 (2006)
21.
McCarthy, J.: The inversion of functions defined by Turing machines. In: Shannon, C.E., McCarthy, J. (eds.) Automata Studies, pp. 177–181. Princeton University Press, Princeton (1956)
22.
Morita, K.: Theory of Reversible Computing. Monographs in Theoretical Computer Science. Springer, Berlin (2017)CrossRef
23.
Perumalla, K.S.: Introduction to Reversible Computing. CRC Press, Boca Raton (2013)CrossRef
24.
Toffoli, T.: Reversible computing. In: de Bakker, J., van Leeuwen, J. (eds.) Automata, Languages and Programming. Proceedings, vol. 85. Lecture Notes in Computer Science, pp. 632–644. Springer, Berlin (1980)
25.
Yokoyama, T., Axelsen, H.B., Glück, R.: Fundamentals of reversible flowchart languages. Theor. Comput. Sci. 611, 87–115 (2016)MathSciNetCrossRef
26.
Yokoyama, T., Glück, R.: A reversible programming language and its invertible self-interpreter. In: Partial Evaluation and Semantics-Based Program Manipulation. Proceedings, pp. 144–153. ACM Press, New York (2007)
Metadata
Title
Making Programs Reversible with Minimal Extra Data
Authors
Robert Glück
Tetsuo Yokoyama
Publication date
04-07-2022
Publisher
Ohmsha
Published in
New Generation Computing / Issue 2/2022
Print ISSN: 0288-3635
Electronic ISSN: 1882-7055
DOI
https://doi.org/10.1007/s00354-022-00169-z

Other articles of this Issue 2/2022

New Generation Computing 2/2022 Go to the issue

OriginalPaper

On the Computational Power of Phosphate Transfer Reaction Networks

OriginalPaper

Codensity Games for Bisimilarity

OriginalPaper

Helmholtz: A Verifier for Tezos Smart Contracts Based on Refinement Types

OriginalPaper

The Weak Universality of Two-Dimensional Five-State von Neumann Neighborhood Number-Conserving Cellular Automaton

OriginalPaper

Monotone Control of R Systems

EditorialNotes

Preface to Hagiya-sensei’s 26-th Birthday Special Issue

Premium Partner

    Image Credits