A 6-state Universal Semi-totalistic Cellular Automaton on Kite and Dart Penrose Tilings

• Autorzy: Imai K. , Hatsuda T. , Poupet V. , Sato K.
• Języki publikacji: EN

Abstrakty

EN

In this paper we investigate certain properties of semi-totalistic cellular automata (CA) on the well known quasi-periodic kite and dart two dimensional tiling of the plane presented by Roger Penrose. We show that, despite the irregularity of the underlying grid, it is possible to devise a 6-state semi-totalistic CA capable of simulating any boolean circuit and any Turing machine on this aperiodic tiling.

Słowa kluczowe

EN

cellular automata; Penrose tiling; universality

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 126, nr 2-3
• Strony: 247--261
• Opis fizyczny: Bibliogr. 22 poz.

Twórcy

autor

Imai K.

• Graduate School of Engineering, Hiroshima University, Higashi-Hiroshima, 739-8527, Japan

autor

Hatsuda T.

• Graduate School of Engineering, Hiroshima University, Higashi-Hiroshima, 739-8527, Japan

autor

Poupet V.

• Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier (LIRMM), Université Montpellier 2, CNRS, 161 rue Ada, 34392 Montpellier, France

autor

Sato K.

• Graduate School of Engineering, Hiroshima University, Higashi-Hiroshima, 739-8527, Japan

Bibliografia

• [1] Chidyagwai, P., Reiter, CA.: A local cellular model for growth on quasicrystals. Chaos, Solutions and Fractals 24 (2005) 803-812.
• [2] Dewdney, A.K.: Computer recreations: a cellular universe of debris, droplets, defects and demons. Scientific American 261, August (1989) 102-105.
• [3] Dewdney, A.K.: Computer recreations: The cellular automata programs that create Wireworld, Rugworld and other diversions, Scientific American 262, January (1990) 146-149.
• [4] Fisch, R.: Cyclic cellular automata and related processes. Physica D 45 (1990) 19-25.
• [5] Gardner, M.: Mathematical Games - The fantastic combinations of John Conway’s new solitaire game “life” (1970) 223. pp. 120123.
• [6] Gardner, M.: Extraordinary nonperiodic tiling that enriches the theory of tiles. Mathematical Games, Scientific American, January, 1977, p. 110-121.
• [7] Goucher, A. P.: Gliders in Cellular Automata on Penrose Tilings. Journal of Cellular Automata (to Appear).
• [8] Griffeath, D.: A CA run on Penrose Tiles, http://psoup.math.wisc.edu/archive/recipe39.html.
• [9] Imai, K., Hatsuda, T., Poupet, V. and Sato, K.: A Universal Semi-totalistic Cellular Automaton on Kite and Dart Penrose Tilings. Proc 18th international workshop on Cellular Automata and Discrete Complex Systems and 3rd international symposium Journes Automates Cellulaires (AUTOMATA&JAC 2012), Electronic Proceedings in Theoretical Computer Science 90 (2012) 267-278.
• [10] Imai, K., Iwamoto, C., and Morita, K.: A Five-State von Neumann Neighbor Universal Hyperbolic Cellular Automaton. Journal of Cellular Automata 1 4 (2006) 275-297.
• [11] Lee, J., Peper, F., Adachi, S., and Morita, K.: An asynchronous cellular automaton implementing 2-state 2-input 2-output reversed-twin reversible elements. In Proc. ACRI2008, LNCS 5191 (2008) 67-76.
• [12] McClure, M.: A Stochastic Cellular Automaton for Three-Coloring Penrose Tiles Computers & Graphics 26 3 (2002) 519-524.
• [13] Morita, K.: Constructing a reversible turing machine by a rotary element, a reversible logic element with memory. In Hiroshima University Institutional Repository http://ir.lib.hiroshima-u.ac.jp/00029224.
• [14] Morita, K., Ogiro, T., and Alhazov, A.: Non-degenerate 2-state reversible logic elements with three or more symbols are all universal. Multiple-Valued Logic and Soft Computing 18 1 (2012) 37-54.
• [15] Mukai, Y., Morita, K.: Universality of 2-symbol reversible logic elements with memory. Resume for LA Symposium Summer (2011), S16 1-15 (in Japanese).
• [16] Owens, N., Stepney, S.: Investigation of the Game of Life cellular automata rules on Penrose tilings: lifetime, ash and oscillator statistics. Journal of Cellular Automata 5 3 (2010) 207-225.
• [17] Owens, N., Stepney, S.: The Game of Life rules on Penrose tilings: still life and oscillators. In: A. Adamatzky (Ed.) Game of Life Cellular Automata, Springer-Verlag London (2010) 331-378.
• [18] Reiter, CA.: Medley of spirals from cyclic cellular automata. Computers & Graphics 34 (2010) 72-76.
• [19] Tsukamoto, Y., Miyazaki, Y., and Tsuiki, H.: Gliders flying on Penrose tilings. Resume for LA Symposium Winter (2013), S22 1-4 (in Japanese).
• [20] Weeks, E.: Cellular automata on quasicrystals, http://www.physics.emory.edu/~weeks/pics/qvote.html.
• [21] Wojtowicz, M.: Cellular Automata rules lexicon, http://www.mirekw.com/ca/ca_rules.html.
• [22] Wolfram, S.: in New Kind of Science (2002) Wolfram Media, 929-929.