Paper by Erik D. Demaine
- Reference:
- Erik D. Demaine, Matthew J. Patitz, Trent A. Rogers, Robert T. Schweller, Scott M. Summers, and Damien Woods, “The two-handed tile assembly model is not intrinsically universal”, in Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP 2013), Riga, Latvia, July 8–12, 2013, pages 400–412.
- Abstract:
-
In this paper, we study the intrinsic universality of the well-studied
Two-Handed Tile Assembly Model (2HAM), in which two “supertile”
assemblies, each consisting of one or more unit-square tiles, can fuse
together (self-assemble) whenever their total attachment strength is at least
the global temperature τ. Our main result is that for all
τ′ < τ, each temperature-τ′ 2HAM tile
system cannot simulate at least one temperature-τ 2HAM tile system. This
impossibility result proves that the 2HAM is not intrinsically universal, in
stark contrast to the simpler abstract Tile Assembly Model which was shown to
be intrinsically universal (The tile assembly model is intrinsically
universal, FOCS 2012). On the positive side, we prove that, for every
fixed temperature τ ≥ 2, temperature-τ 2HAM tile
systems are intrinsically universal: for each τ there is a single
universal 2HAM tile set U that, when appropriately initialized, is
capable of simulating the behavior of any temperature τ 2HAM tile
system. As a corollary of these results we find an infinite set of infinite
hierarchies of 2HAM systems with strictly increasing power within each
hierarchy. Finally, we show how to construct, for each τ, a
temperature-τ 2HAM system that simultaneously simulates all
temperature-τ 2HAM systems.
- Length:
- The paper is 12 pages.
- Availability:
- The paper is available in PDF (343k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- 2HAMIU_Algorithmica (The Two-Handed Tile Assembly Model is not Intrinsically Universal)
See also other papers by Erik Demaine.
These pages are generated automagically from a
BibTeX file.
Last updated July 23, 2024 by
Erik Demaine.