×

Reversible cellular automata with memory: two-dimensional patterns from a single site seed. (English) Zbl 1008.37008

Summary: Standard cellular automata (CA) are ahistoric (memoryless), i.e., the new state of a cell depends on its neighborhood configuration only at the preceding time step. Historic memory of all past iterations can be incorporated into CA by featuring each cell by a weighted mean of all its past states. In this paper, a new kind of reversible CA, which incorporates memory, is introduced in a two-dimensional scenario.

MSC:

37B15 Dynamical aspects of cellular automata
68Q80 Cellular automata (computational aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A. Ilachinski, Cellular Automata. A Discrete Universe, World Scientific, Singapore, 2001.; A. Ilachinski, Cellular Automata. A Discrete Universe, World Scientific, Singapore, 2001. · Zbl 1031.68081
[2] S. Wolfram, A New Kind of Science, Wolfram Media, 2002.; S. Wolfram, A New Kind of Science, Wolfram Media, 2002. · Zbl 1022.68084
[3] Wolfram, S., Universality and complexity in cellular automata, Physica D, 10, 1-35 (1984) · Zbl 0562.68040
[4] Alonso-Sanz, R.; Martin, M., Two-dimensional cellular automata with memory: patterns from a single site seed, Int. J. Mod. Phys. C, 13, 1, 49-65 (2002) · Zbl 1083.68577
[5] Alonso-Sanz, R.; Martin, M., One-dimensional cellular automata with memory: patterns from a single site seed, Int. J. Bifurc. Chaos, 12, 1, 205-226 (2002) · Zbl 1044.37007
[6] Alonso-Sanz, R.; Martin, M. C.; Martin, M., Historic life, Int. J. Bifurc. Chaos, 11, 6, 1665-1682 (2001)
[7] Alonso-Sanz, R., The historic prisoner’s dilemma, Int. J. Bifurc. Chaos, 9, 6, 1197-1210 (1999) · Zbl 1089.91500
[8] Alonso-Sanz, R.; Martin, M. C.; Martin, M., Discounting in the historic prisoner’s dilemma, Int. J. Bifurc. Chaos, 10, 1, 87-102 (2000) · Zbl 1090.91502
[9] Alonso-Sanz, R.; Martin, M. C.; Martin, M., The historic strategist, Int. J. Bifurc. Chaos, 11, 4, 943-966 (2001)
[10] Alonso-Sanz, R.; Martin, M. C.; Martin, M., The historic-stochastic strategist, Int. J. Bifurc. Chaos, 11, 7, 2037-2050 (2001)
[11] Alonso-Sanz, R.; Martin, M. C.; Martin, M., The effect of memory in the continuous-valued prisoner’s dilemma, Int. J. Bifurc. Chaos, 11, 8, 2061-2084 (2001)
[12] R. Feymann, in: T. Hey, R.W. Allen (Eds.), Feymann Lectures on Computation, Perseus Publications, 1996.; R. Feymann, in: T. Hey, R.W. Allen (Eds.), Feymann Lectures on Computation, Perseus Publications, 1996.
[13] Toffoli, T., Computation and construction universality of reversible cellular automata, J. Comput. Syst. Sci., 15, 213-231 (1977) · Zbl 0364.94085
[14] Fredkin, E., Digital mechanics. An informal process based on reversible universal cellular automata, Physica D, 45, 254-270 (1990) · Zbl 0719.68044
[15] Margolus, N., Physics-like models of computation, Physica D, 10, 81-95 (1984) · Zbl 0563.68051
[16] T. Toffoli, N. Margolus, Cellular Automata Machines, MIT Press, Cambridge, MA, 1987.; T. Toffoli, N. Margolus, Cellular Automata Machines, MIT Press, Cambridge, MA, 1987. · Zbl 0655.68055
[17] Toffoli, T.; Margolus, N., Invertible cellular automata: a review, Physica D, 45, 229-253 (1990) · Zbl 0729.68066
[18] Vichniac, G., Simulating physics with cellular automata, Physica D, 10, 96-115 (1984) · Zbl 0563.68053
[19] ’t Hooft, G., Equivalence relations between deterministic and quantum mechanical systems, J. Statist. Phys., 53, 1-2, 323-344 (1988)
[20] Svozil, K., Are quantum fields cellular automata?, Phys. Lett. A, 119, 41, 153-156 (1986)
[21] A. Wuensche, M. Lesser, The Global Dynamics of Cellular Automata. Santa Fe Institute Studies in the Sciences of Complexity, vol. 1, Addison-Wesley, Reading, MA, 1992.; A. Wuensche, M. Lesser, The Global Dynamics of Cellular Automata. Santa Fe Institute Studies in the Sciences of Complexity, vol. 1, Addison-Wesley, Reading, MA, 1992. · Zbl 0814.68090
[22] Cattaneo, G.; Floccini, P.; Mauri, G.; Vogliotti, C. Q.; Santoro, N., Cellular automata in fuzzy backgrounds, Physica D, 105, 105-120 (1997) · Zbl 0938.68735
[23] Wolfram, S., Statistical mechanics of cellular automata, Rev. Mod. Phys., 55, 601-644 (1983) · Zbl 1174.82319
[24] Vichniac, G., Boolean derivatives of cellular automata, Physica D, 45, 63-74 (1990) · Zbl 0715.68065
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.