We study the computational power of the Full-Tilt model of motion planning, where slidable polyominos are moved maximally around a board by way of a sequence of directional "tilts." We focus on the deterministic scenario in which the tilts constitute a repeated clockwise rotation. We show that general-purpose computation is possible within this framework by providing a direct and efficient simulation of space-bounded Turing machines in which one computational step of the machine is simulated per O(1) rotations. We further show that the initial tape of the machine can be programmed by an initial tilt-sequence preceding the rotations. This result immediately implies new PSPACE-completeness results for the well-studied problems of occupancy (deciding if a given board location can be occupied by a tile), vacancy (deciding if a location can be emptied), relocation (deciding if a tile can be moved from one location to another), and reconfiguration (can a given board configuration be reconfigured into a second given configuration) that hold even for deterministically repeating tilt cycles such as rotations. All of our PSPACE-completeness results hold even when there is only a single domino in the system beyond singleton tiles. Following, we show that these results work in the Single-Step tilt model for larger constant cycles. We then investigate computational efficiency by showing a modification to implement a two-tape Turing machine in the Full-Tilt model and Systolic Arrays in the Single-Step model. Finally, we show a cyclic implementation for tilt-efficient Threshold Circuits.

The ability to detect whether a species (or dimension) is zero in Chemical Reaction Networks (CRN), Vector Addition Systems, or Petri Nets is known to increase the power of these models - making them capable of universal computation. While this ability may appear in many forms, such as extending the models to allow transitions to be inhibited, prioritized, or synchronized, we present an extension that directly performs this zero checking. We introduce a new void genesis CRN variant with a simple design that merely increments the count of a specific species when any other species' count goes to zero. As with previous extensions, we show that the model is Turing Universal. We then analyze several other studied CRN variants and show that they are all equivalent through a polynomial simulation with the void genesis model, which does not merely follow from Turing-universality. Thus, inhibitor species, reactions that occur at different rates, being allowed to run reactions in parallel, or even being allowed to continually add more volume to the CRN, does not add additional simulation power beyond simply detecting if a species count becomes zero.

Discrete chemical reaction networks formalize the interactions of molecular species in a well-mixed solution as stochastic events. Given their basic mathematical and physical role, the computational power of chemical reaction networks has been widely studied in the molecular programming and distributed computing communities (e.g., in the language of population protocols). While for Turing-universal systems there is a universal measure of optimal information encoding based on Kolmogorov complexity, chemical reaction networks are not Turing universal unless error and unbounded molecular counts are permitted. Nonetheless, here we show that the optimal number of reactions to generate a specific count x ∈ ℕ with probability 1 is asymptotically equal to a "space-aware" version of the Kolmogorov complexity of x, defined as Ks(x) = minp {|p|/log|p| + log(space(U(p))) :U(p) = x}, where p is a program for universal Turing machine U. This version of Kolmogorov complexity incorporates not just the length of the shortest program for generating x, but also the space usage of that program. Probability 1 computation is captured by the standard notion of stable computation from distributed computing, but we limit our consideration to chemical reaction networks obeying a stronger constraint: they "know when they are done" in the sense that they produce a special species to indicate completion. As part of our results, we develop a module for encoding and unpacking any b bits of information via O(b/log b) reactions, which is information-theoretically optimal for incompressible information. Our work provides one answer to the question of how succinctly chemical self-organization can be encoded---in the sense of generating precise molecular counts of species as the desired state.

Life is built upon amazingly sophisticated molecular machines whose behavior combines mechanical and chemical action. Engineering of similarly complex nanoscale devices from first principles remains an as yet unrealized goal of bioengineering. In this paper we formalize a simple model of mechanical motion (mechanical linkages) combined with chemical bonding. The model has a natural implementation using DNA with double-stranded rigid links, and single-stranded flexible joints and binding sites. Surprisingly, we show that much of the complex behavior is preserved in an idealized topological model which considers solely the graph connectivity of the linkages. We show a number of artifacts including Boolean logic, catalysts, a fueled motor, and chemo-mechanical coupling, all of which can be understood and reasoned about in the topological model. The variety of achieved behaviors supports the use of topological chemical linkages in understanding and engineering complex molecular behaviors.

Traditionally, computation within self-assembly models is hard to conceal because the self-assembly process generates a crystalline assembly whose computational history is inherently part of the structure itself. With no way to remove information from the computation, this computational model offers a unique problem: how can computational input and computation be hidden while still computing and reporting the final output? Designing such systems is inherently motivated by privacy concerns in biomedical computing and applications in cryptography. In this paper we propose the problem of performing “covert computation” within tile self-assembly that seeks to design self-assembly systems that “conceal” both the input and computational history of performed computations. We achieve these results within the growth-only restricted abstract Tile Assembly Model (aTAM) with positive and negative interactions. We show that general-case covert computation is possible by implementing a set of basic covert logic gates capable of simulating any circuit (functionally complete). To further motivate the study of covert computation, we apply our new framework to resolve an outstanding complexity question; we use our covert circuitry to show that the unique assembly verification problem within the growth-only aTAM with negative interactions is coNP-complete.

The natural process of self-assembly has been studied through various abstract models due to the abundant applications that benefit from self-assembly. Many of these different models emerged in an effort to capture and understand the fundamental properties of different physical systems and the mechanisms by which assembly may occur. A newly proposed model, known as Tile Automata, offers an abstract toolkit to analyze and compare the algorithmic properties of different self-assembly systems. In this paper, we show that for every Tile Automata system, there exists a Signal-passing Tile Assembly system that can simulate it. Finally, we connect our result with a recent discovery showing that Tile Automata can simulate Amoebot programmable matter systems, thus showing that the Signal-passing Tile Assembly can simulate any Amoebot system.

Advances in technology have given us the ability to create and manipulate robots for numerous applications at the molecular scale. At this size, fabrication tool limitations motivate the use of simple robots. The individual control of these simple objects can be infeasible. We investigate a model of robot motion planning, based on global external signals, known as the tilt model. Given a board and initial placement of polyominoes, the board may be tilted in any of the 4 cardinal directions, causing all slidable polyominoes to move maximally in the specified direction until blocked. We propose a new hierarchy of shapes and design a single configuration that is strongly universal for any w × h bounded shape within this hierarchy (it can be reconfigured to construct any w × h bounded shape in the hierarchy). This class of shapes constitutes the most general set of buildable shapes in the literature, with most previous work consisting of just the first-level of our hierarchy. We accompany this result with a O(n4 log n)-time algorithm for deciding if a given hole-free shape is a member of the hierarchy. For our second result, we resolve a long-standing open problem within the field: We show that deciding if a given position may be covered by a tile for a given initial board configuration is PSPACEcomplete, even when all movable pieces are 1 × 1 tiles with no glues. We achieve this result by a reduction from Non-deterministic Constraint Logic for a one-player unbounded game.

We investigate the problem of assembling general shapes and patterns in a model in which particles move based on uniform external forces until they encounter an obstacle. In this model, corresponding particles may bond when adjacent with one another. Succinctly, this model considers a 2D grid of “open” and “blocked” spaces, along with a set of slidable polyominoes placed at open locations on the board. The board may be tilted in any of the 4 cardinal directions, causing all slidable polyominoes to move maximally in the specified direction until blocked. By successively applying a sequence of such tilts, along with allowing different polyominoes to stick when adjacent, tilt sequences provide a method to reconfigure an initial board configuration so as to assemble a collection of previous separate polyominoes into a larger shape. While previous work within this model of assembly has focused on designing a specific board configuration for the assembly of a specific given shape, we propose the problem of designing universal configurations that are capable of constructing a large class of shapes and patterns. For these constructions, we present the notions of weak and strong universality which indicate the presence of “excess” polyominoes after the shape is constructed. In particular, for given integers h, w, we show that there exists a weakly universal configuration with O(hw) 1 × 1 slidable particles that can be reconfigured to build any h × w patterned rectangle. We then expand this result to show that there exists a weakly universal configuration that can build any h × w-bounded size connected shape. Following these results, which require an admittedly relaxed assembly definition, we go on to show the existence of a strongly universal configuration (no excess particles) which can assemble any shape within a previously studied “drop” class, while using quadratically less space than previous results. Finally, we include a study of the complexity of deciding if a particle within a configuration may be relocated to another position, and deciding if a given configuration may be transformed into a second given configuration. We show both problems to be PSPACE-complete even when no particles stick to one another and movable particles are restricted to 1 × 1 tiles and a single 2 × 2 polyomino.

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.