Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published October 2012 | public
Book Section - Chapter

The tile assembly model is intrinsically universal


We prove that the abstract Tile Assembly Model (aTAM) of nanoscale self-assembly is intrinsically universal. This means that there is a single tile assembly system U that, with proper initialization, simulates any tile assembly system T. The simulation is "intrinsic" in the sense that the self-assembly process carried out by U is exactly that carried out by T, with each tile of T represented by an m × m "super tile" of U. Our construction works for the full aTAM at any temperature, and it faithfully simulates the deterministic or nondeterministic behavior of each T. Our construction succeeds by solving an analog of the cell differentiation problem in developmental biology: Each super tile of U, starting with those in the seed assembly, carries the "genome" of the simulated system T. At each location of a potential super tile in the self-assembly of U, a decision is made whether and how to express this genome, i.e., whether to generate a super tile and, if so, which tile of T it will represent. This decision must be achieved using asynchronous communication under incomplete information, but it achieves the correct global outcome(s).

Additional Information

© 2012 IEEE. Date of Conference: 20-23 Oct. 2012. Doty was supported by a Computing Innovation Fellowship under NSF grant 1019343 and NSF grants CCF-1219274 and CCF-1162589. Lutz was supported by NSF grants 0652569 and 1143830. Part of this work was done during a sabbatical at Caltech and the Isaac Newton Institute for Mathematical Sciences at the University of Cambridge. Patitz was supported in part by NSF grant CCF-1117672. Schweller was supported in part by NSF grant CCF-1117672. Woods was supported by NSF grant 0832824, the Molecular Programming Project, and NSF grants CCF-1219274 and CCF-1162589. We would like to thank Matthew Cook for pointing out a simplification to our construction, and David Soloveichik for stimulating conversations.

Additional details

August 19, 2023
January 13, 2024