Search

Many models of self-assembly have been shown to be capable of performing computation. Tile Automata was recently introduced combining features of both Cellular 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. [ABSTRACT FROM AUTHOR]

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 tradeoffs between systems with multi-tile seeds and those with single-tile seeds, which is fundamental to the measure of complexity of aTAM systems. [ABSTRACT FROM AUTHOR]