HackerPapers

arXiv:1208.2771cs.FL

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

Katsunobu Imai, Takahiro Hatsuda, Victor Poupet, Kota Sato

HN submission. Found in a submission link or body. Submitters do not count as commenters in the main ranking; a submission is not an endorsement.

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 on this aperiodic tiling.

arXiv comments
In Proceedings AUTOMATA&JAC 2012, arXiv:1208.2498
Journal reference
EPTCS 90, 2012, pp. 267-278
DOI
doi:10.4204/EPTCS.90.21
Subjects
cs.FLFormal Languages and Automata Theory cs.CCComputational Complexity nlin.CGCellular Automata and Lattice Gases

On Hacker News

No comments linking this paper were found in the collected sources. Found in 1 HN submission from Aug 2012 to Aug 2012. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments0 threads

No comments linking this paper were found in the collected sources. Open submission discussions.

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.