Simulation of the aTAM

From self-assembly wiki
Jump to navigation Jump to search

The aTAM assumes a controlled, well-defined origin for the initiation of all assemblies, while the 2HAM allows for "spontaneous" nucleation caused by any two producible assemblies (including singleton tiles) which can bind with sufficient strength. Given this much greater level of freedom, the question of whether or not that could be constrained and forced to behave in a way similar to the aTAM was asked by Cannon, et al. in [1]. The answer was "yes", and in fact in [1] a construction was presented which, given an arbitrary aTAM system \(\mathcal{T}\), provides for a way to construct a 2HAM system \(\mathcal{S}\) which can faithfully simulate \(\mathcal{T}\); the cost is a constant scaling factor of 5. The general technique is to allow \(\mathcal{S}\) to form 5 × 5 blocks which represent the tiles in \(\mathcal{T}\) but in a very constrained way so that the blocks can only fully form and present their output glues once they've attached to a growing assembly which contains a seed block (and therefore they can't spontaneously combine away from the "seeded" assembly). This result is especially notable since, as long as the constant scaling factor is allowed, it shows that any seeded growth of the aTAM can be simulated by a system in the unseeded 2HAM, making it unnecessary for the model itself to enforce a particular starting point for growth, but instead each system can be designed to enforce a well-defined starting point of growth, if desired.

References

  1. 1.0 1.1 Sarah Cannon, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Matthew J. Patitz, Robert Schweller, Scott M. Summers, Andrew Winslow - Two Hands Are Better Than One (up to constant factors)
    Technical Report, Computing Research Repository (1201.1650),2012
    http://arxiv.org/abs/1201.1650
    Bibtex
    Author : Sarah Cannon, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Matthew J. Patitz, Robert Schweller, Scott M. Summers, Andrew Winslow
    Title : Two Hands Are Better Than One (up to constant factors)
    In : Technical Report, Computing Research Repository -
    Address :
    Date : 2012