Simulation and intrinsic universality among reversible cellular automata, the partition cellular automata leverage. (English) Zbl 1434.68312
Adamatzky, Andrew (ed.), Reversibility and universality. Essays presented to Kenichi Morita on the occasion of his 70th birthday. Cham: Springer. Emerg. Complex. Comput. 30, 61-93 (2018).
Summary: This chapter presents the use of Partitioned Cellular Automata – introduced by Morita and colleagues – as the tool to tackle simulation and intrinsic universality in the context of Reversible Cellular Automata. Cellular automata (CA) are mappings over infinite lattices such that all cells are updated synchronously according to the states around each one and a common local function. A CA is reversible if its global function is invertible and its inverse can also be expressed as a CA. Kari proved in 1989 that invertibility is not decidable (for CA of dimension at least 2) and is thus hard to manipulate. Partitioned Cellular Automata (PCA) were introduced as an easy way to handle reversibility by partitioning the states of cells according to the neighborhood. Another approach by Margolus led to the definition of Block CA (BCA) where blocks of cells are updated independently. Both models allow easy check and design for reversibility. After proving that CA, BCA and PCA can simulate each other, it is proven that the reversible sub-classes can also simulate each other contradicting the intuition based on decidability results. In particular, it is proven that any \(d\)-dimensional reversible CA (\(d\)-R-CA) can be expressed as a BCA with \(d+1\) partitions. This proves a 1990 conjecture by T. Toffoli and N. H. Margolus [Physica D 45, No. 1–3, 229–253 (1990; Zbl 0729.68066)] improved and partially proved by J. Kari in [Math. Syst. Theory 29, No. 1, 47–61 (1996; Zbl 0840.68081)]. With the use of signals and reversible programming, a 1-R-CA that is intrinsically universal – able to simulate any 1-R-CA – is built. Finally, with a peculiar definition of simulation, it is proven that any CA (reversible or not) can be simulated by a reversible one. All these results extend to any dimension.
For the entire collection see [Zbl 1396.68007].
For the entire collection see [Zbl 1396.68007].
MSC:
| 68Q80 | Cellular automata (computational aspects) |
References:
| [1] | Albert, J., Čulik, K. II.: A simple universal cellular automaton and its one-way and totalistic version. Complex Syst. 1, 1-16 (1987) · Zbl 0655.68065 |
| [2] | Amoroso, S., Patt, Y.N.: Decision procedure for surjectivity and injectivity of parallel maps for tessellation structure. J. Comput. Syst. Sci. 6, 448-464 (1972) · Zbl 0263.94019 · doi:10.1016/S0022-0000(72)80013-8 |
| [3] | Bennett, C.H.: Logical reversibility of computation. IBM J. Res. Dev. 6, 525-532 (1973) · Zbl 0267.68024 · doi:10.1147/rd.176.0525 |
| [4] | Bennett, C.H.: Notes on the history of reversible computation. IBM J. Res. Dev. 32(1), 16-23 (1988) · doi:10.1147/rd.321.0016 |
| [5] | Burks, A.W.: Essays on Cellular Automata. University of Illinois Press, Champaign (1970) · Zbl 0228.94013 |
| [6] | Durand-Lose, J.: Reversible cellular automaton able to simulate any other reversible one using partitioning automata. In: LATIN 1995. LNCS, vol. 911, pp. 230-244. Springer (1995). https://doi.org/10.1007/3-540-59175-3_92 · Zbl 1495.68147 · doi:10.1007/3-540-59175-3_92 |
| [7] | Durand-Lose, J.: Automates Cellulaires, Automates à Partitions et Tas de Sable. Thèse de doctorat, LaBRI (1996). http://www.univ-orleans.fr/lifo/Members/Jerome.Durand-Lose/Recherche/These/index.html. In French |
| [8] | Durand-Lose, J.: Intrinsic universality of a \(1\)-dimensional reversible cellular automaton. In: STACS 1997. LNCS, Vol. 1200, pp. 439-450. Springer (1997). https://doi.org/10.1007/BFb0023479 · Zbl 1498.68179 · doi:10.1007/BFb0023479 |
| [9] | Durand-Lose, J.: About the universality of the billiard ball model. In: Margenstern, M. (ed.) Universal Machines and Computations (UMC ’98), vol. 2, pp. 118-133. Université de Metz (1998) |
| [10] | Durand-Lose, J.: Reversible space-time simulation of cellular automata. Theoret. Comput. Sci. 246(1-2), 117-129 (2000). https://doi.org/10.1016/S0304-3975(99)00075-4 · Zbl 0971.68110 · doi:10.1016/S0304-3975(99)00075-4 |
| [11] | Durand-Lose, J.: Representing reversible cellular automata with reversible block cellular automata. In: Cori, R., Mazoyer, J., Morvan, M., Mosseri, R. (eds.) Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG ’01, vol. AA of Discrete Mathematics and Theoretical Computer Science Proceedings, pp. 145-154 (2001a). http://dmtcs.loria.fr/volumes/abstracts/dmAA0110.abs.html · Zbl 1052.68090 |
| [12] | Durand-Lose, J.: Back to the universality of the Billiard ball model. Mult. Valued Logic 6(5-6), 423-437 (2001b) · Zbl 1007.68124 |
| [13] | Hedlund, G.A.: Endomorphism and automorphism of the shift dynamical system. Math. Syst. Theory 3, 320-375 (1969) · Zbl 0182.56901 · doi:10.1007/BF01691062 |
| [14] | Kari, J.: Reversibility of 2D cellular automata is undecidable. Phys. D 45, 379-385 (1990) · Zbl 0729.68058 · doi:10.1016/0167-2789(90)90195-U |
| [15] | Kari, J.: Reversibility and surjectivity problems of cellular automata. J. Comput. Syst. Sci. 48(1), 149-182 (1994) · Zbl 0802.68090 · doi:10.1016/S0022-0000(05)80025-X |
| [16] | Kari, J.: Representation of reversible cellular automata with block permutations. Math. Syst. Theory 29, 47-61 (1996) · Zbl 0840.68081 · doi:10.1007/BF01201813 |
| [17] | Kari, J.: On the circuit depth of structurally reversible cellular automata. Fund. Inf. 38(1-2), 93-107 (1999) · Zbl 0935.68070 |
| [18] | Kari, J.: Theory of cellular automata: a survey. Theoret. Comput. Sci. 334, 3-33 (2005) · Zbl 1080.68070 · doi:10.1016/j.tcs.2004.11.021 |
| [19] | Lecerf, Y.: Machines de Turing réversibles. Récursive insolubilité en \(n\in \mathbb{N}\) de l’équation \(u = \theta^nu\), où \(\theta\) est un isomorphisme de codes. Comptes rendus des séances de l’académie des sciences 257:2597-2600 (1963) · Zbl 0192.06901 |
| [20] | Margolus, N.: Physics-like models of computation. Phys. D 10(1-2), 81-95 (1984) · Zbl 0563.68051 · doi:10.1016/0167-2789(84)90252-5 |
| [21] | Margolus, N.: Physics and Computation. Ph.D. thesis, MIT (1988) · Zbl 0563.68051 |
| [22] | Martin, B.: A universal cellular automaton in quasi-linear time and its S-n-m form. Theoret. Comput. Sci. 123, 199-237 (1994) · Zbl 0801.68116 · doi:10.1016/0304-3975(92)00076-4 |
| [23] | Moore, E.F.: Machine models of self-reproduction. Proc. Symp. Appl. Math. 14, 17-33 (1962) · Zbl 0126.32408 · doi:10.1090/psapm/014/9961 |
| [24] | Morita, K.: Any irreversible cellular automaton can be simulated by a reversible one having the same dimension. Tech. Rep. IEICE, Comp. 92-45(1992-10), 55-64 (1992) |
| [25] | Morita, K.: Computation-universality of one-dimensional one-way reversible cellular automata. Inform. Process. Lett. 42, 325-329 (1992b) · Zbl 0779.68064 · doi:10.1016/0020-0190(92)90231-J |
| [26] | Morita, K.: Reversible simulation of one-dimensional irreversible cellular automata. Theoret. Comput. Sci. 148, 157-163 (1995) · Zbl 0873.68141 · doi:10.1016/0304-3975(95)00038-X |
| [27] | Morita, K.: Reversible computing and cellular automata - a survey. Theoret. Comput. Sci. 395(1), 101-131 (2008). https://doi.org/10.1016/j.tcs.2008.01.041 · Zbl 1145.68036 · doi:101-131&publication_year=2008&doi=10.1016/j.tcs.2008.01.041 |
| [28] | Morita, K., Harao, M.: Computation universality of one-dimensional reversible (injective) cellular automata. Trans. IEICE, E 72(6), 758-762 (1989) |
| [29] | Myhill, J.R.: The converse of Moore’s garden-of-eden theorem. Proc. Am. Math. Soc. 14, 685-686 (1963) · Zbl 0126.32501 |
| [30] | Ollinger, N.: Two-states bilinear intrinsically universal cellular automata. In: FCT ’01. LNCS, vol. 2138, 369-399. Springer, Berlin · Zbl 0999.68526 |
| [31] | Ollinger, N.: Universalities in cellular automata. In: Rozenberg, G., Bäck, T., Kok, J.N. (eds.) Handbook of Natural Computing, pp. 189-229. Springer (2012). https://doi.org/10.1007/978-3-540-92910-9 · Zbl 1248.68001 · doi:10.1007/978-3-540-92910-9 |
| [32] | Richardson, D.: Tessellations with local transformations. J. Comput. Syst. Sci. 6(5), 373-388 (1972) · Zbl 0246.94037 |
| [33] | Sarkar, P.: A brief history of cellular automata. ACM Comput. Surv. 32(1), 80-107 (2000) · doi:10.1145/349194.349202 |
| [34] | Toffoli, T.: Computation and construction universality of reversible cellular automata. J. Comput. Syst. Sci. 15, 213-231 (1977) · Zbl 0364.94085 · doi:10.1016/S0022-0000(77)80007-X |
| [35] | Toffoli, T., Margolus, N.: Cellular Automata Machine - A New Environment for Modeling. MIT press, Cambridge (1987) · Zbl 0655.68055 |
| [36] | Toffoli, T., Margolus, N.: Invertible cellular automata: a review. Phys. D 45, 229-253 (1990) · Zbl 0729.68066 · doi:10.1016/0167-2789(90)90185-R |
| [37] | Wolfram, S. |
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.
