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

Katsunobu Imai
(Graduate School of Engineering, Hiroshima University, Japan) 		Takahiro Hatsuda
(Graduate School of Engineering, Hiroshima University, Japan) 		Victor Poupet
(Laboratoire d'Informatique Fondamentale de Marseille, Aix-Marseille University, France) 		Kota Sato
(Graduate School of Engineering, Hiroshima University, Japan)

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 semi-totalistic CA capable of simulating any boolean circuit on this aperiodic tiling.

In Enrico Formenti: Proceedings 18th international workshop on Cellular Automata and Discrete Complex Systems and 3rd international symposium Journées Automates Cellulaires (AUTOMATA&JAC 2012), La Marana, Corsica, September 19-21, 2012, Electronic Proceedings in Theoretical Computer Science 90, pp. 267–278.
Published: 13th August 2012.
ArXived at: https://dx.doi.org/10.4204/EPTCS.90.21 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org