×

Invertible cellular automata: A review. (English) Zbl 0729.68066

Summary: In the light of recent developments in the theory of invertible cellular automata, we attempt to give a unified presentation of the subject and discuss its relevance to computer science and mathematical physics.

MSC:

68Q80 Cellular automata (computational aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aladyev, V., Computability in homogeneous structures, Izv. Akad. Nauk. Estonian SSR, Fiz.-Mat., 21, 80-83 (1972) · Zbl 0231.02046
[2] Amoroso, S.; Patt, Y. N., Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures, J. Comp. Syst. Sci., 6, 448-464 (1972) · Zbl 0263.94019
[3] Amoroso, S., Some clarifications of the concept of a Garden-of-Eden configuration, J. Comp. Syst. Sci., 10, 77-82 (1975) · Zbl 0348.94056
[4] Banks, E., Information processing and transmission in cellular automata, (Tech. Rep. MAC TR-81 (1971), MIT Project MAC)
[5] Benioff, P., Quantum mechanical Hamiltonian models of discrete processes that erase their own histories: applications to Turing machines, Int. J. Theor. Phys., 21, 177-201 (1982) · Zbl 0499.68021
[6] Bennett, C., Logical reversibility of computation, IBM J. Res. Develop., 6, 525-532 (1973) · Zbl 0267.68024
[7] Bennett, C.; Grinstein, G., Role of irreversibility in stabilizing complex and nonenergodic behavior in locally interacting discrete systems, Phys. Rev. Lett., 55, 657-660 (1985)
[8] Bennett, C., On the nature and origin of complexity in discrete, homogeneous, locally-interacting systems, Found. Phys., 16, 585-592 (1986)
[9] Bennett, C.; Margolus, N.; Toffoli, T., Bond-energy variables for Ising spin-glass dynamics, Phys. Rev. B, 37, 2254 (1988)
[10] (Bennett, C.; Toffoli, T.; Wolfram, S., Cellular Automata ’86. Cellular Automata ’86, Tech. Memo MIT/LCS/TM-317 (December 1986), MIT Lab. for Comp. Sci) · Zbl 0645.00008
[11] (Burks, A., Essays on Cellular Automata (1970), University of Illinois Press: University of Illinois Press Champaign, IL) · Zbl 0228.94013
[12] IBM J., 215-238 (March 1967), republished in English translation in
[13] Creutz, M., Deterministic Ising dynamics, Ann. Phys., 167, 62-76 (1986)
[14] Culik, K., On invertible cellular automata, Complex Systems, 1, 1035-1044 (1987) · Zbl 0657.68053
[15] Invariants in lattice gas models, (Monaco, R., Discrete Kinetic Theory, Lattice Gas Dynamics, and Foundations of Hydrodynamics (1989), World Scientific: World Scientific Singapore), 102-113
[16] (Doolen, G.; etal., Lattice-Gas Methods for Partial Differential Equations (1990), Addison-Wesley: Addison-Wesley New York)
[17] Everett, H., The theory of the universal wave function, (DeWitt, B.; Graham, N., The Many-World Interpretation of Quantum Mechanics (1973), Princeton Univ. Press: Princeton Univ. Press Princeton, NJ)
[18] Feynman, R., Quantum-mechanical computers, Opt. News. Opt. News, Found. Phys., 16, 507-531 (1986), reprinted in
[19] Fredkin, E.; Toffoli, T., Conservative logic, Int. J. Theor. Phys., 21, 219-253 (1982) · Zbl 0496.94015
[20] (Fredkin, E.; Landauer, R.; Toffoli, T., Proceedings of a Conference on Physics and Computation. Proceedings of a Conference on Physics and Computation, Int. J. Theor. Phys., 21 (1982)), 12
[21] Frisch, U.; Hasslacher, B.; Pomeau, Y., Lattice-gas automata for the Navier-Stokes equation, Phys. Rev. Lett., 56, 1505-1508 (1986)
[22] Frisch, U., Lattice gas hydrodynamics in two and three dimensions, (Doolen, G.; etal., Lattice-Gas Methods for Partial Differential Equations (1990), Addison-Wesley: Addison-Wesley New York), 77-135
[23] Gardner, M., The fantastic combinations of John Conway’s new solitaire game ‘Life’, Sci. Am., 223, 120-123 (April 1970)
[24] Gutowitz, H.; Victor, J. D.; Knight, B. W., Local structure theory for cellular automata, Physica D, 28, 18-48 (1987) · Zbl 0634.92022
[25] Gutowitz, H. A., A hierarchical classification of cellular automata, Physica D, 45, 136-156 (1990), these Proceedings · Zbl 0729.68056
[26] Hardy, J.; de Pazzis, O.; Pomeau, Y., Molecular dynamics of a classical lattice gas: transport properties and time correlation functions, Phys. Rev. A, 13, 1949-1960 (1976)
[27] Hasslacher, B., Discrete fluids, Los Alamos Science, 211-217 (1987), Special Issue No. 15
[28] Hayot, F., The effect of Galilean non-invariance in lattice gas automaton one-dimensional flow, Complex Systems, 1, 753-761 (1987)
[29] Head, T., One-dimensional cellular automata: injectivity from unambiguity, Complex Systems, 3 (1989), to appear in · Zbl 0725.68076
[30] Hedlund, G. A.; Appel, K. I.; Welch, L. R., All onto functions of span less than or equal to five, (Communications Research Division, working paper (July 1963))
[31] Hedlund, G. A., Endomorphism and automorphism of the shift dynamical system, Math. Syst. Theory, 3, 51-59 (1969)
[32] Hénon, M., Optimization of collision rules in the FCHC lattice gases and addition of rest particles, (Monaco, R., Discrete Kinetic Theory, Lattice Gas Dynamics, and Foundations of Hydrodynamics (1989), World Scientific: World Scientific Singapore), 146-159
[33] Hénon, M., On the relation between lattice gases and cellular automata, (Monaco, R., Discrete Kinetic Theory, Lattice Gas Dynamics, and Foundations of Hydrodynamics (1989), World Scientific: World Scientific Singapore), 160-161
[34] H. Hrgovčić, personal communication.; H. Hrgovčić, personal communication.
[35] Jacopini, G.; Sontacchi, G., Reversible parallel computation: an evolving space model, Theor. Comp. Sci., 75 (1990), to appear in · Zbl 0694.68040
[36] Jaynes, Information theory and statistical mechanics, Phys. Rev., 108, 171-190 (1957) · Zbl 0084.43701
[37] Kaneko, K., Symplectic cellular automata, Phys. Lett. A, 129, 9-16 (1988)
[38] Kari, J., Reversibility and surjectivity of cellular automata, (Licentiate’s Thesis (May 1989), University of Turku: University of Turku Finland) · Zbl 0802.68090
[39] Kari, J., Reversibility of 2D cellular automata is undecidable, Physica D, 45, 379-385 (1990), these Proceedings · Zbl 0729.68058
[40] (Lindenmayer, A.; Rozenberg, G., Automata, Language, and Development (1976), North-Holland: North-Holland Amsterdam) · Zbl 0346.92001
[41] Margolus, N., Physics-like models of computation, Physica D, 10, 81-95 (1984) · Zbl 0563.68051
[42] Margolus, N., Quantum computation, Ann. NY Acad. Sci., 480, 487-497 (1986)
[43] Margolus, N., Physics and Computation, (Tech. Rep. MIT/LCS/TR-415. Tech. Rep. MIT/LCS/TR-415, Ph. D. Thesis (March 1988), MIT Lab. for Comp. Sci)
[44] Margolus, N.; Toffoli, T., Cellular Automata Machines, (Doolen, G.; etal., Lattice-Gas Methods for Partial Differential Equations (1990), Addison-Wesley: Addison-Wesley New York), 219-248
[45] Margolus, N.; Toffoli, T.; Vichniac, G., Cellular automata supercomputers for fluid dynamics modeling, Phys. Rev. Lett., 56, 1694-1696 (1986)
[46] Maruoka, A.; Kimura, M., Conditions for injectivity of global maps for tessellation automata, Info. Control, 32, 158-162 (1976) · Zbl 0338.94030
[47] Maruoka, A.; Kimura, M., Injectivity and surjectivity of parallel maps for cellular automata, J. Comp. Syst. Sci., 18, 47-64 (1979) · Zbl 0411.68047
[48] Maruoka, A.; Kimura, M., Strong surjectivity is equivalent to \(C\)-injectivity, Theor. Comp. Sci., 18, 269-277 (1982) · Zbl 0477.68050
[49] (Monaco, R., Discrete Kinetic Theory, Lattice Gas Dynamics, and Foundations of Hydrodynamics (1989), World Scientific: World Scientific Singapore) · Zbl 0734.76002
[50] Morita, K.; Harao, M., Computation universality of one-dimensional reversible (injective) cellular automata, Trans. IEICE E, 72, 758-762 (1989)
[51] Moore, E., Machine models of self-reproduction, (Proc. Symp. Appl. Math., 14 (1962)). (Burks, A., Essays on Cellular Automata (1970), University of Illinois Press: University of Illinois Press Champaign, IL), 187-203, reprinted in: · Zbl 0233.94026
[52] Moore, E., The firing squad synchronization problem, (Moore, E. F., Sequential Machines (1964), Addison-Wesley: Addison-Wesley New York), 213-214 · Zbl 0192.07602
[53] Myhill, J., The converse of Moore’s garden-of-Eden theorem, (Proc. Am. Math. Soc., 14 (1963)). (Burks, A., Essays on Cellular Automata (1970), University of Illinois Press: University of Illinois Press Champaign, IL), 204-205, reprinted in: · Zbl 0233.94027
[54] Nasu, M., Local maps inducing surjective global maps of one-dimensional tessellation automata, Math. Syst. Theor., 11, 327-351 (1978) · Zbl 0389.68024
[55] Packard, N.; Wolfram, S., Two-dimensional cellular automata, J. Stat. Phys., 38, 901-946 (1985) · Zbl 0625.68038
[56] Patt, Y. N., Injections of neighborhood size three and four on the set of configurations from the infinite one-dimensional tessellation automata of two-state cells (1971), (unpublished report, cited in ref. [2]), ECON-N1-P-1, Ft. Monmouth, NJ 07703
[57] Petri, C. A., State-transition structures in physics and in computation, (Fredkin, E.; Landauer, R.; Toffoli, T., Proceedings of a Conference on Physics and Computation. Proceedings of a Conference on Physics and Computation, Int. J. Theor. Phys., 21 (1982)), 979-992 · Zbl 0497.68031
[58] Pomeau, Y., Invariant in cellular automata, J. Phys. A, 17, L415-L418 (1984) · Zbl 0537.68049
[59] Preston, K.; Duff, M., Modern Cellular Automata (1984), Plenum Press: Plenum Press New York · Zbl 0659.68082
[60] Richardson, D., Tessellation with local transformations, J. Comp. Syst. Sci., 6, 373-388 (1972) · Zbl 0246.94037
[61] Sato, T.; Nonda, N., Certain relations between properties of maps of tessellation automata, J. Comp. Syst. Sci., 15, 121-145 (1977) · Zbl 0379.94068
[62] Sears, M., The automorphisms of the shift dynamical systems are relatively sparse, Math. Syst. Theory, 5, 228-231 (1971) · Zbl 0221.54040
[63] Smith, A., Cellular automata theory, (Tech. Rep., 2 (1969), Stanford Electronic Lab., Stanford Univ)
[64] Takesue, S., Reversible cellular automata and statistical mechanics, Phys. Rev. Lett., 59, 2499-2502 (1987)
[65] Smith, M. A., Representations of geometrical and topological quantities in cellular automata, Physica D, 45, 271-277 (1990), these Proceedings · Zbl 0729.68064
[66] Takesue, S., Relaxation properties of elementary reversible cellular automata, Physica D, 45, 278-284 (1990), these Proceedings · Zbl 0711.58036
[67] Toffoli, T., Computation and construction universality of reversible cellular automata, J. Comp. Syst. Sci., 15, 213-231 (1977) · Zbl 0364.94085
[68] Toffoli, T., Cellular automata mechanics, (Tech. Rep. 208 (1977), Comp. Comm. Sci. Dept., The University of Michigan)
[69] Toffoli, T., Bicontinuous extension of reversible combinatorial functions, Math. Syst. Theory, 14, 13-23 (1981) · Zbl 0469.94020
[70] Toffoli, T., (de, Bakker; van, Leeuwen, Reversible Computing, Automata, Languages and Programming (1980), Springer: Springer Berlin), 632-644 · Zbl 0443.68038
[71] Toffoli, T., CAM: A high-performance cellular-automaton machine, Physica D, 10, 195-204 (1984)
[72] Toffoli, T., Cellular automata as an alternative to (rather than an approximation of) differential equations in modeling physics, Physica D, 10, 117-127 (1984) · Zbl 0563.68054
[73] Toffoli, T., Information transport obeying the continuity equation, IBM J. Res. Develop., 32, 1, 29-36 (January 1988)
[74] Toffoli, T., Four topics in lattice gases: ergodicity; relativity; information flow; and rule compression for parallel lattice-gas machines, (Monaco, R., Discrete Kinetic Theory, Lattice Gas Dynamics, and Foundations of Hydrodynamics (1989), World Scientific: World Scientific Singapore), 343-354
[75] Toffoli, T., How cheap can mechanics’ first principles be?, (Zurek, W. H., Complexity, Entropy, and the Physics of Information (1990), Addison-Wesley: Addison-Wesley Reading, MA), to appear in:
[76] Toffoli, T., Frontiers in computing, (Ritter, G. X., Information Processing 89 (1989), North-Holland: North-Holland Amsterdam), 1
[77] Toffoli, T.; Margolus, N., Cellular Automata Machines - A New Environment for Modeling (1987), MIT Press: MIT Press Cambridge, MA
[78] Toffoli, T.; Margolus, N., Programmable matter, (Doolen, G., Lattice Gas Methods for PDEs. Lattice Gas Methods for PDEs, Physica D, 46 (1990)), special issue, to appear
[79] T. Toffoli and N. Margolus, Invertible cellular automata, occasionaly updated technical memo (MIT Lab. for Comp. Sci.), eventually to appear in book form.; T. Toffoli and N. Margolus, Invertible cellular automata, occasionaly updated technical memo (MIT Lab. for Comp. Sci.), eventually to appear in book form.
[80] G. ’t Hooft, A two-dimensional model with discrete general coordinate-invariance, preprint.; G. ’t Hooft, A two-dimensional model with discrete general coordinate-invariance, preprint.
[81] Turing, A., On computable numbers, with an application to the Entscheidungsproblem, (Proc. London Math. Soc. Ser. 2, 42 (1936)), 230-265
[82] Ulam, S., Random processes and transformations, (Proc. Int. Congr. Mathem. (held in 1950), 2 (1952)), 264-275 · Zbl 0049.09511
[83] Vichniac, G., Simulating physics with cellular automata, Physica D, 10, 96-115 (1984) · Zbl 0563.68053
[84] von Neumann, J., (Burks, A., Theory of Self-Reproducing Automata (1966), University of Illinois Press: University of Illinois Press Champaign, IL)
[85] Wolfram, S., Statistical mechanics of cellular automata, Rev. Mod. Phys., 55, 601 (1983) · Zbl 1174.82319
[86] Wolfram, S., Universality and complexity in cellular automata, Physica D, 10, 1-35 (1984) · Zbl 0562.68040
[87] Wolfram, S., Computation theory of cellular automata, Commun. Math. Phys., 96, 15-57 (1984) · Zbl 0587.68050
[88] Wolfram, S., Cellular automaton fluids 1: basic theory, J. Stat. Phys., 45, 471-526 (1986) · Zbl 0629.76002
[89] Wolfram, S., Theory and Applications of Cellular Automaton (1986), World Scientific: World Scientific Singapore
[90] Yaku, T., Inverse and injectivity of parallel relations induced by cellular automata, (Proc. Am. Math. Soc., 58 (1976)), 216-220 · Zbl 0341.94032
[91] (Calculating Space. Calculating Space, Tech. Transl. AZT-70-164-GEMIT (1970)), translated as · Zbl 0203.48901
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.