Paper by Erik D. Demaine

Reference:

Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Matthew J. Patitz, Robert T. Schweller, Andrew Winslow, and Damien Woods, “One Tile to Rule Them All: Simulating Any Tile Assembly System with a Single Universal Tile”, in Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP 2014), edited by J. Esparza, P. Fraigniaud, T. Husfeldt, and E. Koutsoupias, Lecture Notes in Computer Science, volume 8572, 2014, pages 368–379.

Abstract:

In the classical model of tile self-assembly, unit square tiles translate in the plane and attach edgewise to form large crystalline structures. This model of self-assembly has been shown to be capable of asymptotically optimal assembly of arbitrary shapes and, via information-theoretic arguments, increasingly complex shapes necessarily require increasing numbers of distinct types of tiles.

We explore the possibility of complex and efficient assembly using systems consisting of a single tile. Our main result shows that any system of square tiles can be simulated using a system with a single tile that is permitted to flip and rotate. We also show that systems of single tiles restricted to translation only can simulate cellular automata for a limited number of steps given an appropriate seed assembly, and that any longer-running simulation must induce infinite assembly.

Comments:

The full paper is available as arXiv:1212.4756.

Availability:

The paper is available in PDF (286k).

See information on file formats.

[Google Scholar search]