Source-linked AI summary
Active Self-Assembly of Algorithmic Shapes and Patterns in Polylogarithmic Time
Damien Woods, Ho-Lin Chen, Scott Goodfriend, Nadine Dabby, Erik Winfree, Peng Yin
TL;DR
For some hard-to-compute shapes, previous constructions require temporary growth beyond the target boundary. This paper models active self-assembly with growing, state-changing, moving monomers and shows that shapes and patterns can be assembled with polylogarithmic time and monomer-type costs, plus the relevant computation and description costs.
Problem
For shapes whose pixels require more than n time and space to compute on a Turing machine, previous computable constructions require temporary growth beyond the shape boundary.
Source: §1 · p. 4Method
The nubot model uses simple monomers that grow or shrink, change state, and move relative to one another under asynchronous pairwise rules.
Source: §1 · p. 3Results
Arbitrary connected two-dimensional shapes and patterns are assembled in expected polylogarithmic time plus per-pixel Turing-machine computation, using logarithmically many monomer types plus shape or pattern Kolmogorov complexity.
Source: §1 · pp. 3–4Takeaways & Limitations
The constructions keep pattern growth in-place within the boundary and can begin from a single monomer using local information in a distributed, asynchronous process.
Source: §1 · p. 4The model lacks a realistic notion of persistence length.
Source: §8 · p. 32
Abstract
from arXiv · showhide
We describe a computational model for studying the complexity of self-assembled structures with active molecular components. Our model captures notions of growth and movement ubiquitous in biological systems. The model is inspired by biology's fantastic ability to assemble biomolecules that form systems with complicated structure and dynamics, from molecular motors that walk on rigid tracks and proteins that dynamically alter the structure of the cell during mitosis, to embryonic development where large-scale complicated organisms efficiently grow from a single cell. Using this active self-assembly model, we show how to efficiently self-assemble shapes and patterns from simple monomers. For example, we show how to grow a line of monomers in time and number of monomer states that is merely logarithmic in the length of the line. Our main results show how to grow arbitrary connected two-dimensional geometric shapes and patterns in expected time that is polylogarithmic in the size of the shape, plus roughly the time required to run a Turing machine deciding whether or not a given pixel is in the shape. We do this while keeping the number of monomer types logarithmic in shape size, plus those monomers required by the Kolmogorov complexity of the shape or pattern. This work thus highlights the efficiency advantages of active self-assembly over passive self-assembly and motivates experimental effort to construct general-purpose active molecular self-assembly systems.
1 Introduction
Biological development and active molecular systems motivate a model in which simple components grow, change state, and move to assemble complex structures. The introduction presents efficient constructions and distinguishes the model from prior approaches through its movement rule and focus on simple components.
1 Introduction
- Biological development motivates active assembly because it combines exponential growth with state changes that guide processes involving insertion and rearrangement.The introduction also relates molecular programming to programmable DNA-tile systems and active nanostructures whose structure can change dynamically.Source: §1 · pp. 2–3
- A two-dimensional grid of monomers follows asynchronous pairwise rules for state changes, appearance, disappearance, and movement, with local moves propagating nonlocally.The system evolves as a continuous-time Markov process; the paper identifies movement as crucial to construction efficiency.Source: §1 · p. 3
- The model builds a monomer line in logarithmic time in line length using movement, appearance, and state change, and builds an n × log2 n rectangle while counting from 0 to n − 1.Logarithmic-time line construction is provably impossible in the passive abstract tile assembly model.Source: §1 · p. 3
- The model assembles arbitrary connected shapes and patterns in polylogarithmic time plus per-pixel Turing-machine computation, using logarithmically many monomer types plus shape or pattern Kolmogorov complexity.The construction is initiated by one monomer and proceeds with local information in a distributed, asynchronous fashion.Source: §1 · pp. 3–4
1.1 Related work
- Prior tile, graph-rewriting, and reconfigurable-robot models share computational or reconfiguration themes, but nubots emphasize geometric movement and very few states.Some active tile models change internal states or remove tiles, while the cited comparisons do not share the nubot model's notion of movement.Source: §1.1 · pp. 5–7
2 Nubot model description
The Nubot model represents assemblies as monomers on a triangular grid whose local rules can change states and bonds, create or remove monomers, and move them. Agitation, stability, and continuous-time system evolution specify how configurations can move and how expected time is analyzed.
2 Nubot model description
- The model places state-labelled monomers on a two-dimensional triangular grid, with neighboring monomers connected by flexible, rigid, or null bonds.A configuration is a finite set of monomers at distinct locations together with their bonds.Source: §2 · p. 8
2.1 Rules
- Rules act on adjacent monomers to change states and bonds, create or remove monomers, or move one monomer by a unit distance.Movement rules nondeterministically choose an arm and a stationary base; the movement can carry a movable set, but is blocked when that set is empty.Source: §2.1 · pp. 8–10
2.2 Agitation
- Agitation moves a minimal set of monomers without breaking bonds or causing collisions, while leaving their states and bond types unchanged.The paper's constructions do not exploit agitation and work whether it is present or absent.Source: §2.1 · p. 9, §2.2 · p. 11
2.3 Stability
- A configuration is stable when agitation of any monomer in any of six directions moves the entire assembly together.The paper uses stability to help establish that structures do not disconnect or reach unintended configurations.Source: §2.3 · p. 11
2.4 System evolution
- The system evolves as a continuous-time Markov process, with each applicable rule or agitation step assigned rate 1 in this paper.When every producible configuration has at most one stable connected component, expected transition time is unchanged by including or omitting agitation; the constructions satisfy this assumption.Source: §2.4 · p. 12
3 Examples
The examples demonstrate growth, movement, insertion, rotation, and algorithmically directed behavior in the Nubot model. Their running times range from constant or linear to logarithmic, depending on the operation.
3 Examples
- A chain starting from one monomer in state k uniquely produces k + 1 monomers in expected time k.The construction uses k sequential events, each with unit expected time.Source: §3 · p. 13, Figure 4 · p. 13
- A single-monomer walker moves n steps along a linear track in O(n) expected time.The figure's rules implement the subroutine shown alongside the example.Source: §3 · p. 13, Figure 5 · p. 13
- Inserting one monomer between two others takes constant expected time.Figure 6 shows the rules, an example trajectory, and a subroutine abstraction.Source: §3 · p. 13, Figure 6 · p. 14
- Rotating an arm of n monomers takes O(log n) expected time because each monomer moves independently.The paper notes that this speed is impossible for cellular automata and has an analog in reconfigurable robotics.Source: §3 · p. 13, Figure 7 · p. 14
- A Turing machine example stores its program in the rule set and directs the tape head to move and update tape monomers.New tape-cell monomers can be created when a longer tape is needed, demonstrating algorithmically directed behavior.Source: §3 · p. 13
4 System simulation
The section gives an O(tn^2)-time algorithm for simulating an assembly trajectory and establishes that its movement rule can be simulated tractably. Its movable-set subroutine runs in O(n) time and identifies the minimal set that can move without collisions or bond disruption.
4 System simulation
- O(tn^2) time suffices to simulate a trajectory with t transitions and at most n monomers per configuration.The algorithm also provides the basis for the paper’s software simulator.Source: §4 · p. 14
4.1 Simulation of a single step
- O(n^2) time suffices for one simulation step, with movement taking O(n^2) and other rule types taking O(n).Movement is costlier because the movable-set algorithm may be tried up to n times, with each attempt taking O(n).Source: §4.1 · p. 15
4.2 Computing the movable set
- The greedy movable-set algorithm identifies the movable set in O(n) time for a configuration with n monomers.Its output is the minimal set containing the arm but not the base that can move without collisions or bond disruption.Source: §4.2 · p. 16
- The proof establishes that a nonempty output can move safely and minimally, while an empty output means no movable set containing the arm avoids the base.The argument checks that blockers are added to the set until the set can move or must include the base.Source: §4.2 · p. 16
- Choosing which monomer is the arm versus the base can change the resulting configuration, but the paper does not exploit this asymmetry.Swapping the arm and base in the Figure 3a example induces a different movable set.Source: §4.2 · p. 16
5 Efficient growth of simple shapes: lines and squares
The section gives logarithmic-time, logarithmic-state constructions for lines and squares, along with a fast mechanism for synchronizing a completed line. The constructions use asynchronous growth and movement to build and coordinate monomers.
5.1 Line
- A line of length n can be uniquely produced in expected time O(log n) with O(log n) states.The construction decomposes n into O(log n) distinct powers of 2 and grows the corresponding lines in parallel.Source: §5.1 · pp. 17, 19, Figure 9 · p. 17
- Repeated pairwise insertions expand a seeded line until its monomers reach state 0, with disjoint subroutines able to run asynchronously without interference.Each left-right pair creates two adjacent left-right pairs, while rigid bonds keep the structure stable.Source: §5.1 · pp. 17, 19
- A synchronization row grows beneath completed regions of a line and shifts relative to the backbone once all insertions finish, signaling monomers to switch state.The shift takes O(1) time; growing and deleting the row take O(log n) expected time, using O(log n) states overall.Source: §5.1 · pp. 20–22, Figure 11 · p. 21
5.2 Square
- An n × n square can be constructed in O(log n) time using O(log n) states.The construction grows and synchronizes vertical lines, then contracts the backbone to bring them into contact.Source: §5.2 · p. 22
6 Computable shapes
The section constructs arbitrary connected computable shapes by enumerating pixel locations, computing membership in parallel, folding the results into a square, and safely deleting absent pixels. The expected time is O(log^2 n + t(|n|)), with O(s + log n) states.
6 Computable shapes
- An arbitrary connected computable 2D shape of size at most √n × √n can be constructed in expected time O(log^2 n + t(|n|)) using O(s + log n) states.Here, t(|n|) is the time for a program-size s Turing machine to decide whether a given pixel is present.Source: §6 · p. 23
6.1 Construction overview
- The construction first builds a binary counter of pixel locations, runs a membership computation for each location, folds the resulting backbone into a square, and carves away absent pixels.Figure 13 shows the construction overview.Source: §6.1 · p. 23, Figure 13 · p. 24
6.2 Binary counter
- A binary counter writes the numbers 0 through n −1 in O(log^2 n) time using O(log n) states, by copying rows and appending successive 0 and 1 bits.The counter grows asynchronously; its copying and bit-flipping mechanism ensures that rows encode the correct sequences.Source: §6.2 · pp. 23, 25, Figure 14 · p. 26
6.2.1 Counter synchronization
- After the backbone and counter rows finish, a synchronization routine informs backbone monomers that the counter is complete in expected time O(log n).The routine is applied after the backbone reaches length n and all rows finish their final copying.Source: §6.2.1 · p. 25
6.3 Turing machine computations
- Parallel Turing-machine heads decide whether each pixel belongs to the shape, with each computation taking at most t(|n|) time and O(s) program states.Heads use counter rows as tapes, grow additional tape monomers if needed, and transmit yes/no answers to the backbone.Source: §6.3 · pp. 25–27
6.4 Folding
- The backbone folds into an n × n square through parallel arm rotations and synchronization, with the folding step taking expected time O(log^2 n).Folding uses O(1) states.Source: §6.4 · p. 27
6.5 Bonding and carving
- Distributed carving deletes no-pixels only after bonding conditions are met, preserving connectedness while producing the desired shape.After folding, bonding and carving together take expected time O(log n).Source: §6.5 · pp. 27–28
7 Efficient computation of patterns
The section constructs colored n × n patterns in expected time O(log^(ℓ+1) n), using O(s + log n) monomer states and without growth beyond pattern borders. It does so asynchronously and without explicit synchronization.
7 Efficient computation of patterns
- An arbitrary finite computable pattern of size at most n × n can be constructed without growth outside its borders in expected time O(log^(ℓ+1) n), using O(s + log n) states.Each pixel’s color is computable by a polynomial-time, linear-space Turing machine running in O(log^ℓ n) time.Source: §7 · p. 28
7.1 Vertical and horizontal binary counters
- Vertical counter rows rotate into a backbone column, then initiate horizontal counters that copy each row’s index and generate all column indices.The resulting strips encode distinct pairs (i, j); Figure 16 sketches the row reconfiguration.Source: §7.1 · pp. 29–30, Figure 16 · p. 29
7.2 Turing machine computations
- Turing machines use each completed strip as a tape to compute the colors of its pixels, completing all computations in expected time O(log^(ℓ+1) n).The machines use coordinates (i, j, p) and require at most log2 n tape space; Figure 17 depicts the strip as input and work tape.Source: §7.2 · pp. 30–31, Figure 17 · p. 30
7.3 Patterns with diameter a power of 2
- For n that is a single power of 2, the construction adds a final row of k monomers and processes their pixels sequentially, adding only a constant factor to time.Here k = n −⌊n / log n⌋log n < log n.Source: §7.3 · p. 31
8 Discussion and future work
The discussion frames nubots as a model for efficiently generating shapes and patterns, while identifying open questions about connectivity, dynamic structures, physical realism, and the model’s computational limits.
8 Discussion and future work
- The nubot model generates a wide variety of shapes and patterns exponentially quickly, with the aim of exploring molecular computation seen in nature and emerging laboratory systems.The authors note that the constructions produce shapes and patterns that are ultimately static.Source: §8 · p. 31
- The paper builds ultimately static structures, leaving open which forever-dynamic structural systems nubots can model, unlike cellular automata that lack the model’s notion of movement.The authors ask which dynamic structural systems can and cannot be modeled.Source: §8 · pp. 31–32
- The model lacks a realistic notion of persistence length, and the authors propose defining tensile-strength or persistence-length resources to better capture molecular-scale laboratory behavior.They also ask what systems can be built under variable-strength bond constraints and how bond-strength cost relates to the shapes, patterns, or dynamics modeled.Source: §8 · p. 32
- The authors leave comparison with reconfigurable robots and laboratory implementation of nubots as future work, noting differences between molecular- and macro-scale systems.The cited robot models achieve arbitrary reconfiguration in logarithmic time, or linear parallel time under more realistic physical constraints.Source: §8 · pp. 32–34
- The pattern construction does not produce a completely connected assembly; synchronization can make it completely connected, leaving open whether this is possible deterministically in polylogarithmic time without long-range communication.The question concerns an n × n square and communication over distances greater than log n.Source: §8 · pp. 32–33
- Open computational questions include upper and lower bounds for nubots and better tools for time analysis, since many expressible systems do not meet the Chernoff-bound lemma’s conditions.The paper asks whether a near-linear expected-time bound follows from the longest sequence of rule applications leading to a terminal monomer type.Source: §8 · pp. 32–33
- The discussion proposes remote rule triggering as a future extension and asks what flexible bonds enable beyond constructions that can avoid them.Remote triggering is not considered in the paper; the only construction that uses flexible bonds is synchronization, which can also be designed without them under agitation.Source: §8 · p. 33