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 capa-ble of asymptotically optimal assembly of arbitrary shapes and, via information-theoretic arguments, increasingly complex shapes necessar-ily require increasing numbers of distinct types of tiles. We explore the possibility of complex and efficient assembly using sys-tems 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 lim-ited number of steps given an appropriate seed assembly, and that any longer-running simulation must induce infinite assembly