nach oben

New Generation Computing

Erschienen in:

04.07.2022

Making Programs Reversible with Minimal Extra Data

verfasst von: Robert Glück, Tetsuo Yokoyama

Erschienen in: New Generation Computing | Ausgabe 2/2022

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Vorheriger Artikel Codensity Games for Bisimilarity

Nächster Artikel Embedding Non-linear Pattern Matching with Backtracking for Non-free Data Types into Haskell

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

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.

We abbreviate argument parentheses, e.g., we write \({ fst }(\texttt {x.y})\) instead of \({ fst }(\texttt {(x.y)})\) [14].

We have \(|\texttt {nil}|=1\), and hence \(|\{\texttt {nil}\}| \ne |\{\}|\). The size differs from [14], where \(|\texttt {nil}|=0\).

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\).

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

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)

Bennett, C.H.: Logical reversibility of computation. IBM J. Res. Dev. 17(6), 525–532 (1973)MathSciNetCrossRef

Bennett, C.H.: Time/space trade-offs for reversible computation. SIAM J. Comput. 18(4), 766–776 (1989)MathSciNetCrossRef

De Vos, A.: Endoreversible models for the thermodynamics of computing. Entropy 22(6), 660 (2020)MathSciNetCrossRef

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)

Feynman, R.P.: Feynman Lectures on Computation. Addison-Wesley, Boston (1996)

Frank, M.P.: Reversibility for efficient computing. PhD thesis, Massachusetts Institute of Technology (1999)

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.

Jones, N.D.: Computability and Complexity: From a Programming Perspective. MIT Press, Cambridge (1997). Revised version, available from http://www.diku.dk/~neil/Comp2book.html

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.

Krakovsky, M.: Taking the heat. Commun. ACM 64(6), 18–20 (2021)CrossRef

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)

Titel: Making Programs Reversible with Minimal Extra Data
verfasst von: Robert Glück
Tetsuo Yokoyama
Publikationsdatum: 04.07.2022
Verlag: Ohmsha
Erschienen in: New Generation Computing / Ausgabe 2/2022
Print ISSN: 0288-3635
Elektronische ISSN: 1882-7055
DOI: https://doi.org/10.1007/s00354-022-00169-z

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2/2022

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

On the Computational Power of Phosphate Transfer Reaction Networks

DNA Concentration Regulator That can be Driven for a Long Time

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

Autonomous and Programmable Strand Generator Implemented as DNA and Enzymatic Chemical Reaction Cascade

Embedding Non-linear Pattern Matching with Backtracking for Non-free Data Types into Haskell

Premium Partner