Intrinsic Universality and the Computational Power of Self-Assembly
Our story is set in the world of algorithmic self-assembly, where small unit-sized tiles stick together to form large complicated structures in what is best described as an asynchronous and distributed computational process. We regale the forging of a powerful tool, simulation. We tell of its wielding by brave adventurers to classify and separate the computational and expressive power of self-assembly models.
Our journey begins with the result that there is a single intrinsically universal tile set, that with proper initialization and scaling, simulates any tile assembly system. This intrinsically universal tile set exhibits something stronger than Turing universality: it directly simulates the geometry and dynamics of any simulated system. From there we find that there is no such tile set in the noncooperative, or temperature 1, model, proving it weaker than the full tile assembly model. In the two-handed or hierarchical model, where large assemblies can bind together in one step, we encounter an infinite set, of infinite hierarchies, with strictly increasing simulation power. Towards the end of our adventure, we find one tile to rule them all: a single rotatable, flipable, polygonal tile that can simulate any tile assembly system. It seems this could be the beginning of a much longer journey, so directions for future work are suggested.
Damien Woods is a Senior Postdoctoral Scholar in Computer Science, and The Molecular Programming Fellow, at Caltech, USA. His areas of research include the theory and practice of molecular self-assembly and self-replication, molecular robotics, simulation and intrinsic universality in self-assembly, and the computational complexity of cellular automata, small universal Turing machines, Boolean circuits and optical computers. He uses the theory of computation to understand biological, chemical and physical mechanisms.
Recent work includes developing simulation and intrinsic universality as tools to characterise the computational power of molecular self-assembly systems, and developing a theory of active robotic self-assembly that includes non-local molecular motor movement. Woods has taken to the wet-lab and works on the origin of life with Winfree and Yurke. His PhD work at NUI Maynooth, Ireland (2005), explored the computational power of optical computers and, with Naughton, he defined and analyzed physically-inspired optical computing resources. With Murphy he worked on the complexity of Boolean circuits and membranes systems, answering an open question. With Neary he worked on simple models of computation, answering open questions about the time efficiency of small universal Turing machines and the cellular automaton Rule 110, while finding some of the smallest and fastest programs capable of general-purpose computation.