The Two-Handed Tile Assembly Model Is Not Intrinsically Universal

DOI10.1007/978-3-642-39206-1_34MaRDI QIDQ5326578zbMATH OpenOpenAlexFDO

Authors Erik D. Demaine, Trent A. Rogers, Robert T. Schweller, Scott M. Summers, Damien Woods, Matthew J. Patitz

Publication date 6 August 2013

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://resolver.caltech.edu/CaltechAUTHORS:20160218-140524803

Mathematics Subject Classification ID

Recommendations

• The two-handed tile assembly model is not intrinsically universal
• The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation
• Nearly constant tile complexity for any shape in two-handed tile assembly
• One tile to rule them all: simulating any tile assembly system with a single universal tile
• Directed non-cooperative tile assembly is decidable
• Complexities for high-temperature two-handed tile self-assembly
• Solving NP-complete problems in the tile assembly model
• The Impacts of Dimensionality, Diffusion, and Directedness on Intrinsic Universality in the abstract Tile Assembly Model

Cited in

(22)

• The power of duples (in self-assembly): it's not so hip to be square
• Optimal staged self-assembly of general shapes
• Nearly constant tile complexity for any shape in two-handed tile assembly
• Producibility in hierarchical self-assembly
• Parallel computation using active self-assembly
• Fractal dimension of assemblies in the abstract tile assembly model
• On the complexity of two-dimensional signed majority cellular automata
• An introduction to tile-based self-assembly and a survey of recent results
• The two-handed tile assembly model is not intrinsically universal
• Unraveling simplicity in elementary cellular automata
• Resiliency to multiple nucleation in temperature-1 self-assembly
• Replication of Arbitrary Hole-Free Shapes via Self-assembly with Signal-Passing Tiles
• The Simulation Powers and Limitations of Hierarchical Self-Assembly Systems
• Two hands are better than one (up to constant factors): self-assembly in the 2HAM vs. aTAM
• Intrinsic universality in self-assembly
• A brief tour of theoretical tile self-assembly
• Strict self-assembly of fractals using multiple hands
• The simulation powers and limitations of higher temperature hierarchical self-assembly systems
• The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation
• Parallel Computation Using Active Self-assembly
• Parallelism and time in hierarchical self-assembly
• The need for seed (in the abstract Tile Assembly Model)

This page was built for publication: The Two-Handed Tile Assembly Model Is Not Intrinsically Universal

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5326578)