Intrinsic Universality of the aTAM

From self-assembly wiki
Revision as of 11:16, 12 July 2013 by \('"2\)'"7
(\(1) \)2 | \(3 (\)4) | \(5 (\)6)
Jump to navigation Jump to search

An intrinsically universal model is one which contains some system U, such that for any arbitrary system T within that model, U can be given a starting condition based on T such that U will then completely simulate the behavior of T. That is, U will mimic all behaviors of T, but at a re-scaling in which each n × n block within U, for some \(n \in \mathbb{N}\), can be mapped to a single element of T. Cellular automata and Turing machines are both examples of models which are intrinsically universal. While an aTAM system can be designed to simulate an arbitrary Turing machine, which could computationally simulate an arbitrary aTAM system, another interesting question was whether or not the aTAM is intrinsically universal, or: Is there a single tile set which can be used to simulate the behavior of any arbitrary aTAM system? Essentially, if the tiles of this "universal" tile set could be arranged to form a seed structure such that that structure contains an encoding of some other aTAM system, say \(\mathcal{T}\), could additional copies of tiles from the universal tile set attach to grow into an assembly which simulates the system \(\mathcal{T}\)? Of course, the simulation would be a scaled up version of the original system, but it must be the case that every behavior that \(\mathcal{T}\) is capable of, the simulating system is also capable of. Preliminary work by Doty, Lutz, Patitz, Summers, and Woods in [1] showed that for a constrained set of aTAM systems, namely those in which all tiles bind with exactly strength \(\tau\) and there are no glue mismatches between adjacent tile edges, that class is intrinsically universal. Furthermore, it was later shown by Doty, Lutz, Patitz, Schweller, Summers, and Woods in [2] that the entire, unconstrained class of aTAM systems is intrinsically universal. In fact, they demonstrated a tile set U and a method for using the definition of an arbitrary aTAM system \(\mathcal{T}\) of any temperature to form a seed structure for U so that the system with that seed, the tiles from U, and at temperature 2, can simulate \(\mathcal{T}\). Thus, a single tile set in a properly seeded system at temperature 2 can simulate the behavior of any aTAM system at any temperature.

The previous result shows a powerful symmetry to the aTAM, since there is a system within it that can behave exactly like any other system within it. In [3], Meunier, Patitz, Summers, Theyssier, Winslow, and Woods showed that the temperature 2 parameter for systems using the intrinsically universal tile set is in fact a lower bound. They showed that no aTAM tile set exists which can simulate arbitrary aTAM systems of temperature >1, while operating in a system of temperature 1, proving that the cooperative behavior provided by temperature 2 self-assembly can not be simulated at temperature 1. Further, their impossibility result extends to 3D, showing that even 3D temperature 1 aTAM systems cannot simulate 2D temperature 2 aTAM systems, which is contrasted with the facts that 3D temperature 1 systems are capable of universal computation (see The influence of temperature), and the second result of [3] shows that 3D temperature 1 systems can simulate arbitrary 2D temperature 1 systems. These results especially emphasize the fact that the power to perform universal computation does not imply the power to simulate arbitrary behaviors of algorithmic self-assembly.

References

  1. David Doty, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers, Damien Woods - Intrinsic Universality in Self-Assembly
    Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science pp. 275--286,2009
    Bibtex
    Author : David Doty, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers, Damien Woods
    Title : Intrinsic Universality in Self-Assembly
    In : Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science -
    Address :
    Date : 2009
  2. David Doty, Jack H. Lutz, Matthew J. Patitz, Robert T. Schweller, Scott M. Summers, Damien Woods - The tile assembly model is intrinsically universal
    Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science ,2012
    Bibtex
    Author : David Doty, Jack H. Lutz, Matthew J. Patitz, Robert T. Schweller, Scott M. Summers, Damien Woods
    Title : The tile assembly model is intrinsically universal
    In : Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science -
    Address :
    Date : 2012
  3. 3.0 3.1 Pierre-Etienne Meunier, Matthew J. Patitz, Scott M. Summers, Guillaume Theyssier, Andrew Winslow, Damien Woods - Intrinsic universality in tile self-assembly requires cooperation
    Technical Report, Computing Research Repository (1304.1679),2013
    http://arxiv.org/abs/1304.1679
    Bibtex
    Author : Pierre-Etienne Meunier, Matthew J. Patitz, Scott M. Summers, Guillaume Theyssier, Andrew Winslow, Damien Woods
    Title : Intrinsic universality in tile self-assembly requires cooperation
    In : Technical Report, Computing Research Repository -
    Address :
    Date : 2013