Article

Reversible Space Equals Deterministic Space

Authors:

Klaus-Jorn Lange,

Pierre McKenzie,

Alain TappAuthors Info & Claims

CCC '97: Proceedings of the 12th Annual IEEE Conference on Computational Complexity

Page 45

Published: 24 June 1997 Publication History

Abstract

This paper describes the simulation of an S(n) space-bounded deterministic Turing machine by a reversible Turing machine operating in space S(n). It thus answers a question posed by Bennett in 1989 and refutes the conjecture, made by Li and Vitanyi in 1996, that any reversible simulation of an irreversible computation must obey Bennett's reversible pebble game rules.

References

[1]

C. BENNETT, Logical reversibility of computation, IBM. J. Res. Develop. 17 (1973), pp. 525-532.

Digital Library

[2]

C. BENNETT, Time/space trade-offs for reversible computation. SIAM J. Comput. 81:4 (1989). pp. 766-776.

Digital Library

[3]

G. BRASSARD, A quantum jump in Computer Science, in Computer Science Today ed. J. van Leeuwen, Lecture Notes in Computer Science, Volume 1000 (special anniversary volume), Springer-Verlag (1995), pp. 1-14.

[4]

J. VON NEUMANN, Theory of self-reproducing automata, A.W. Burks, Ed., Univ. Illinois Press, Urbana (1966).

Digital Library

[5]

S.A. COOK, A taxonomy of problems with fast parallel algorithms, Information and Control 64 (1985), pp. 2-22.

Digital Library

[6]

S.A. COOK AND P. MCKENZIE, Problems complete for deterministic logarithmic space, J. Algorithms 8 (1987), pp. 385-394.

Digital Library

[7]

D. DEUTSCH, Quantum theory, the Church-Turing principle and the universal quantum computer, Proc. Royal Soc. London, Series A 400 (1985), pp. 97-117.

[8]

J.E. HOPCROFT AND J.D. ULLMAN, Introduction to Automata Theory, languages, and Computation, Addison-Wesley (1979).

Digital Library

[9]

M. KARCHMER AND A. WIGDERSON, On span programs, Proc. 8th IEEE Structure in Complexity Theory Conference (1993), pp. 102-111.

[10]

R. LANDAUER, Irreversibility and heat generation in the computing process, IBM J. Res. Develop. 5 (1961), pp. 183- 191.

Digital Library

[11]

Y. LECERF, Machines de Turing réversibles. Insolubilité récursive en n ¿ N de l' équation u = ¿ⁿ, où, ¿ est un "isomorphisme de codes", Comptes Rendus 257 (1963), pp. 2597-2600.

[12]

R. LEVINE AND A. SHERMAN, A note on Bennett's time-space trade-off for reversible computation, SIAM J. Comput. 19:4 (1990), pp. 673-677.

Digital Library

[13]

P. LEWIS AND C. PAPADIMITRIOU, Symmetric space-bounded computation, Theoret. Comput. Sci. 19(1982), 161- 187.

[14]

M. LI AND P. VITANYI, Reversible simulation of irreversible computation, Proc. 11th IEEE Conference on Computational Complexity (1996), pp. 301-306.

Digital Library

[15]

M. LI AND P. VITANYI, Reversibility and adiabatic computation: trading time and space for energy, Proc. Royal Soc. London, Series A 452 (1996), pp. 769-789.

[16]

N. NISAN, RL ¿ SL, Proc. 24th ACM Symp. on Theory of Computing, (1992), pp. 619-623.

Digital Library

[17]

N. NISAN, E. SZEMEREDI, AND A. WIGDERSON, Undirected connectivity in O(log^1.5 n)space, Proc. 34th IEEE Symp. on Foundations of Computer Science (1992), pp. 24-29.

Digital Library

[18]

P. SHOR, Algorithms for quantum computation: Discrete log and factoring, Proc. 35th IEEE Symp. Foundations of Compo Sci. (1994), pp. 124-134.

Digital Library

[19]

MICHAEL SIPSER, Halting Space-Bounded Computations. Theoretical Computer Science 10 (l990). pp. 335-338.

Cited By

Demaine ELynch JMirano GTyagi NSudan M(2016)Energy-Efficient AlgorithmsProceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science10.1145/2840728.2840756(321-332)Online publication date: 14-Jan-2016
https://dl.acm.org/doi/10.1145/2840728.2840756
Buhrman HCleve RKoucký MLoff BSpeelman FShmoys D(2014)Computing with a full memoryProceedings of the forty-sixth annual ACM symposium on Theory of computing10.1145/2591796.2591874(857-866)Online publication date: 31-May-2014
https://dl.acm.org/doi/10.1145/2591796.2591874
Buhrman HFehr SSchaffner CSpeelman FKleinberg R(2013)The garden-hose modelProceedings of the 4th conference on Innovations in Theoretical Computer Science10.1145/2422436.2422455(145-158)Online publication date: 9-Jan-2013
https://dl.acm.org/doi/10.1145/2422436.2422455
Show More Cited By

Reversible Space Equals Deterministic Space
1. Theory of computation
  1. Models of computation
    1. Computability

Recommendations

Deterministic and unambiguous two-dimensional languages over one-letter alphabet

The paper focuses on deterministic and unambiguous recognizable two-dimensional languages with particular attention to the case of a one-letter alphabet. The family DREC(1) of deterministic languages over a one-letter alphabet is characterized as both L(...
Reversible multi-head finite automata characterize reversible logarithmic space
LATA'12: Proceedings of the 6th international conference on Language and Automata Theory and Applications

Deterministic and non-deterministic multi-head finite automata are known to characterize the deterministic and non- deterministic logarithmic space complexity classes, respectively. Recently, Morita introduced reversible multi-head finite automata (...
Relativizing Time, Space, and Time-Space

Consider the classes of formal languages specified by nondeterministic acceptors that operate simultaneously within time bounds from a set $\mathcal{T}$ and space bounds from a set $\mathcal{S}$. How large must the time bounds be in order to obtain all of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

CCC '97: Proceedings of the 12th Annual IEEE Conference on Computational Complexity

June 1997

ISBN:0818679077

Copyright © Copyright (c) 1997 Institute of Electrical and Electronics Engineers, Inc. All rights reserved.

Publisher

IEEE Computer Society

United States

Publication History

Published: 24 June 1997

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Demaine ELynch JMirano GTyagi NSudan M(2016)Energy-Efficient AlgorithmsProceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science10.1145/2840728.2840756(321-332)Online publication date: 14-Jan-2016
https://dl.acm.org/doi/10.1145/2840728.2840756
Buhrman HCleve RKoucký MLoff BSpeelman FShmoys D(2014)Computing with a full memoryProceedings of the forty-sixth annual ACM symposium on Theory of computing10.1145/2591796.2591874(857-866)Online publication date: 31-May-2014
https://dl.acm.org/doi/10.1145/2591796.2591874
Buhrman HFehr SSchaffner CSpeelman FKleinberg R(2013)The garden-hose modelProceedings of the 4th conference on Innovations in Theoretical Computer Science10.1145/2422436.2422455(145-158)Online publication date: 9-Jan-2013
https://dl.acm.org/doi/10.1145/2422436.2422455
Frank MBagherzadeh NValero MRamirez A(2005)Introduction to reversible computingProceedings of the 2nd conference on Computing frontiers10.1145/1062261.1062324(385-390)Online publication date: 4-May-2005
https://dl.acm.org/doi/10.1145/1062261.1062324
Flake GBaum E(2002)Rush Hour is PSAPCE-complete, or "Why you should generously tip parking lot attendants"Theoretical Computer Science10.1016/S0304-3975(01)00173-6270:1-2(895-911)Online publication date: 6-Jan-2002
https://dl.acm.org/doi/10.1016/S0304-3975%2801%2900173-6

View Options

View options

Media

Figures

Other

Tables

View Table of Contents