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.
Type de document :
Article dans une revue
Fundamenta Informaticae, Polskie Towarzystwo Matematyczne, 2013, Cellular Automata and Models of Computation, 126 (2-3), pp.247-261. 〈10.3233/FI-2013-880〉
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01476788
Contributeur : Victor Poupet <>
Soumis le : samedi 25 février 2017 - 18:27:05
Dernière modification le : lundi 16 juillet 2018 - 16:24:02
Document(s) archivé(s) le : vendredi 26 mai 2017 - 12:13:57

Fichier

automata2012.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité - Pas d'utilisation commerciale - Pas de modification 4.0 International License

Identifiants

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〉

Partager

Métriques

Consultations de la notice

249

Téléchargements de fichiers

533