A 6-state Universal Semi-totalistic Cellular Automaton on Kite and Dart Penrose Tilings - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Fundamenta Informaticae Year : 2013

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

Katsunobu Imai
  • Function : Author
  • PersonId : 853094
Takahiro Hatsuda
  • Function : Author
  • PersonId : 1002572
Victor Poupet
Kota Sato
  • Function : Author
  • PersonId : 1002573

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.
Fichier principal
Vignette du fichier
automata2012.pdf (2.7 Mo) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-01476788 , version 1 (25-02-2017)

Licence

Identifiers

Cite

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

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More