Skip to Main content Skip to Navigation
Journal articles

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

Katsunobu Imai 1 Takahiro Hatsuda 1 Victor Poupet 2 Kota Sato 1
2 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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 and any Turing machine on this aperiodic tiling.
Document type :
Journal articles
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01476788
Contributor : Victor Poupet <>
Submitted on : Saturday, February 25, 2017 - 6:27:05 PM
Last modification on : Thursday, June 6, 2019 - 3:40:20 PM
Long-term archiving on: : Friday, May 26, 2017 - 12:13:57 PM

File

automata2012.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution - NonCommercial - NoDerivatives 4.0 International License

Identifiers

Collections

Citation

Katsunobu Imai, Takahiro Hatsuda, Victor Poupet, Kota Sato. A 6-state Universal Semi-totalistic Cellular Automaton on Kite and Dart Penrose Tilings. Fundamenta Informaticae, Polskie Towarzystwo Matematyczne, 2013, Cellular Automata and Models of Computation, 126 (2-3), pp.247-261. ⟨10.3233/FI-2013-880⟩. ⟨lirmm-01476788⟩

Share

Metrics

Record views

506

Files downloads

736