One Tile to Rule Them All: Simulating Any Tile Assembly System with a Single Universal Tile
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.
Additional Information
© 2014 Springer-Verlag Berlin Heidelberg. Research of Matthew J. Patitz supported in part by NSF grant CCF-1117672. Research of Robert Schweller supported in part by NSF grant CCF-1117672. Research of Andrew Winslow supported in part by NSF grant CDI-0941538. Research of Damien Woods Supported by NSF grants 0832824 & 1317694 (the Molecular Programming Project), CCF-1219274, and CCF-1162589. This work was initiated at the 27th Bellairs Winter Workshop on Computational Geometry held on February 11-17, 2012 in Holetown, Barbados. We thank the other participants of that workshop for a fruitful and collaborative environment. In particular, we thank Brad Ballinger and Anna Lubiw for important discussions regarding Lemma 3. In addition, we thank Jarkko Kari for interesting and fruitful discussions on aperiodic tilings of the plane with few tile types.Attached Files
Submitted - 1212.4756v1.pdf
Files
Name | Size | Download all |
---|---|---|
md5:3f2f4e66e4f6a1ce2c41115bdf914014
|
807.4 kB | Preview Download |
Additional details
- Eprint ID
- 57453
- Resolver ID
- CaltechAUTHORS:20150512-112419135
- CCF-1117672
- NSF
- CCF-1117672
- NSF
- CDI-0941538
- NSF
- CCF-0832824
- NSF
- CCF-1317694
- NSF
- CCF-1219274
- NSF
- CCF-1162589
- NSF
- Created
-
2015-05-12Created from EPrint's datestamp field
- Updated
-
2021-11-10Created from EPrint's last_modified field
- Series Name
- Lecture Notes in Computer Science
- Series Volume or Issue Number
- 8572