Abstract
Reversible computation has attracted much attention over the years, not only for its promise for computers with radically reduced power consumption, but also for its importance for Quantum Computing. Though studied extensively in a great variety of synchronous computa- tion models, it is virtually unexplored in an asynchronous framework. Particularly suitable asynchronous models for the study of reversibility are asynchronous cellular automata. Simple yet powerful, they update their cells at random times that are independent of each other. In this paper, we present the embedding of a universal reversible Turing machine (RTM) in a two-dimensional self-timed cellular automaton (STCA), a special type of asynchronous cellular automaton, of which each cell uses four bits to store its state, and a transition on a cell accesses only these four bits and one bit of each of the four neighboring cells. The embedding of a universal RTM on an STCA requires merely four rotation-symmetric transition rules, which are bit-conserving and locally reversible. We show that the model is globally reversible.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Frank, M., Vieri, C., Ammer, M.J., Love N., Margolus, N.H., Knight T. Jr.: A scalable reversible computer in silicon. In: Calude, C.S., Casti, J., Dinneen, M.J. (eds.): Unconventional Models of Computation, Springer-Verlag, Singapore (1998) 183–200
Fredkin, E., Toffoli, T.: Conservative logic. Int. J. Theoretical Physics 21(3–4) (1982) 219–253
Hertling, P.: Embedding cellular automata into reversible ones. In: Calude, C.S., Casti, J., Dinneen, M.J. (eds.): Unconventional Models of Computation, Springer-Verlag, Singapore (1998) 243–256
Imai, K., Morita, K.: A computation-universal two-dimensional 8-state triangular reversible cellular automaton. Theoretical Computer Science 231(2) (2000) 181–191
Landauer, R.: Irreversibility and heat generation in the computing process. IBM J. Research and Development 5 (1961) 183–191
Margolus, N.: Physics-like models of computation. Physica D 10 (1984) 81–95
Morita, K.: A simple universal logic element and cellular automata for reversible computing. Lecture Notes in Computer Science 2055 (2001) 102–113
Morita, K., Tojima, Y., Imai, K.: A simple computer embedded in a reversible and number-conserving two-dimensional cellular space. Multi. Val. Logic 6 (2001) 483–514
Peper, F., Isokawa, T., Kouda, N., Matsui, N.: Self-timed cellular automata and their computational ability. Future Generation Computer Systems 18(7) (2002) 893–904
Peper, F., Lee, J., Adachi, S., Mashiko, S.: Laying out circuits on asynchronous cellular arrays: towards feasible nanocomputers. (submitted)
Toffoli, T.: Computation and construction universality of reversible cellular automata. J. Computer and System Sciences 15 (1977) 213–231
Author information
Authors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lee, J., Peper, F., Adachi, S., Morita, K., Mashiko, S. (2002). Reversible Computation in Asynchronous Cellular Automata. In: Unconventional Models of Computation. UMC 2002. Lecture Notes in Computer Science, vol 2509. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45833-6_19
Download citation
DOI: https://doi.org/10.1007/3-540-45833-6_19
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44311-7
Online ISBN: 978-3-540-45833-3
eBook Packages: Springer Book Archive