Asynchronous signal passing for tile self-assembly: fuel efficient computation and efficient assembly of shapes

DOI10.1007/978-3-642-39074-6_17zbMATH Open1381.68088arXiv1202.5012OpenAlexW2596304771MaRDI QIDQ5300923FDOQ5300923

Authors: Jennifer E. Padilla, Raul Pena, Robert T. Schweller, Nadrian C. Seeman, Robert Sheline, Scott M. Summers, Xingsi Zhong, Matthew J. Patitz 

Publication date: 28 June 2013

Published in: Unconventional Computation and Natural Computation (Search for Journal in Brave)

Abstract: In this paper we demonstrate the power of a model of tile self-assembly based on active glues which can dynamically change state. We formulate the Signal-passing Tile Assembly Model (STAM), based on the model of Padilla, Liu, and Seeman to be asynchronous, allowing any action of turning a glue on or off, attaching a new tile, or breaking apart an assembly to happen in any order. Within this highly generalized model we provide three new solutions to tile self-assembly problems that have been addressed within the abstract Tile Assembly Model and its variants, showing that signal passing tiles allow for substantial improvement across multiple complexity metrics. Our first result utilizes a recursive assembly process to achieve tile-type efficient assembly of linear structures, using provably fewer tile types than what is possible in standard tile assembly models. Our second system of signal-passing tiles simulates any Turing machine with high fuel efficiency by using only a constant number of tiles per computation step. Our third system assembles the discrete Sierpinski triangle, demonstrating that this pattern can be strictly self-assembled within the STAM. This result is of particular interest in that it is known that this pattern cannot self-assemble within a number of well studied tile self-assembly models. Notably, all of our constructions are at temperature 1, further demonstrating that signal-passing confers the power to bypass many restrictions found in standard tile assembly models.

Full work available at URL: https://arxiv.org/abs/1202.5012

Recommendations

• Asynchronous signal passing for tile self-assembly: fuel efficient computation and efficient assembly of shapes
• Fuel Efficient Computation in Passive Self-Assembly
• Replication of Arbitrary Hole-Free Shapes via Self-assembly with Signal-Passing Tiles

Mathematics Subject Classification ID

Cited In (19)

• An introduction to tile-based self-assembly and a survey of recent results
• Dynamic simulation of 1D cellular automata in the Active aTAM
• Fuel Efficient Computation in Passive Self-Assembly
• Asynchronous signal passing for tile self-assembly: fuel efficient computation and efficient assembly of shapes
• Exponential replication of patterns in the signal tile assembly model
• The impacts of dimensionality, diffusion, and directedness on intrinsic cross-model simulation in tile-based self-assembly
• Self-assembly of 3-D structures using 2-D folding tiles
• Active tile self-assembly. I: Universality at temperature 1
• Exponential replication of patterns in the signal tile assembly model
• Hierarchical Self-Assembly of Fractals with Signal-Passing Tiles
• Simplifying the role of signals in tile self-assembly
• Resiliency to multiple nucleation in temperature-1 self-assembly
• Verification and computation in restricted tile automata
• Parallel Computation Using Active Self-assembly
• Replication of Arbitrary Hole-Free Shapes via Self-assembly with Signal-Passing Tiles
• A brief tour of theoretical tile self-assembly
• Parallel computation using active self-assembly
• Activatable tiles for compact robust programmable molecular assembly and other applications
• Signal Passing Self-Assembly Simulates Tile Automata

This page was built for publication: Asynchronous signal passing for tile self-assembly: fuel efficient computation and efficient assembly of shapes

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