An official website of the United States government
Self-assembly is the process by which a system of particles randomly agitate and combine, through local interactions, to form larger complex structures. In this work, we fuse a particular well-studied generalization of tile assembly (the 2-Handed or Hierarchical Tile Assembly Model) with concepts from cellular automata such as states and state transitions characterized by neighboring states. This allows for a simplification of the concepts from active self-assembly, and gives us machinery to relate the disparate existing models. We show that this model, coined Tile Automata, is invariant with respect to freezing and non-freezing transition rules via a simulation theorem showing that any non-freezing tile automata system can be simulated by a freezing one. Freezing tile automata systems restrict state transitions such that each tile may visit a state only once, i.e., a tile may undergo only a finite number of transitions. We conjecture that this result can be used to show that the Signal-passing Tile Assembly Model is also invariant to this constraint via a series of simulation results between that model and the Tile Automata model. Further, we conjecture that this model can be used to consolidate the several oft-studied models of self-assembly wherein assemblies may break apart, such as the Signal-passing Tile Assembly Model, the negative-glue 2-Handed Tile Assembly Model, and the Size-Dependent Tile Assembly Model. Lastly, the Tile Automata model may prove useful in combining results in cellular automata with self-assembly.
more »
« less
Verification and Computation in Restricted Tile Automata
Many models of self-assembly have been shown to be capable of performing computation. Tile Automata was recently introduced combining features of both Celluar Automata and the 2-Handed Model of self-assembly both capable of universal computation. In this work we study the complexity of Tile Automata utilizing features inherited from the two models mentioned above. We first present a construction for simulating Turing Machines that performs both covert and fuel efficient computation. We then explore the capabilities of limited Tile Automata systems such as 1-Dimensional systems (all assemblies are of height $$1$$) and freezing Systems (tiles may not repeat states). Using these results we provide a connection between the problem of finding the largest uniquely producible assembly using $$n$$ states and the busy beaver problem for non-freezing systems and provide a freezing system capable of uniquely assembling an assembly whose length is exponential in the number of states of the system. We finish by exploring the complexity of the Unique Assembly Verification problem in Tile Automata with different limitations such as freezing and systems without the power of detachment.
more »
« less
- Award ID(s):
- 1817602
- PAR ID:
- 10179042
- Date Published:
- Journal Name:
- Proceedings of the 26th International Conference on DNA Computing
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
The algorithmic self-assembly of shapes has been considered in several models of self-assembly. For the problem of shape construction, we consider an extended version of the two-handed tile assembly model, which contains positive (attractive) and negative (repulsive) interactions. As a result, portions of an assembly can become unstable and detach. In this model, we utilize fuel-efficient computation to perform Turing machine simulations for the construction of the shape. In this paper, we show how an arbitrary shape can be constructed using an asymptotically optimal number of distinct tile types (based on the shape’s Kolmogorov complexity). We achieve this at O(1) scale factor in this straightforward model, whereas all previous results with sublinear scale factors utilize powerful self-assembly models containing features such as staging, tile deletion, chemical reaction networks, and tile activation/deactivation. Furthermore, the computation and construction in our result only creates constant-size garbage assemblies as a byproduct of assembling the shape.more » « less
-
Meeks, Kitty; Scheideler, Christian (Ed.)The Tile Automata (TA) model describes self-assembly systems in which monomers can build structures and transition with an adjacent monomer to change their states. This paper shows that seeded TA is a non-committal intrinsically universal model of self-assembly. We present a single universal Tile Automata system containing approximately 4600 states that can simulate (a) the output assemblies created by any other Tile Automata system Γ, (b) the dynamics involved in building Γ’s assemblies, and (c) Γ’s internal state transitions. It does so in a non-committal way: it preserves the full non-deterministic dynamics of a tile’s potential attachment or transition by selecting its state in a single step, considering all possible outcomes until the moment of selection. The system uses supertiles, each encoding the complete system being simulated. The universal system builds supertiles from its seed, each representing a single tile in Γ, transferring the information to simulate Γ to each new tile. Supertiles may also asynchronously transition states according to the rules of Γ. This result also implies IU for pairwise asynchronous Cellular Automata.more » « less
-
Inspired by nature and motivated by a lack of top-down tools for precise nanoscale manufacture, self-assembly is a bottom-up process where simple, unorganized components autonomously combine to form larger more complex structures. Such systems hide rich algorithmic properties - notably, Turing universality - and a self-assembly system can be seen as both the object to be manufactured as well as the machine controlling the manufacturing process. Thus, a benchmark problem in self-assembly is the unique assembly of shapes: to design a set of simple agents which, based on aggregation rules and random movement, self-assemble into a particular shape and nothing else. We use a popular model of self-assembly, the 2-handed or hierarchical tile assembly model, and allow the existence of repulsive forces, which is a well-studied variant. The technique utilizes a finely-tuned temperature (the minimum required affinity required for aggregation of separate complexes). We show that calibrating the temperature and the strength of the aggregation between the tiles, one can encode the shape to be assembled without increasing the number of distinct tile types. Precisely, we show one tile set for which the following holds: for any finite connected shape S, there exists a setting of binding strengths between tiles and a temperature under which the system uniquely assembles S at some scale factor. Our tile system only uses one repulsive glue type and the system is growth-only (it produces no unstable assemblies). The best previous unique shape assembly results in tile assembly models use O(K(S)/(log K(S))) distinct tile types, where K(S) is the Kolmogorov (descriptional) complexity of the shape S.more » « less
-
Meeks, Kitty; Scheideler, Christian (Ed.)This work fully characterizes fractal generation in the seeded Tile Automata model (seeded TA), a model similar to the abstract Tile Assembly model (aTAM) with the added ability for adjacent tiles to change states. Under these assumptions, we first show that all discrete self-similar fractals (DSSFs) with feasible generators are strictly buildable at scale 1 and temperature 1 in seeded TA. We then show that these results imply the existence of a single seeded TA system Γ that can strictly build any DSSF infinitely at scale 1 and temperature 1.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
