PaperlayerView exact revision on arXiv

Source-linked AI summary

The tile assembly model is intrinsically universal

David Doty, Jack H. Lutz, Matthew J. Patitz, Robert T. Schweller, Scott M. Summers, Damien Woods

arXiv:1111.3097v2cs.DScs.CC

TL;DR

Controlling nanoscale self-assembly is a major technical challenge. This paper gives the aTAM a single intrinsically universal tile set, using genome-carrying supertiles to simulate any tile assembly system, and proves universality for the full model at any temperature.

  • Problem

    Controlling nanoscale self-assembly processes is an enormous technical challenge.

    Source: §1 · p. 2

  • Method

    Each supertile carries an encoding of the simulated system, which is expressed at each location to determine whether and which simulated tile to generate.

    Source: §1 · p. 3

  • Results

    A single tile set is intrinsically universal for all tile assembly systems, with the construction covering the full aTAM at any temperature.

    Source: §1 · p. 2, §3 · p. 6

  • Takeaways & Limitations

    The universal tile set captures the local interactions, nondeterminism, and tile-growth processes of any tile assembly system on a global scale.

    Source: §1 · p. 3

    Bounded space for random-number generation makes perfectly uniform selection impossible to guarantee.

    Source: §10.1 · p. 48

Abstract

from arXiv · show

We prove that the abstract Tile Assembly Model (aTAM) of nanoscale self-assembly is intrinsically universal. This means that there is a single tile assembly system U that, with proper initialization, simulates any tile assembly system T. The simulation is "intrinsic" in the sense that the self-assembly process carried out by U is exactly that carried out by T, with each tile of T represented by an m x m "supertile" of U. Our construction works for the full aTAM at any temperature, and it faithfully simulates the deterministic or nondeterministic behavior of each T. Our construction succeeds by solving an analog of the cell differentiation problem in developmental biology: Each supertile of U, starting with those in the seed assembly, carries the "genome" of the simulated system T. At each location of a potential supertile in the self-assembly of U, a decision is made whether and how to express this genome, i.e., whether to generate a supertile and, if so, which tile of T it will represent. This decision must be achieved using asynchronous communication under incomplete information, but it achieves the correct global outcome(s).

1 Introduction

The paper establishes intrinsic universality for the full aTAM: one initialized tile set simulates any system while reproducing its self-assembly process. Genome-bearing supertiles and local communication support this simulation, whose precise notion of simulation also offers a finer way to compare self-assembly models.

1 Introduction

  • Structural DNA nanotechnology uses nucleic acids to engineer nanoscale structures, while the aTAM idealizes two-dimensional, error-free self-assembly from a seed.The aTAM uses matching glues with sufficient total strength for tiles to bind.Source: §1 · p. 2
  • A single tile set intrinsically simulates any aTAM system, representing each simulated tile as an m × m supertile and preserving deterministic or nondeterministic behavior at any temperature.The simulating system uses temperature 2.Source: §1 · pp. 2–3
  • Each supertile carries the simulated system’s complete genome along its supersides, and local decisions determine whether it forms and which simulated tile it represents.The choice is nondeterministic precisely where the simulated system is nondeterministic.Source: §1 · p. 3
  • Frames, crawlers, and probes coordinate asynchronous communication between supersides while avoiding blocked paths needed for later communication.Frames communicate with adjacent supersides, crawlers carry information across the supertile, and probes communicate with the opposite superside.Source: §1 · p. 3
  • Intrinsic universality supplies a tighter basis for comparing self-assembly models than tile complexity or Turing-machine simulation alone.Combining the result with existing simulations can yield a single tile set in another model that simulates any aTAM system [9].Source: §1 · pp. 3–4
  • Unlike the restricted aTAM submodel in, this work takes a completely different approach, using new frames, crawlers, and probes to simulate the full aTAM.Source: §1 · p. 4

2 Abstract Tile Assembly Model

This section defines the aTAM’s tiles, assemblies, stability, and growth rules. It also states glue-strength and label assumptions used to simplify the construction.

2 Abstract Tile Assembly Model

  • A tile type is a unit square whose four sides each carry a glue label and a nonnegative integer strength; an assembly places tiles on the integer lattice.An assembly is τ-stable when every cut in its binding graph has strength at least τ.Source: §2 · p. 5
  • A tile assembly system consists of a finite tile set, a finite τ-stable seed, and a temperature; producible assemblies grow by stable single-tile attachments.A system is directed when it has exactly one producible terminal assembly.Source: §2 · p. 5
  • The construction assumes glue strengths are at most τ and that labels are not shared by glues of unequal strength.The authors state these assumptions do not affect the model’s fundamental capabilities.Source: §2 · p. 5

3 Main result

The section defines intrinsic simulation through m×m block representations and states that one tile set is intrinsically universal for all tile assembly systems. The construction’s scale is O(g^4 log g), where g is the number of distinct glues in the simulated system.

3 Main result

  • An m-block representation maps each m×m region of the simulating assembly to a tile or undefined space in T.A valid representation preserves a mapped block as it grows, and clean mapping permits extra tiles only adjacent to represented tiles, or in a lone nonempty block.Source: §3 · pp. 5–6
  • The cited conditions require both directions: every T step α →T β can be followed from any α′ with R*(α′)=α by an S step, and every S step maps to a T step.Source: §3 · p. 6
  • One tile set U is intrinsically universal for the class of all tile assembly systems.For each simulated system, computable functions choose its representation and seed, and U simulates it at a scale m.Source: §3 · p. 6
  • The construction achieves scale m = O(g^4 log g), where g is the number of different glues in T.The paper identifies decreasing this scale or proving a nontrivial lower bound as an open question.Source: §3 · p. 6

4 High-level description of construction

Each potential supertile must coordinate incomplete, asynchronous information from sides that may arrive in any order, while preserving the simulated system’s tile-growth behavior. Frames, crawlers, and probes gather and route that information so a supertile can determine whether and how to grow.

4.1 The fundamental problem of simulating arbitrary tile systems

  • Opposite supersides may need to test glue compatibility across a gap, yet connecting them can block later communication between the other sides.A later west input may require an east output, but an earlier north–south connection can create a barrier between east and west.Source: §4.1 · p. 7

4.2.1 Frame

  • Each side first builds a four-layer frame that records corner wins and losses and propagates side information, including glue and the simulated system’s encoding.A planar construction is nontrivial; the frame condenses possible side-arrival scenarios for later crawlers and probes.Source: §4.2.1 · pp. 8–9

4.2.2 Crawlers and lookup tables

  • Crawlers gather adjacent glue information, consult an encoded tile lookup table, and, when binding is sufficient, may create output supersides on unoccupied sides.A crawler remains unfilled after an unsuccessful lookup and can later combine information from a newly arriving side.Source: §4.2.2 · p. 9

4.2.3 More general crawler protocol

  • The general protocol initiates crawlers when sides connect unless frame information indicates another crawler is coming; successful crawlers test potential outputs before placing them.An unsuccessful crawler waits at the supertile edge for a possible new input side and another lookup.Source: §4.2.3 · p. 10

4.2.4 Multiple crawlers

  • When crawlers meet, one can use information passed through another crawler to complete a lookup; with four sides present, corner precedence selects a unique output crawler.If the earlier crawler is full, the arriving crawler stops; otherwise it can use additional glue information and may overtake it.Source: §4.2.4 · p. 10

4.2.5 Probes

  • Probes grow across a gap only when a side has a win-win frame, so at most two opposite sides probe and adjacent probes cannot interfere.Probes close the gap only when the represented glues match a tile type with sufficient binding strength; otherwise, space remains for crawlers.Source: §4.2.5 · p. 11

4.2.6 Simulation of nondeterministic tile systems

  • For nondeterministic systems, a random choice selects among matching tile types, and meeting probes share that choice so both sides encode the same tile.If probes do not meet, a single responsible crawler can generate the choice before its lookup.Source: §4.2.6 · p. 11

5 Supertile layout

Supertile layout depends on how many supersides must cooperate to produce outputs. The section introduces side encoding and then covers layouts from one-sided binding onward.

5 Supertile layout

  • The layout of completed supertiles depends substantially on how many supersides must cooperate to produce output supersides.The overview proceeds from superside layout to supertile layout, beginning with one-sided binding.Source: §5 · p. 12
  • The section presents frames, probes, and crawlers as mechanisms for sharing information so it can move around a simulated supertile.The overview focuses on their high-level operation rather than their detailed interactions.Source: §5 · p. 12
  • Detailed mechanism descriptions appear in Sections 7–9, while Section 6 argues the construction’s correctness.The overview builds on the preceding layout descriptions.Source: §5 · p. 12

5.1 Superside layout

A superside is a linear encoding of the simulated system and one side of a simulated tile. Its regions include glue data, lookup tables, and probe information.

5.1 Superside layout

  • A superside contains O(g4 log g) tiles encoding the simulated system T and one side of a simulated tile.Figure 2 shows the south superside’s regions, including glue, lookup, and probe areas.Source: §5.1 · p. 12, Figure 2 · p. 12
  • The south superside layout includes two tile-lookup tables, a probe region and table, and a blank region that preserves symmetry.The probe table computes probe positions in output supersides; the blank region matches the length of the probe region and table.Source: §5.1 · p. 12, Figure 2 · p. 12
  • Duplicated regions support lookups at both ends and copying encoded superside information to new output supersides; strength-τ is flagged in each tile type.The strength bit supports rules governing crawler growth or state changes.Source: §5.1 · p. 12

5.2 One-sided binding

For one-sided binding, a strength-τ input can trigger a lookup and output construction. With non-contributing inputs, crawlers detect occupied sides and coordinate output around them.

5.2 One-sided binding

  • A strength-τ south superside sends a probe to the center, where it initiates a crawler that looks up the south glue and may output three supersides.The crawler’s random number selects among valid tile types, and successful output construction supplies the remaining encoded sides.Source: §5.2 · pp. 13–14, Figure 3 · p. 13

5.2.1 One-sided binding with non-contributing input sides

  • When opposite strength-τ supersides compete, the first probe to claim the center initiates crawlers that share the same glue and random choice.The east crawler stops when it detects the north input, while the west crawler performs a lookup along that side.Source: §5.2.1 · p. 14, Figure 4 · p. 15
  • In other cases with non-contributing inputs, a single crawler moves counterclockwise, detects occupied sides, and outputs only where needed.A non-contributing input superside is one not used to simulate tile binding; mismatching supersides are an example.Source: §5.2.1 · pp. 14–15

5.3 Two-sided binding

For two contributing sides, adjacent sides cooperate through a corner crawler, while opposite sides use meeting probes to coordinate crawlers across the gap. With non-contributing input sides, crawlers use frame information and precedence to avoid duplicate or blocked outputs.

5.3 Two-sided binding

  • Adjacent west and south sides initiate a crawler that looks up their glue pair and outputs the east and north supersides when no east superside is present.The lookup uses a random number as input, allowing the simulated tile choice to follow the system’s behavior.Source: §5.3 · pp. 15–16
  • Meeting north and south probes initiate two crawlers that use the same glues and random number, producing consistent tile types for east and west output.This shares the information needed to simulate one tile binding despite the probes blocking the center path.Source: §5.3 · pp. 17–18, Figure 6 · p. 17

5.3.1 Two-sided binding with non-contributing input sides

  • With an adjacent non-contributing input side, the successful crawler outputs while another crawler halts after detecting that output; alternative growth orders can leave only the successful crawler.When two adjacent non-contributing sides are present, the crawler encodes the tile type in an O(log g)-tile column rather than outputting supersides.Source: §5.3.1 · pp. 18–19, Figure 7 · p. 19
  • For opposite-side binding with a non-contributing side, meeting probes can block one output direction while the crawler on that side halts after learning the center is blocked.Up to four crawlers may arise in the case with two adjacent non-contributing sides, but outputting crawlers detect those sides and stop growth.Source: §5.3.1 · pp. 19–21, Figure 8 · p. 20

5.4 Three-sided binding

Three-sided binding is handled by crawlers that gather glue information asynchronously, waiting when needed and using probes or competing crawlers to determine whether a tile can be simulated. The described configurations extend by rotation; an additional non-contributing side is handled as in four-sided binding.

5.4 Three-sided binding

  • When a north-west crawler lacks the south glue, it waits at the south-west corner and resumes lookup and east output after the south superside arrives.The waiting behavior handles the asynchronous arrival of a potential input side.Source: §5.4 · p. 21
  • When north and south probes do not meet, a north-west crawler gathers all three glues, becomes full, and outputs east.The probes can grow without meeting because the north and south glues do not match with sufficient strength.Source: §5.4 · p. 22, Figure 10 · p. 22
  • When two crawlers start, the one lacking sufficient strength waits while the crawler with all three glues becomes full and outputs east; a different growth order can leave only the successful crawler.The same handling applies to rotations of these three-sided cases.Source: §5.4 · pp. 23–24

5.4.1 Three-sided binding with a non-contributing input side

  • Three-sided binding with an additional non-contributing input side is treated as conceptually identical to four-sided binding, so its cases are not detailed separately.The difference is the number of glues in the lookup and a crawler’s unsuccessful output attempt.Source: §5.4.1 · p. 24

5.5 Four-sided binding

For four-sided binding, crawlers determine the represented tile type without producing output supersides. When two crawlers are initiated, precedence and shared frame information ensure that only one encodes the tile type.

5.5 Four-sided binding

  • A crawler that gathers all four glues performs a lookup, then encodes a matching tile type in an O(log g)-tile row or becomes dead if no tile matches.This single-crawler case includes configurations in which no probes are created.Source: §5.5 · p. 24
  • When two crawlers are initiated, precedence and knowledge of the four-sided win-loss configuration make one output the tile type and the other stop.If a crawler learns that a higher-precedence crawler will output, it stops; the highest-precedence crawler outputs after gathering the glues.Source: §5.5 · p. 24

6 Correctness of construction

The correctness argument checks that supertiles produce valid output supersides and encode the correct tile type, or encode no tile when binding should not occur. The crawler rules distinguish across-gap binding from other configurations and make the representation function computationally simple.

6 Correctness of construction

  • The representation function decodes an encoded tile type by checking a constant number of regions, each of size O(log g), and has FAC0 complexity.Correct superside decoding and tile encoding together imply that assembly sequences are simulated correctly.Source: §6 · pp. 25–26
  • Across-gap binding produces exactly two output-state crawlers, and both encode the same simulated tile type.The crawlers share glue information and a random number, including when two strength-τ probes connect.Source: §6 · pp. 26–27
  • For binding that is not across the gap, exactly one crawler enters the output state and uniquely encodes the simulated tile type.Additional crawlers from non-contributing input sides stop after determining that probe-initiated crawlers will encode the tile type.Source: §6 · p. 27
  • If the input glues cannot bind a tile type with sufficient strength, no crawler reaches the output state in a producible terminal assembly.Depending on the number and arrangement of input sides, crawlers either are not initiated, wait unfilled, or become dead after lookup.Source: §6 · p. 28

7 The Frame

The frame gathers input-glue and neighboring-side information before other supertile components form. Its four-layer growth coordinates competing sides and uses a WAI signal to prevent deadlock.

7 The Frame

  • Each frame side grows only when an adjacent supertile provides an output superside, transferring input-glue information inward while preventing growth on sides without inputs.The first layer grows as two halves from near the corners, stopping one tile short of the center.Source: §7 · pp. 28, 30, 31
  • A superside that wins both ends fills four layers, while one that loses waits for neighboring frame growth so it can incorporate that side’s information.This distributed coordination handles the asynchronous arrival of adjacent sides.Source: §7 · p. 30
  • The West side sends a WAI signal when it loses at exactly one end; the signal or another side’s completion reaches the waiting end and prevents deadlock.The signal can travel around the frame or bounce at a side that wins on its right, depending on the configuration.Source: §7 · p. 30
  • Competition tiles select which adjacent superside wins each end; the resulting LEFT/RIGHT outcomes are encoded as WW, WL, LW, or LL.When both adjacent supertiles could initiate a competition tile, nondeterministic placement determines which one binds.Source: §7 · p. 31
  • Layer 4 copies known side information and exposes end glues that can initiate frame growth for adjacent supersides.For a West neighbor, the tile next to the end tile also exposes an initiating glue.Source: §7 · p. 38

8 Probes

Probes let supersides test whether opposing glue information can support a simulated tile, and can initiate crawlers when the test succeeds. They also coordinate tile selection when multiple matching tiles are possible.

8 Probes

  • Opposing probes meet if and only if their represented glues match a tile type and have sufficient combined strength; otherwise, a gap remains for crawlers to pass.Each glue has a unique position in the probe region, with North/East and South/West using complementary growth patterns.Source: §8 · p. 39
  • When complementary probes meet, a tile between them initiates two crawlers that gather both glues for the later tile lookup.The probes advertise their glue information on their tips and sides for the crawlers to read.Source: §8 · p. 39
  • South or West probes advertise the same random number on both sides so two crawlers choose a consistent output tile when several choices are possible.The number is used during the later tile lookup.Source: §8 · p. 39
  • A strength-τ probe can test for an opposing strength-τ win-win side, helping ensure only one crawler is responsible for outputting supersides.The test claims the right to fill out the supertile rather than cooperating to form a tile.Source: §8 · p. 39

9 Crawlers

Crawlers collect glue information around a supertile, consult the encoded tile set, and either wait for further inputs or output a tile’s glue information. Their initiation, coordination, and state changes handle competing or piggybacking crawlers.

9 Crawlers

  • Crawlers gather input glues from frame sides or probes and consult the tile lookup table to determine whether they have sufficient information to match a simulated tile.If they do not, they continue along another input side or wait for one to arrive.Source: §9 · p. 40

9.1 Crawler initiation

  • Adjacent frame sides initiate a crawler only when they agree, using gathered W/L information to choose the appropriate corners for each configuration.Matching probes can also initiate two crawlers when they meet in the supertile’s center.Source: §9.1 · pp. 40–42

9.2 Multiple crawlers

  • When two crawlers meet, one may piggyback on the other; when both independently collect enough glue information, a corner precedence ranking breaks the tie.The chosen ranking is NW > SW > SE > NE.Source: §9.2 · p. 42

9.3 Crawler states

  • A crawler becomes full only after collected glues meet the threshold, match a tile type, and complete a lookup; it becomes output when it can produce a superside.The crawler’s logical states are unfilled, full, output, and dead.Source: §9.3 · p. 42

9.4 Outputting crawlers

  • A full crawler that wins POC2 at an unformed side transitions to output and starts an output initiation row that brings lookup and probe tables into position.Once the tables arrive, they support further crawler growth and pass their encodings into the output superside.Source: §9.4 · pp. 43, 45, 46

10 The tile lookup table

The tile lookup table encodes the simulated tile set so crawlers can find a tile consistent with their collected input glues. Its size determines the dominant contribution to the supertile’s scale.

10 The tile lookup table

  • A crawler reads the encoded tile table using its collected input glues; a match supplies a tile definition and makes the crawler full, while no match leaves it unfilled.The table encodes the simulated tile set and leaves space for lookup computations.Source: §10 · p. 46

10.1 Tile lookup table structure

  • The table indexes glue combinations as addresses and lists tiles valid for each address, including tiles whose input-glue strengths meet the simulated system’s threshold.A tile may be listed under multiple addresses when different subsets of its glues suffice.Source: §10.1 · p. 47

10.2 Example

  • In the illustrated lookup, the crawler counts to the matching address, selects an entry, copies that tile’s definition, and then computes its state.It can run two counters in parallel when performing two lookups at once.Source: §10.1 · p. 48, §10.2 · p. 49

10.3 Scale

  • The address-entry portion requires O(g^4 log g) space, making the tile lookup table—and thus its size—the main factor in the supertile scale.Alternating spacer tiles double the table’s width without changing that asymptotic bound.Source: §10.3 · pp. 49–50

A Abstract Tile Assembly Model

The section defines the abstract Tile Assembly Model (aTAM) and its core objects, growth rules, and behavioral properties. It also states simplifying assumptions on glue strengths and labels.

A Abstract Tile Assembly Model

  • A tile type assigns each of four sides a glue label and nonnegative strength; assemblies are connected arrangements of tiles on the integer lattice.Adjacent tiles interact when their abutting glues match and have positive strength.Source: A Abstract Tile Assembly Model · p. 50
  • A tile assembly system specifies a finite tile set, a finite stable seed, and a positive temperature; a tile attaches when the resulting assembly remains stable.The frontier consists of empty locations where a tile could stably attach.Source: A Abstract Tile Assembly Model · p. 51
  • Production proceeds through sequences of single-tile additions, and fairness requires that no frontier location remain starved indefinitely.Producible assemblies are those reachable from the seed; the production relation is a partial order.Source: A Abstract Tile Assembly Model · p. 51
  • A terminal assembly has no available attachment locations, while a directed system has a common producible extension for every pair of producible assemblies.Source: A Abstract Tile Assembly Model · p. 51
  • Glue strengths may be capped at the temperature without changing system behavior, and labels are not shared by glues of unequal strength.These assumptions are stated to simplify the main construction without affecting fundamental model capabilities.Source: A Abstract Tile Assembly Model · p. 51
Loading 1111.3097v2…