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

Attribution - NonCommercial - NoDerivatives

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⟩
253 View
406 Download

Altmetric

Share

Gmail Facebook X LinkedIn More