Abstract In this paper we present a model containing modifications to the Signal-passing Tile Assembly Model (STAM), a tile-based self-assembly model whose tiles are capable of activating and deactivating glues based on the binding of other glues. These modifications consist of an extension to 3D, the ability of tiles to form “flexible” bonds that allow bound tiles to rotate relative to each other, and allowing tiles of multiple shapes within the same system. We call this new model the STAM*, and we present a series of constructions within it that are capable of self-replicating behavior. Namely, the input seed assemblies to our STAM* systems can encode either “genomes” specifying the instructions for building a target shape, or can be copies of the target shape with instructions built in. A universal tile set exists for any target shape (at scale factor 2), and from a genome assembly creates infinite copies of the genome as well as the target shape. An input target structure, on the other hand, can be “deconstructed” by the universal tile set to form a genome encoding it, which will then replicate and also initiate the growth of copies of assemblies of the target shape. Since the lengths of the genomes for these constructions are proportional to the number of points in the target shape, we also present a replicator which utilizes hierarchical self-assembly to greatly reduce the size of the genomes required. The main goals of this work are to examine minimal requirements of self-assembling systems capable of self-replicating behavior, with the aim of better understanding self-replication in nature as well as understanding the complexity of mimicking it.

Abstract In this paper, we investigate shape-assembling power of a tile-based model of self-assembly called the Signal-Passing Tile Assembly Model (STAM). In this model, the glues that bind tiles together can be turned on and off by the binding actions of other glues via “signals”. Specifically, the problem we investigate is “shape replication” wherein, given a set of input assemblies of arbitrary shape, a system must construct an arbitrary number of assemblies with the same shapes and, with the exception of size-bounded junk assemblies that result from the process, no others. We provide the first fully universal shape replication result, namely a single tile set capable of performing shape replication on arbitrary sets of any 3-dimensional shapes without requiring any scaling or pre-encoded information in the input assemblies. Our result requires the input assemblies to be composed of signal-passing tiles whose glues can be deactivated to allow deconstruction of those assemblies, which we also prove is necessary by showing that there are shapes whose geometry cannot be replicated without deconstruction. Additionally, we modularize our construction to create systems capable of creating binary encodings of arbitrary shapes, and building arbitrary shapes from their encodings. Because the STAM is capable of universal computation, this then allows for arbitrary programs to be run within an STAM system, using the shape encodings as input, so that any computable transformation can be performed on the shapes. This is the full version, containing all construction and proof details, of a previously published extended abstract version that had most details omitted.

In the abstract Tile Assembly Model (aTAM) square tiles self-assemble, autonomously binding via glues on their edges, to form structures. Algorithmic aTAM systems can be designed in which the patterns of tile attachments are forced to follow the execution of targeted algorithms. Such systems have been proven to be computationally universal as well as intrinsically universal (IU), a notion borrowed and adapted from cellular automata showing that a single tile set exists which is capable of simulating all aTAM systems (FOCS 2012). The input to an algorithmic aTAM system can be provided in a variety of ways, with a common method being via the “seed” assembly, which is a pre-formed assembly from which all growth propagates. Arbitrary amounts of information can be encoded into seed assemblies by both (1) the types and patterns of glues exposed on their exteriors, and (2) their shapes. Since a common metric by which aTAM systems are measured is their tile complexity (i.e. the number of unique types of tiles they utilize), in order to provide a fair basis for comparison, systems are often designed with seed assemblies consisting of only a single seed tile, a.k.a. single-tile seeds. (For instance, in STOC 2000 and 2001 information theoretically optimal tile complexity was shown possible for the self-assembly of squares.) This requires the transferring of any information that may be encoded in a multi-tile seed assembly into tile complexity. In this paper, we explore this process to show when and how such transformations are possible while ensuring that a derived system with a single-tile seed faithfully replicates the behaviors of the original system. We first show that a trivial transformation, in which the locations of a multi-tile seed are tiled by “hard- coded” tiles that can grow to represent that seed from a single tile, can succeed only if (1) there are not tile locations in the seed such that there exist growth sequences where those locations could block future growth, or (2) an ordering of growth can be enforced for the growth of the seed from a single tile to ensure that such blocking locations are tiled before collisions are possible. However, we show that knowing if this is the case is uncomputable. Therefore, we examine what is possible if the scale factor of the original system is increased and show that all systems with multi-tile seeds can be transformed into systems with single-tile seeds at scale factor 3 (i.e. each tile of the original system is replaced by a 3 × 3 square of tiles), such that the transformed systems faithfully replicate the dynamics of the original systems. We also prove that this scale factor is optimal, and that in fact there exist systems with multi-tile seeds for which no systems at scale factors 1 or 2 (or scale factor 3 when a more restrictive form of simulation is required) with single-tile seeds exist that can even produce the same sets of terminal output shapes. Since the scale 3 transformation results in a tile complexity which is proportional to the size of the original tile set plus the size of the multi-tile seed multiplied by the scale factor, we then also provide a transformation that yields an asymptotically optimal tile complexity proportional to the Kolmogorov complexity of the original system and which is based on the IU construction from FOCS 2012. Additionally, we are able to make simple modifications to that construction to provide a single aTAM system which simultaneously and in parallel simulates all aTAM systems, and provide a connection between that system and the existence of systems within models other than the aTAM which are IU for the aTAM. This set of results provides a full characterization of the tradeoff's between systems with multi-tile seeds and those with single-tile seeds, which is fundamental to the measure of complexity of aTAM systems.

In this paper, we investigate shape-assembling power of a tile-based model of self-assembly called the Signal-Passing Tile Assembly Model (STAM). In this model, the glues that bind tiles together can be turned on and off by the binding actions of other glues via "signals". In fact, we prove our positive results in a version of the model in which it is slightly more difficult to work (where tiles are allowed to rotate) but show that they also hold in the standard STAM. Specifically, the problem we investigate is "shape replication" wherein, given a set of input assemblies of arbitrary shape, a system must construct an arbitrary number of assemblies with the same shapes and, with the exception of size-bounded junk assemblies that result from the process, no others. We provide the first fully universal shape replication result, namely a single tile set capable of performing shape replication on arbitrary sets of any 3-dimensional shapes without requiring any scaling or pre-encoded information in the input assemblies. Our result requires the input assemblies to be composed of signal-passing tiles whose glues can be deactivated to allow deconstruction of those assemblies, which we also prove is necessary by showing that there are shapes whose geometry cannot be replicated without deconstruction. Additionally, we modularize our construction to create systems capable of creating binary encodings of arbitrary shapes, and building arbitrary shapes from their encodings. Because the STAM is capable of universal computation, this then allows for arbitrary programs to be run within an STAM system, using the shape encodings as input, so that any computable transformation can be performed on the shapes.

In this paper we present a model containing modifications to the Signal-passing Tile Assembly Model (STAM), a tile-based self-assembly model whose tiles are capable of activating and deactivating glues based on the binding of other glues. These modifications consist of an extension to 3D, the ability of tiles to form "flexible" bonds that allow bound tiles to rotate relative to each other, and allowing tiles of multiple shapes within the same system. We call this new model the STAM*, and we present a series of constructions within it that are capable of self-replicating behavior. Namely, the input seed assemblies to our STAM* systems can encode either "genomes" specifying the instructions for building a target shape, or can be copies of the target shape with instructions built in. A universal tile set exists for any target shape (at scale factor 2), and from a genome assembly creates infinite copies of the genome as well as the target shape. An input target structure, on the other hand, can be "deconstructed" by the universal tile set to form a genome encoding it, which will then replicate and also initiate the growth of copies of assemblies of the target shape. Since the lengths of the genomes for these constructions are proportional to the number of points in the target shape, we also present a replicator which utilizes hierarchical self-assembly to greatly reduce the size of the genomes required. The main goals of this work are to examine minimal requirements of self-assembling systems capable of self-replicating behavior, with the aim of better understanding self-replication in nature as well as understanding the complexity of mimicking it.