Everybody Wants to Be a Seed: Arbitrary Single-Tile Seeds in the Abstract Tile Assembly Model

This section reproduces the brief informal sketch of the abstract Tile Assembly Model (aTAM) from [1] and [11], originally formulated in [6].

A tile type is a unit square with four sides, each consisting of a glue label, often represented as a finite string, and a nonnegative integer strength. A glue $g$ that appears on multiple tiles (or sides) always has the same strength $s_g$. An aTAM system has a finite set $T$ of tile types, but an infinite number of copies of each tile type, with each copy being referred to as a tile. An assembly is a positioning of tiles on the integer lattice ${\mathbb{Z}}^2$, described formally as a partial function $\alpha :{\mathbb{Z}}^2⇢T$. Let ${𝒜}^T$ denote the set of all assemblies of tiles from $T$, and let denote the set of finite assemblies of tiles from $T$. Write $\alpha ⊑\beta$ to denote that $\alpha$ is a subassembly of $\beta$, which means that $\mathrm{dom}\alpha \subseteq \mathrm{dom}\beta$ and $\alpha (p)=\beta (p)$ for all points $p\in \mathrm{dom}\alpha$. Two adjacent tiles in an assembly interact, or are attached, if the glue labels on their abutting sides are equal and have positive strength. Each assembly induces a binding graph, a grid graph whose vertices are tiles, with an edge between two tiles if they interact. The assembly is $\tau$-stable if every cut of its binding graph has strength at least $\tau$, where the strength of a cut is the sum of all of the individual glue strengths in the cut.

A tile assembly system (TAS) is a triple $𝒯=(T,\sigma ,\tau )$, where $T$ is a finite set of tile types, $\sigma :{\mathbb{Z}}^2⇢T$ is a finite, $\tau$-stable seed assembly, and $\tau$ is the temperature. An assembly $\alpha$ is producible if either $\alpha =\sigma$ or if $\beta$ is a producible assembly and $\alpha$ can be obtained from $\beta$ by the stable binding of a single tile. In this case write $\beta {\to }_1^{𝒯}\alpha$ ($\alpha$ is producible from $\beta$ by the attachment of one tile), and write $\beta {\to }^{𝒯}\alpha$ if $\beta {\to }_1^{𝒯\ast }\alpha$ ($\alpha$ is producible from $\beta$ by the attachment of zero or more tiles). An assembly is terminal if no tile can be $\tau$-stably attached to it. Let $𝒜\left[𝒯\right]$ be the set of producible assemblies of $𝒯$, and let ${𝒜}_{\mathrm{\square }}\left[𝒯\right]\subseteq 𝒜\left[𝒯\right]$ be the set of producible, terminal assemblies of $𝒯$. A TAS $𝒯$ is directed if $|{𝒜}_{\mathrm{\square }}\left[𝒯\right]|=1$.

An assembly sequence in a TAS $𝒯$ is a (finite or infinite) sequence $\overrightarrow{\alpha }=({\alpha }_0,{\alpha }_1,\mathrm{\dots })$ of assemblies in which each ${\alpha }_{i+1}$ is obtained from ${\alpha }_i$ by the addition of one tile, i.e. ${\alpha }_i{\to }_1^{𝒯}{\alpha }_{i+1}$. A set of locations $L_2\subset {\mathbb{Z}}^2$ depends upon some other set $L_1\subset {\mathbb{Z}}^2$ if, for every valid assembly sequence in $𝒯$, if a tile is placed in some location in $L_2$, a tile was previously placed in some location in $L_1$. In an assembly $\alpha \in 𝒜\left[𝒯\right]$, a tile $t$ at location $\overrightarrow{l}$ blocks a tile if there exists a valid assembly sequence which begins with $\alpha$ and results in one or more tiles adjacent to $t$ which did not require glues of $t$ to bind to the assembly and to which a tile of a type different than $t$ could bind with $\tau$ strength in location $\overrightarrow{l}$ if $t$ was removed.

This section defines the notion of simulation of a TAS by another. The following definitions are those either from [11] for the “standard” ones or from [1] for those that take into account the assembly of the seed representation from a single initial tile. For more in-depth discussions, see those papers.

Intuitively, simulation of a system $𝒯$ by a system $𝒮$ requires that there is some scale factor $m\in {\mathbb{Z}}^{+}$ such that $m\times m$ squares of tiles in $𝒮$ represent individual tiles in $𝒯$, and there is a representation function capable of inspecting assemblies in $𝒮$ and mapping them to assemblies in $𝒯$.

From this point on, let $T$ be a tile set, and let $m\in {\mathbb{Z}}^{+}$. An $m$-block macrotile over $T$ is a partial function $\alpha :{\mathbb{Z}}_m^2⇢T$, where ${\mathbb{Z}}_m=\{0,1,\mathrm{\dots },m-1\}$. Let $B_m^T$ be the set of all $m$-block macrotiles over $T$. The $m$-block with no domain is said to be empty. For a general assembly $\alpha :{\mathbb{Z}}^2⇢T$ and $(x,y)\in {\mathbb{Z}}^2$, define ${\alpha }_{x,y}^m$ to be the $m$-block macrotile defined by ${\alpha }_{x,y}^m(i_x,i_y)=\alpha (mx+i_x,my+i_y)$ for . For some tile set $S$, a partial function $R:B_m^S⇢T$ is said to be a valid $m$-block macrotile representation from $S$ to $T$ if for any $\alpha ,\beta \in B_m^S$ such that $\alpha ⊑\beta$ and $\alpha \in \mathrm{dom}R$, then $R(\alpha )=R(\beta )$.

For a given valid $m$-block macrotile representation function $R$ from tile set $S$ to tile set $T$, define the assembly representation function¹¹1Note that $R^{\ast }$ is a total function since every assembly of $S$ represents some assembly of $T$; the functions $R$ and $\alpha$ are partial to allow undefined points to represent empty space. $R^{\ast }:{𝒜}^S\to {𝒜}^T$ such that $R^{\ast }({\alpha }^{\prime })=\alpha$ if and only if $\alpha (x,y)=R\left({\alpha }_{x,y}^{\prime m}\right)$ for all $(x,y)\in {\mathbb{Z}}^2$. For an assembly ${\alpha }^{\prime }\in {𝒜}^S$ such that $R({\alpha }^{\prime })=\alpha$, ${\alpha }^{\prime }$ is said to map cleanly to $\alpha \in {𝒜}^T$ under $R^{\ast }$ if for all non empty blocks ${\alpha }_{x,y}^{\prime m}$, $(x,y)+(u_x,u_y)\in \mathrm{dom}\alpha$ for some $u_x,u_y\in \{-1,0,1\}$ such that $u_x^2+u_y^2\le 1$.

In other words, ${\alpha }^{\prime }$ may have tiles on macrotile blocks representing empty space in $\alpha$, but only if that position is adjacent to a tile in $\alpha$. Such growth “around the edges” of ${\alpha }^{\prime }$ is called fuzz and it is restricted to be adjacent to only valid macrotiles, but not diagonally adjacent (i.e. no diagonal fuzz).

In the following definitions, let $𝒯=(T,{\sigma }_T,{\tau }_T)$ be a tile assembly system, let $𝒮=(S,{\sigma }_S,{\tau }_S)$ be a tile assembly system, and let $R$ be a valid $m$-block representation function $R:B_m^S\to T$.

The previous definition essentially specifies that every time $𝒮$ simulates an assembly $\alpha \in 𝒜[𝒯]$, there must be at least one valid growth path in $𝒮$ for each of the possible next steps that $𝒯$ could make from $\alpha$ which results in an assembly in $𝒮$ that maps to that next step.

The following definition is one of the definitions of simulation that are relevant to use when simulating systems with multi-tile seeds with systems with single-tile seeds. It comes from [1].

This section defines a new type of tile assembly systems, whose seed is a single tile chosen at assembly time. Those are the systems that this paper is interested in.

An Omni-nuclear Tile Assembly System (OnTAS) is an ordered triple $𝒪=(T,\tau ,f_{\sigma })$ where $T$ is a finite set of tile types, $\tau$ is the temperature and $f_{\sigma }:T\to {\mathbb{Z}}^2$ is a function that associates a position in the plane to each tile type. Intuitively an OnTAS is a TAS whose seed is a single tile that can be be arbitrarily chosen from its tile set at execution time. Then, $f_{\sigma }$ indicates the coordinates where a tile is placed whenever it is used as the seed. The OnTAS are collectively known as the Omni-nuclear Tile Assembly Model or OnTAM.

Formally, an OnTAS represents the class of all aTAM TAS with tile set $T$ and temperature $\tau$ and whose seed is a single tile from $T$ whose position depends on the tile type:

For any $t\in T$, is the unique function whose domain and image set are the singletons $\left\{f_{\sigma }(t)\right\}$ and $\{t\}$, respectively.

This paper focuses on OnTAS with a behaviour that depends as little as possible on the type of the initial tile. Then, some properties concerning TAS can be intuitively extended to OnTAS $𝒪$ if those properties are followed by all the TAS of the corresponding $\widetilde{𝒪}$ set:

• $\mathrm{■}$

  A set of locations depends on another one if the former depends on the latter whichever the type of the initial tile.

• $\mathrm{■}$

  A subassembly is said to be producible by a given OnTAS if it is producible whichever the type of the initial tile.

Moreover, the notion of simulation can be extended as follows:

This leads to the following definition, which formalises the intuitive notion of what is a “robust” OnTAS, with a consistent behaviour:

Since the set of images of $f_{\sigma }$ is included in the set of ignored locations of a robust OnTAS, no location further than $m$ from the initial tile $t$ is ignored, whichever the type of $t$. All locations further than $m$ from the initial tile have “forgotten” the type of the initial tile.

The definition of $\widetilde{𝒪}$ shows that the behaviour of an OnTAS amounts to choosing non-deterministically among a set of TAS. A disjoint union of $k$ OnTAS with the same temperature implements this operation of non-deterministic choice: whenever $𝒮$ starts with a tile from ${𝒮}_i$, it will behave like ${𝒮}_i$, since the union is disjoint. Hence, being able to simulate an arbitrary TAS with an OnTAS is enough to be able to reproduce the behaviour of a non-deterministic selection among a fixed set of TAS of same temperature with an OnTAS. This in turn, precisely characterises OnTAS as “equivalent” to a non-deterministic selection within fixed sets of TAS. The following sections are dedicated to constructing an OnTAS that simulates an arbitrary TAS. Note that the OnTAS presented there is robust: its behaviour precisely matches that of the TAS and the choice of seed tile does not affect the shape or behavior shown in the resulting assembly sequence.

This section considers an illustrating example: the task of self-assembling a ray. In the aTAM, a TAS $𝒯$ with 2 tile types at temperature $\tau =1$ is sufficient for this (Figure 1(a)). One of the tile types corresponds to the single-tile seed $\sigma$ (in red). It has a single glue to which the tiles of the other type (in blue) can bind. Those have glues on 2 opposite sides so that the assembly grows in a line. An OnTAS with the same tile types and temperature does not have the same productions. If the first tile is of the non-seed type, the assembly can grow to the left as long as it keeps adding non-seed tiles at each step. Thus, the left end of the ray can be arbitrarily far from the actual initial tile, or fail to exist at all. While in this case, in a probabilistic setting with a constant probability of choosing the red tile at each step, the full line assembles with probability zero. For a richer TAS $𝒯$, the OnTAS with the same tile set can be completely unable to assemble the same final assemblies as $𝒯$.

Consider an OnTAS ${𝒯}^{\prime }=(T^{\prime },\tau ,f_{\sigma })$, $\tau =2$, with 11 tile types. The tiles are those represented on Figure 1(b).

The proof of the lemma is easy; it features here with all details in order to demonstrate the articulation of the concepts involved, and to serve as a canvas for the proof of the main result. It details the producible assemblies from any single tile, and shows that the tiles that represent the seed of $𝒯$ are always at a known, bounded, distance of the initial tile.

This construction is to be used to seed-first simulate any arbitrary aTAM TAS with a corresponding OnTAS. In it, most tiles belong to modules that self-assemble from any of their tiles. Once a module has self-assembled, the next steps depend on its environment: it acts kind of as a stem cell. If the module is isolated, it grows a pseudo-seed from which a representation of the seed of $𝒯$ self-assembles sequentially. Otherwise, it interacts with its neighbours to form the macrotiles of the actual simulation which starts from the complete seed representation.

The productions of ${𝒪}_{𝒯}$ are made of 2 parts: the seed representation, that assembles before anything else from any tile of $O_T$, and the actual simulation. The tile set $T^{\prime }\subset O_T$ simulates $T$ for the latter part. It assembles modules that cooperate to form the macrotiles. A macrotile is composed of a central brick module (green tiles in the following figures), which represents the tile being simulated, of tenon modules (red and blue tiles in the following figures), which represent the glues, and of mortar modules (yellow tiles in the following figures) that connect the components together and with the neighbouring macrotiles (Figure 3(b)). The assembly of the seed representation follows from the initial tile. That initial tile grows a subassembly of bound size. The tile set $S_{\sigma }\subset O_T$ grows an arm from there (orange tiles in the following figures) then assembles a barrier (cyan tiles in the following figures) around that subassembly and along the border of the macrotiles of the seed representation. That barrier represents the seed, it separates the initial assembly and the rest of the simulation while being the interface between them. When it is complete, some modules bind to it. Those modules can only assemble either from the complete seed representation or from a previous module. Their assembly enables the start of the actual simulation (Figure 4).

All modules carry special $SEED$ glues that allows isolated modules to initiate the nucleation process. These glues serve as an interface with the tiles of $S_{\sigma }$ when they are exposed. After the nucleation, the modules assemble in a sequence so that no $SEED$ glue is ever exposed. Proving that invariant is an important part of the proof of Theorem 8. The rest of the proof consists in the one hand in showing that the simulation itself is correct and that the modules always interact with each other correctly. The macrotiles are designed so that whatever competitions between tiles happen locally, the resulting assembly exposes the right glues. In the other hand, the proof that the nucleation process always has the same outcome relies on showing that in all the possible cases, the initial subassembly fits within the core of $s^{\prime }$.

To derive $T^{\prime }$ from $T$, the first step consists in generating $T_{IO}$. It is a standard process used and described in [1] as well as in [3]. Each glue is marked with a direction, so that the glues of each tile type are either input or output glues. A subset $I\subset \{N,E,S,W\}$ is a set of input directions for a tile type $t\in T$ if the sum of the strength of the glues on the sides of $t$ in $I$ is at least $\tau$, and no proper subset of $I$ is a set of input directions for $t$. Then the tiles of $T_{IO}$ are all tiles $t$ with input glues on their input sides and output glues on their output sides. In particular, if a side of a tile of $T_{IO}$ has an input glue of strength $\tau$, it is its only side with an input glue.

$T^{\prime }$ is a scale-5 version of $T_{IO}$. The idea is to have a single point of cooperation and/or competition on the central tile of each macrotile. The existing adjacent macrotiles grow fuzz towards that point. The tile that attaches there determines which tile is being represented and the rest of the macrotile assembles from it. The macrotile can then grow fuzz itself, on its empty sides with output glues, for new macrotiles to self-assemble.

The precise construction is inspired by the construction used in [3] to simulate the aTAM with thekeeps no memory of the choice of seed. 2HAM. The key takeaway is the use of modules so that a macrotile is able to fully assemble only if its neighbours are themselves sufficiently assembled. A macrotile is made up of 3 types of modules (Figure 2):

• $\mathrm{■}$

  The tenon modules assemble from adjacent macrotiles towards the centre of the macrotile. Symmetrically, they assemble from the core of the macrotile towards the adjacent empty areas. The tile in the centre of the module is called its core tile.

• $\mathrm{■}$

  The central brick module (which corresponds to the brick in [3]) self-assembles from the tile that binds to the input tenons. That tile is called the core tile of both the brick and any macrotile it belongs to.

• $\mathrm{■}$

  The mortar modules bind themselves to the other modules of both the current macrotile and the existing adjacent ones. They allow for the growth of the output tenons on the empty output sides.

Each module can fully self-assemble without external help through strength-$\tau$ glues, but their first tiles depend on other module types. Each brick depends on one orkeeps no memory of the choice of seed. more tenons, each tenon depends on the cooperation of a brick with a mortar module and each mortar module depends on the cooperation of a tenon with either a brick or a mortar module.

During the assembly of a macrotile, the tenons shared with its input neighbors assemble first, then the brick assemble from the centre of the macrotile (Figure 3(a)). On tiles with 4 input glues, no brick binds and the macrotile is complete when all the input tenons self-assembled (see Section 4.1.1). The mortar modules bind both to the mortar modules of the adjacent macrotiles and to the input tenons, with glue pairs of strengths $(\tau -1,1)$ respectively. From there, in clockwise order, an output tenon binds both to the brick and to the previous mortar module with a $(\tau -1,1)$-strengths glue pair, then a mortar module binds both to that tenon and to the brick, and so on until all sides of the macrotile have a tenon, either input or output (Figure 3(b)).

Each module has a single $SEE{D}_i^d$ glue, where $i\in \{b,t,m_l,m_r,m_{long}\}$ is the identifier for the module type ($b$ corresponds to brick modules, etc.) and $d\in \{N,E,S,W\}$ is the direction that the glue is facing. The identifiers of the mortar modules depend on their chirality: $m_l$ is the identifier for mortar modules that goes from the bottom to the left and $m_r$ is the identifier for their counterparts. That way, all modules of each one of the 5 module types (the fifth one is described below in Section 4.1.2) in each one of the 4 possible orientation share a unique $SEED$ glue. The $SEED$ glue is the one that serves as an interface from isolated modules to the tiles used to assemble the representation of the seed, as detailed in Section 4.2. The only exceptions are the brick modules with a strength-$\tau$ input glue. They do not have a $SEED$ glue at all because they can attach to the tenons with the corresponding strength-$\tau$ glue and the latter do have a $SEED$ glue.

The purpose of the tileset $S_{\sigma }$ is to assemble a scaled representation of $\sigma$, ${\sigma }^{\prime }$, as a descendant of any isolated tile of $O_T$, the whole OnTAS tileset.

A first subset $S\subset S_{\sigma }$ does not depend on $𝒯$. Consider any of the module types of the macrotiles in any of the 4 possible orientations (grey tiles on Figure 4). That module may attach to other modules. The resulting assembly has a single $SEED$ glue from which tiles from $S$ self-assemble an arm ${\sigma }_O$ (orange tiles on Figures 4 and 5). ${\sigma }_O$ grows to an edge of the rectangle area that encloses the initial module and any other modules that bind to it, where it places a final tile, $\ast$. The variant of ${\sigma }_O$ that grows from brick modules is designed so that it crashes into any input tenon module attached to the adjacent tile to the $SEED$ glue. That way, ${\sigma }_O$ can only ever grow if the brick module self-assembled by itself and not as a part of a macrotile even when the $SEED$ glue itself is not blocked. Similarly, the long mortar modules grow their ${\sigma }_O$ arm towards their first tiles.

The second subset $T_{\sigma }\subset S_{\sigma }$ actually assembles the representation of $\sigma$. That tileset corresponds to $T_{\sigma }$ in [1]. It takes over ${\sigma }_O$ to continue the assembly of ${\sigma }^{\prime }$ with the same process as described in [1]: it assemble an inner path (blue tiles on Figure 4) that goes through the macrotiles representing $\sigma$. That path continues in an outer path made out of mortar modules and tenons (resp. yellow and blue tiles on Figure 4). The outer path self-assembles along the inner path, on the border of ${\sigma }^{\prime }$. The paths go along the border of $s^{\prime }$ without crossing it and ${\sigma }_O$ self-assembles within that empty space.

The inner path plays the same role as the bricks and tenons regarding ${\sigma }^{\prime }$. It exposes the same glues as “standard” macrotiles would, so that the mortar modules and the output tenons assemble correctly on the outer path. The first module on the outer path binds to both the first and the last tile of the inner path. Then, the outer path assembles so that the structure of the outputs of the macrotiles of the seed representation is the same as for the other macrotiles, detailed in the previous section. Following the first one, each module depends on a previously assembled module (either mortar or tenon) and on the inner path.

The mortar modules on the outer path do not assembles their last few tiles, depending on the angle between the edges of the macrotiles they are part of (Figure 6). Their first tiles expose the glue that are necessary for the simulation to move on and the last ones are blocked by the inner path.

Each tile of the “main” tile set $T^{\prime }$ is part of a unique module to which corresponds a unique ${\sigma }_O$. Each tile of $S_{\sigma }$ corresponds to a unique position in the representation of $\sigma$. Hence $f_{{\sigma }^{\prime }}$ is defined so that the centre of the centres of the macrotiles of ${\sigma }^{\prime }$ are aligned at scale 5 with corresponding tiles of $\sigma$. In particular, the $\ast$ tile is always placed at coordinates $(2,6)$, as in Figure 4.

Now that the producible assemblies are precisely described, the representation function can be easily derived. Formally, the representation function from an OnTAS to the simulated TAS is defined as follows:

• $\mathrm{■}$

  The presence of any tile of $T_{\sigma }$ within an (aligned) $5\times 5$-tiles square area indicates that the macrotile represents the corresponding tile in $\sigma$

• $\mathrm{■}$

  The presence of the core tile of a brick module from $T^{\prime }$ in the centre of an (aligned) $5\times 5$-tiles area indicates that the macrotile represents the corresponding tile of $T$.

• $\mathrm{■}$

  Given a macrotile with four input tenons facing its core, if the combination of glues they represent exists with no mismatch on at least one tile of $T_{IO}$, then the northern tenon indicates which tile of $t$ the macrotile represents.

The following sections show that these conditions cannot interfere with each other.

This section proves that from “correct” macrotiles, only “correct” macrotiles can be assembled and from that the Lemma 14 can be deduced.

Intuitively, that means that from a valid assembly representation of $𝒯$ in ${𝒪}_{𝒯}$, on all empty spots of $a^{\prime }$ where a macrotile can be added that corresponds to a valid tile in $𝒯$ and that eventually exposes the right output glues towards its empty neighbours.

To prove Lemma 15, the idea is to show that there is a finite number of producible subassemblies, that their sizes are bounded and that they always expose a $SEED$ glue.

The statement of Lemma 16 is largely inspired by Theorem 5.1 from [1] and the proof follows roughly the same ideas, with some key differences.