Intrinsic universality and the computational power of self-assembly

Area of Science:

• * Nanotechnology and Materials Science
• * Theoretical Computer Science
• * Computational Biology

Background:

• * Molecular self-assembly is a fundamental process for creating complex structures from simple components.
• * Designing molecules for predictable self-assembly into desired objects is a key engineering challenge.
• * Algorithmic self-assembly models provide theoretical frameworks to understand bottom-up fabrication capabilities and limitations.

Purpose of the Study:

• * To survey and classify the computational and expressive powers of different algorithmic self-assembly models using simulation.
• * To investigate the existence and properties of universal tile sets within these models.
• * To explore the hierarchical structures of simulation power in restricted or extended models.

Main Methods:

• * Analyzing simulation relationships between various abstract Tile Assembly Models (TAMs).
• * Investigating the properties of specific tile sets, including intrinsically universal and polygonal tiles.
• * Comparing the simulation capabilities of cooperative, non-cooperative, and two-handed TAMs.

Main Results:

• * A single intrinsically universal tile set exists that can simulate any instance of Winfree's abstract TAM.
• * This universal tile set demonstrates a direct capture of geometry and dynamics, exceeding Turing universality.
• * The non-cooperative model is proven weaker than the full TAM due to the absence of such a universal tile set.
• * The two-handed model exhibits infinite hierarchies of increasing simulation power.
• * A single rotatable, flipable polygonal tile can simulate any tile assembly system.
• * A tile capable of aperiodic plane tiling (with gaps) was identified.

Conclusions:

• * Simulation serves as a powerful tool for developing a computational complexity theory for self-assembly.
• * The study reveals significant differences in expressive and computational power across various self-assembly models.
• * Future research directions include further exploration of complexity classes and the design of novel self-assembling systems.