Top

Published in:

2012 | OriginalPaper | Chapter

Reversible Cellular Automata

Author : Kenichi Morita

Published in: Handbook of Natural Computing

Publisher: Springer Berlin Heidelberg

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

search-config

AI-assisted search

Off

Abstract

A reversible cellular automaton (RCA) is a special type of cellular automaton (CA) such that every configuration of it has only one previous configuration, and hence its evolution process can be traced backward uniquely. Here, we discuss how RCAs are defined, their properties, how one can find and design them, and their computing abilities. After describing definitions on RCAs, a survey is given on basic properties on injectivity and surjectivity of their global functions. Three design methods of RCAs are then given: using CAs with block rules, partitioned CAs, and second-order CAs. Next, the computing ability of RCAs is discussed. In particular, we present simulation methods for irreversible CAs, reversible Turing machines, and some other universal systems by RCAs, in order to clarify the universality of RCAs. In spite of the strong constraint of reversibility, it can be seen that RCAs have rich abilities in computing and information processing, and even very simple RCAs have universal computing ability.

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 "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

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

previous chapter Universalities in Cellular Automata*

next chapter Conservation Laws in Cellular Automata

Amoroso S, Cooper G (1970) The Garden of Eden theorem for finite configurations. Proc Am Math Soc 26:158–164MathSciNetMATHCrossRef

Amoroso S, Patt YN (1972) Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures. J Comput Syst Sci 6:448–464MathSciNetMATHCrossRef

Bennett CH (1973) Logical reversibility of computation. IBM J Res Dev 17:525–532MATHCrossRef

Boykett T (2004) Efficient exhaustive listings of reversible one dimensional cellular automata. Theor Comput Sci 325:215–247MathSciNetMATHCrossRef

Cook M (2004) Universality in elementary cellular automata. Complex Syst 15:1–40MATH

Czeizler E, Kari J (2007) A tight linear bound for the synchronization delay of bijective automata. Theor Comput Sci 380:23–36MathSciNetMATHCrossRef

Durand-Lose J (1995) Reversible cellular automaton able to simulate any other reversible one using partitioning automata. In: Proceedings of LATIN 95, Valparaiso, Chile, LNCS 911. Springer, pp 230–244

Fredkin E, Toffoli T (1982) Conservative logic. Int J Theor Phys 21:219–253MathSciNetMATHCrossRef

Hedlund GA (1969) Endomorphisms and automorphisms of the shift dynamical system. Math Syst Theory 3:320–375MathSciNetMATHCrossRef

Imai K, Hori T, Morita K (2002) Self-reproduction in three-dimensional reversible cellular space. Artif Life 8:155–174CrossRef

Imai K, Morita K (1996) Firing squad synchronization problem in reversible cellular automata. Theor Comput Sci 165:475–482MathSciNetMATHCrossRef

Imai K, Morita K (2000) A computation-universal two-dimensional 8-state triangular reversible cellular automaton. Theor Comput Sci 231:181–191MathSciNetMATHCrossRef

Kari J (1994) Reversibility and surjectivity problems of cellular automata. J Comput Syst Sci 48:149–182MathSciNetMATHCrossRef

Kari J (1996) Representation of reversible cellular automata with block permutations. Math Syst Theory 29:47–61MathSciNetMATH

Kari J (2005a) Theory of cellular automata: a survey. Theor Comput Sci 334:3–33MathSciNetMATHCrossRef

Kari J (2005b) Reversible cellular automata. In: Proceedings of the DLT 2005, Palermo, Italy, LNCS 3572. Springer, pp 57–68

Kutrib M, Malcher A (2008) Fast reversible language recognition using cellular automata. Inf Comput 206:1142–1151MathSciNetMATHCrossRef

Landauer R (1961) Irreversibility and heat generation in the computing process. IBM J Res Dev 5:183–191MathSciNetMATHCrossRef

Lecerf Y (1963) Machines de Turing réversibles — Reursive insolubilité en n ∈ N de l'équation u = θ ⁿ u, où θ est un isomorphisme de codes. Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences 257:2597–2600MathSciNet

Margolus N (1984) Physics-like model of computation. Physica 10D:81–95MathSciNet

Maruoka A, Kimura M (1976) Condition for injectivity of global maps for tessellation automata. Inf Control 32:158–162MathSciNetMATHCrossRef

Maruoka A, Kimura M (1979) Injectivity and surjectivity of parallel maps for cellular automata. J Comput Syst Sci 18:47–64MathSciNetMATHCrossRef

Minsky ML (1967) Computation: finite and infinite machines. Prentice-Hall, Englewood Cliffs, NJMATH

Moore EF (1962) Machine models of self-reproduction. In: Proceedings of the symposia in applied mathematics, vol 14. American Mathematical Society, New York, pp 17–33

Mora JCST, Vergara SVC, Martinez GJ, McIntosh HV (2005) Procedures for calculating reversible one-dimensional cellular automata. Physica D 202:134–141MathSciNetMATHCrossRef

Morita K (1995) Reversible simulation of one-dimensional irreversible cellular automata. Theor Comput Sci 148:157–163MATHCrossRef

Morita K (1996) Universality of a reversible two-counter machine. Theor Comput Sci 168:303–320MATHCrossRef

Morita K (2001a) Cellular automata and artificial life — computation and life in reversible cellular automata. In: Goles E, Martinez S (eds) Complex systems. Kluwer, Dordrecht, pp 151–200CrossRef

Morita K (2001b) A simple reversible logic element and cellular automata for reversible computing. In: Proceedings of the 3rd international conference on machines, computations, and universality, LNCS 2055. Springer, Heidelberg, Germany, pp 102–113

Morita K (2007) Simple universal one-dimensional reversible cellular automata. J Cell Autom 2:159–165MathSciNetMATH

Morita K (2008a) Reversible computing and cellular automata — a survey. Theor Comput Sci 395:101–131MATHCrossRef

Morita K (2008b) A 24-state universal one-dimensional reversible cellular automaton. In: Adamatzky A et al. (eds) Proceedings of AUTOMATA-2008. Luniver Press, Bristol, UK, pp 106–112

Morita K, Harao M (1989) Computation universality of one-dimensional reversible (injective) cellular automata. Trans IEICE Jpn E-72:758–762

Morita K, Imai K (1996) Self-reproduction in a reversible cellular space. Theor Comput Sci 168:337–366MathSciNetMATHCrossRef

Morita K, Yamaguchi Y (2007) A universal reversible Turing machine. In: Proceedings of the 5th international conference on machines, computations, and universality, LNCS 4664. Springer, pp 90–98

Morita K, Shirasaki A, Gono Y (1989) A 1-tape 2-symbol reversible Turing machine. Trans IEICE Jpn E-72:223–228

Morita K, Tojima Y, Imai K, Ogiro T (2002) Universal computing in reversible and number-conserving two-dimensional cellular spaces. In: Adamatzky A (ed) Collision-based computing. Springer, London, UK, pp 161–199CrossRef

Myhill J (1963) The converse of Moore's Garden-of-Eden theorem. Proc Am Math Soc 14:658–686MathSciNetCrossRef

von Neumann J (1966) In: Burks AW (ed) Theory of self-reproducing automata. The University of Illinois Press, Urbana, IL

Ollinger N (2002) The quest for small universal cellular automata. In: Proceedings of ICALP, LNCS 2380. Lyon, France, pp 318–329

Ollinger N, Richard G (2006) A particular universal cellular automaton, oai:hal.archives-ouvertes.fr:hal-00095821_v2

Richardson D (1972) Tessellations with local transformations. J Comput Syst Sci 6:373–388MATHCrossRef

Sutner K (1991) De Bruijn graphs and linear cellular automata. Complex Syst 5:19–31MathSciNetMATH

Sutner K (2004) The complexity of reversible cellular automata. Theor Comput Sci 325:317–328MathSciNetMATHCrossRef

Toffoli T (1977) Computation and construction universality of reversible cellular automata. J Comput Syst Sci 15:213–231MathSciNetMATHCrossRef

Toffoli T (1980) Reversible computing. In: de Bakker JW, van Leeuwen J (eds) Automata, languages and programming, LNCS 85. Springer, Berlin, Germany, pp 632–644CrossRef

Toffoli T, Margolus N (1987) Cellular automata machines. The MIT Press, Cambridge, MA

Toffoli T, Margolus N (1990) Invertible cellular automata: a review. Physica D 45:229–253MathSciNetMATHCrossRef

Toffoli T, Capobianco S, Mentrasti P (2004) How to turn a second-order cellular automaton into lattice gas: a new inversion scheme. Theor Comput Sci 325:329–344MathSciNetMATHCrossRef

Watrous J (1995) On one-dimensional quantum cellular automata. In: Proceedings of the 36th symposium on foundations of computer science. Las Vegas, NV. IEEE, pp 528–537

Wolfram S (2001) A new kind of science. Wolfram Media, Champaign, IL

Title: Reversible Cellular Automata
Author: Kenichi Morita
Publisher: Springer Berlin Heidelberg
Book: Handbook of Natural Computing
Print ISBN: 978-3-540-92909-3

Electronic ISBN: 978-3-540-92910-9

Copyright Year: 2012
DOI: https://doi.org/10.1007/978-3-540-92910-9_7

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner