An Axiomatic Study of Leveraging Blockers to Self-Assemble Arbitrary Shapes via Temperature Programming

As mentioned above, previous theoretical results on temperature programming relied on two yet to be demonstrated mechanisms: 1) suppressing interactions of sticky glues off-seed at lower temperatures and 2) using the existence of a tile in the assembly to prevent the binding of another tile.

Recent experimental work [16] has shown that by “poisoning” systems with single glue domain length strands, called blockers, which are complementary to “input” glues, that one can not only “turn off” high strength (that is, very sticky) glues at lower temperatures, but also suppress spurious nucleation (that is, off-lattice interactions that lead to structures not grown from a seed) across all temperatures. This is thought to be due to the binding penalty induced by blockers being multiplicative for pathways that lead to spurious nucleation (which leads to an exponential impact on the spurious nucleation rate) while having a less significant impact on the growth rate of seeded assemblies since the penalty will result in linear slowdown  [5]. Figure 1(a), constructed from data in [15], shows this effect in practice. In the presence of a seed, growth may be slowed, but still proceeds at a reasonable rate (as indicated by the increase in fluorescence in samples with seeds), while spurious nucleation is suppressed to undetectable levels across all temperatures (as indicated by the relatively flat fluorescence trace of unseeded samples). Also, shown in this plot is the deactivation effect blockers have on stickier (that is, high-strength) glues at lower temperatures. It shows the growth rate of tiles consisting of length 10 glues becomes suppressed to undetectable levels at lower temperatures (evidenced by the insignificant increase in the seeded sample containing tiles with length 10 glues at temperatures $41C$ and below) where the growth rate of tiles consisting of length 9 glues is still significant (evidenced by the significant increase in the seeded samples at these temperatures).

The Blocked Tile Assembly Model is inspired by the glue deactivation and spurious nucleation suppression afforded by blockers. But, it still remains in the realm of theory since attempting to implement such system in the laboratory could face technical hurdles such as spurious nucleation due to the oscillation of temperature or strain at the interfaces of tiles with different glue lengths preventing further growth. In [15], temperature programming was physically realized. The authors showed that the key mechanisms required to physically realize temperature programming are attainable, and they used these features to program nanotube length using temperature oscillations. When interpreted through the lens of the Blocked Tile Assembly Model, the construction in [15] is simple. Two sets of tiles which assemble a cross-section of a nanotube were designed: one having length 10 glues (which are the high strength glues) and the other having length 9 glues (which are the low strength glues). These tile sets were designed to form alternating cross-sections of the nanotube. Blockers were added to the input side of the length 10 glues preventing those tiles from attaching at a lower temperature where the length 9 glues are active. On the other hand, the tiles with length 9 glues are unable to attach at warmer temperatures were the length 10 glues are active. The authors leverage the exclusivity of growth temperatures to design a system which requires the temperature to be oscillated in order to grow the next segment of the tube. In this manner, the number of oscillations dictates the length of the nanotube. (See Figure 2 for an example system which illustrates this idea.)

Figure 1(b) presents atomic force microscopy (AFM) data from [15]) which shows a nanotube grown using the temperature programming technique described above. The segments composed of tiles with length 9 glues were marked with a special molecule so that they appear with bright dots on the image. The temperature was oscillated 4 times (that is, it was held a high temperature and then a low temperature and this process was repeated 4 times) so that we would expect to see 8 cross-section segments alternating between being unmarked and marked. Note that this is indeed what we see in the image. We see the seed, the bright tube in the bottom right-hand corner of the image, followed by eight alternating unmarked and marked segments. This provides evidence that the system is working as intended.

We first formally define the Blocked Tile Assembly Model that presents a formalization of the intuitive model used to design the system presented in [15], which is capable of using temperature to program tube length. A natural extension of the work presented in [15] is to examine whether we can leverage the mechanisms used in that paper to use temperature to program not just length, but the shape of the structure. This is akin to the idea of a 3D printer (although we work in 2 dimensions) which uses a universal ink to construct arbitrary structures. That is, can we assemble a target nanostructure purely through temperature fluctuations without the need to design, order, or add new strands?

We answer this question affirmatively through our two main results. The constructions we present rely on the same mechanisms already demonstrated in [15] with two exceptions. Our constructions rely on having three or more tile sets which have disjoint growth temperatures. In other words, our constructions would require something like length 8 glues in addition to length 9 and length 10 glues. Another yet to be experimentally demonstrated mechanism is having mismatches in the glues between neighboring tiles. However, this mechanism has been demonstrated experimentally, albeit unintentionally, with other DNA tile motifs through the occurrence of errors in algorithmic self-assembly [24]. Neither of these technical challenges appear insurmountable which provides us hope that these constructions, or at least somewhat simplified versions of them, may be experimentally feasible.

Our first main result provides a way for a single BlockTAM tile and blocker set, always beginning from the same seed tile, to receive, and then encode, an arbitrary input value into the glues of a row of tiles solely via a sequence of temperature changes. We call this a universal number encoder, and such a system could be combined with an aTAM system designed to perform any algorithmic self-assembly task by first reading that information as its input and then carrying out its algorithmic growth. Dozens of powerful examples of algorithmic self-assembling systems have been theoretically demonstrated, e.g. [18, 20, 2, 10, 14, 11], and one in particular worth mentioning is that of [20] in which such an input sequence could be the information-theoretically optimal encoding of the definition of an arbitrary shape so that the assembly then proceeds to grow into a scaled version of that shape.

This leads naturally to our second main result, which we call a universal shape builder, and is a fixed tile and blocker set such that, given any arbitrary shape $S$, a system that always begins from the same seed tile can be controlled by a temperature sequence taken from the set of temperatures $\{2,3,4\}$ that is specific to $S$ so that the resulting terminal assembly is in the shape of $S$ at a constant scale factor of $6$.

As an input module to the construction of [20], our universal number encoder is also a version of a universal shape builder, and although it is optimal in terms of the number of temperature phases required to build an arbitrary shape, the scale factor of the shape is extremely large.¹¹1The scale factor would depend on the particular shape, but would likely be on the order of at least tens of thousands. However, while our second construction requires a number of temperature phases that is linear in the number of points in the target shape, its scale factor is a mere $6$. In combination, these results provide evidence of the broad powers and potential of the BlockTAM and inspiration for both further theoretical and experimental implementations.

Both results have been fully designed, implemented, and simulated. Python code that can be used to generate example systems for both results (along with pre-existing examples) [13] and a web-based simulator [8] can be accessed from: http://self-assembly.net/wiki/index.php/Blocked_Tile_Assembly_Model_(BlockTAM).

We begin by providing a high-level overview of the aTAM and BlockTAM so that readers familiar with the aTAM may skip the formal definitions section.

The abstract Tile Assembly Model is a tile-based model of self-assembly where growth proceeds from an initial assembly called the seed and proceeds asynchronously and nondeterministically via single-tile attachments. The systems which make up the abstract Tile Assembly Model (aTAM) are called tile assembly systems (TAS) and they are triples $(T,\sigma ,\tau )$ where $T$ is the set of tile types, $\sigma$ is the seed assembly, and $\tau$ is the temperature, or minimum binding threshold, of the system. Growth of the system begins from the seed $\sigma$ and grows via single tile attachments (where the tiles come from the tile set $T$) provided that each tile binds to the assembly with at least a combined strength of $\tau$.

The Blocked Tile Assembly Model (BlockTAM) is an adaptation of the Multiple Temperature Model introduced in  [4]. To formally define this model, we first define a 1 Phase Blocked Tile Assembly Model (1BlockTAM). The BlockTAM can be thought of as consisting of a sequence of 1BlockTAM systems where the resulting terminal assembly of the $i^{\text{th}}$ system is fed into the ${(i+1)}^{\text{th}}$ system as a seed.

A system in the 1 Phase Blocked Tile Assembly Model (1BlockTAM) is a 4-tuple $(T,C,\sigma ,\tau )$ where $T$, $\sigma$ and $\tau$ are defined as in the aTAM, and $C$ is defined to be a set of “blockers”. A blocker is defined as a triple $(t,d,s)$ where $t$ is a tile, $d$ is a direction on the tile, and $s$ is a strength. Growth of the system proceeds as in the aTAM with the exception that any glue which has a blocker whose strength is $\ge \tau$ is treated as a strength 0 glue (to reflect the fact that the glue is “blocked”). We formalize this by constructing an aTAM system from the 1BlockTAM system where any glues that are “blocked” in the system have their strength set to 0 and defining the behavior of the 1BlockTAM system to be the same as the derived aTAM system.

The definitions below are an adaptation of the abstract Tile Assembly Model (aTAM) definition presented in [7]. We note that [18] and [11] are good introductions to the model for unfamiliar readers.

Let $\mathbb{N}$ be the set of nonnegative integers, and for $n\in \mathbb{N}$, let $[n]=\{0,1,\mathrm{\dots },n-2,n-1\}$. Similarly, for $l,u\in \mathbb{Z}$, let .

Fix $\mathrm{\Sigma }$ to be some alphabet with ${\mathrm{\Sigma }}^{\ast }$ its finite strings. A glue $g\in {\mathrm{\Sigma }}^{\ast }\times \mathbb{N}$ consists of a finite string label and non-negative integer strength. A tile type is a tuple $t\in {({\mathrm{\Sigma }}^{\ast }\times \mathbb{N})}^4$, thought of as a unit square with a glue on each side. A tile set is a finite set of tile types. We always assume a finite set of tile types, but allow an infinite number of copies of each tile type to occupy locations in the ${\mathbb{Z}}^2$ lattice, each called a tile.

Given a tile set $T$, a configuration is an arrangement (possibly empty) of tiles in the lattice ${\mathbb{Z}}^2$, i.e. a partial function $\alpha :{\mathbb{Z}}^2⇢T$. Two adjacent tiles in a configuration interact, or are bound or attached, if the glues on their abutting sides are equal (in both label and strength) and have positive strength. Each configuration $\alpha$ induces a binding graph $B_{\alpha }$ whose vertices are those points occupied by tiles, with an edge of weight $s$ between two vertices if the corresponding tiles interact with strength $s$. An assembly is a configuration whose domain (as a graph) is connected and non-empty. The shape $S_{\alpha }\subseteq {\mathbb{Z}}^2$ of assembly $\alpha$ is the domain of $\alpha$. For some $\tau \in {\mathbb{Z}}^{+}$, an assembly $\alpha$ is $\tau$-stable if every cut of $B_{\alpha }$ has weight at least $\tau$, i.e. a $\tau$-stable assembly cannot be split into two pieces without separating bound tiles whose shared glues have cumulative strength $\tau$. Given two assemblies $\alpha ,\beta$, we say $\alpha$ is a subassembly of $\beta$ (denoted $\alpha ⊑\beta$) if $S_{\alpha }\subseteq S_{\beta }$ and for all $p\in S_{\alpha }$, $\alpha (p)=\beta (p)$ (i.e., they have tiles of the same types in all locations of $\alpha$).

A tile-assembly system (TAS) is a triple $𝒯=(T,\sigma ,\tau )$, where $T$ is a tile set, $\sigma$ is a finite $\tau$-stable assembly called the seed assembly, and $\tau \in {\mathbb{Z}}^{+}$ is called the binding threshold (a.k.a. temperature). If the seed $\sigma$ consists of a single tile, i.e. $|\sigma |=1$, we say $𝒯$ is singly-seeded. Given a TAS $𝒯=(T,\sigma ,\tau )$ and two $\tau$-stable assemblies $\alpha$ and $\beta$, we say that $\alpha$ $𝒯$-produces $\beta$ in one step (written $\alpha {\to }_1^{𝒯}\beta$) if $\alpha ⊑\beta$ and $|S_{\beta }\setminus S_{\alpha }|=1$. That is, $\alpha {\to }_1^{𝒯}\beta$ if $\beta$ differs from $\alpha$ by the addition of a single tile. The $𝒯$-frontier is the set ${\partial }^{𝒯}\alpha ={\bigcup }_{\alpha {\to }_1^{𝒯}\beta }{S}_{\beta }\setminus S_{\alpha }$ of locations in which a tile could $\tau$-stably attach to $\alpha$. When $𝒯$ is clear from context we simply refer to these as the frontier locations.

We use ${𝒜}^T$ to denote the set of all assemblies of tiles in tile set $T$. Given a TAS $𝒯=(T,\sigma ,\tau )$, a sequence of $k\in {\mathbb{Z}}^{+}\cup \{\mathrm{\infty }\}$ assemblies ${\alpha }_0,{\alpha }_1,\mathrm{\dots }$ over ${𝒜}^T$ is called a $𝒯$-assembly sequence if, for all , ${\alpha }_{i-1}{\to }_1^{𝒯}{\alpha }_i$. The result $lim\alpha$ of an assembly sequence $\alpha$ is the unique limiting assembly of the sequence. For finite assembly sequences, this is the final assembly; whereas for infinite assembly sequences, this is the assembly consisting of all tiles from any assembly in the sequence. We say that $\alpha$ $𝒯$-produces $\beta$ (denoted $\alpha {\to }^{𝒯}\beta$) if there is a $𝒯$-assembly sequence starting with $\alpha$ whose result is $\beta$. We say $\alpha$ is $𝒯$-producible if $\sigma {\to }^{𝒯}\alpha$ and write $𝒜[𝒯]$ to denote the set of $𝒯$-producible assemblies. We say $\alpha$ is $𝒯$-terminal if $\alpha$ is $\tau$-stable and there exists no assembly that is $𝒯$-producible from $\alpha$. We denote the set of $𝒯$-producible and $𝒯$-terminal assemblies by ${𝒜}_{\mathrm{\square }}[𝒯]$. If $|{𝒜}_{\mathrm{\square }}[𝒯]|=1$, i.e., there is exactly one terminal assembly, we say that $𝒯$ is directed. When $𝒯$ is clear from context, we may omit $𝒯$ from notation.

Assembly in the BlockTAM proceeds through a series of temperature phases, each of which consists of a hold at a specified temperature during which growth proceeds until all assemblies are terminal. Once all assemblies are terminal, the temperature of the system is set to the next temperature in a specified series and remains there until all growth is again terminal. This process continues until all growth is terminal during the last temperature phase. Note that a temperature sequence must be finite and that infinite growth (in the limit) during a phase is only allowed during the final phase.

Although the BlockTAM shares similarities with other tile-assembly models that allow for temperature variations (e.g. [1, 21]), additional complexity arises from the fact that, at different temperatures, different subsets of the blockers in a system may be actively blocking glues. Therefore, to ease explanation of the BlockTAM, here we first define its dynamics during a single phase, then in Section 2.4 define the full model in terms of phases.

In order to easily translate between a tile and its blocked version, we assume all distinct glues have distinct labels. That is, there are not two glues with the same labels, but different strengths. This is a simple transformation that can be obtained by relabeling each glue so that the new label is a concatenation of the glue’s original label along with its strength.

A blocker is defined as a triple $(t,d,s)$ where $t$ is a tile, $d$ is a direction on the tile, and $s$ is a strength. We say that a blocker $c=(t,d,s)$ binds to tile $t$ on its $d$ edge with strength $s$. Let $t$ be a tile, $C$ be a set of blockers, and $\tau$ be a temperature, then we define the tile $t$ blocked at temperature $\tau$ by blocker set $C$, denoted $\text{blocked}(t,C,\tau )$ to be the tile with the same glues as $t$ unless there is a blocker which binds at the location of the glue on the tile with strength greater than or equal to $\tau$. Note that when $C$ and $\tau$ are obvious from context, we simply write $\text{blocked}(t)$. Also, since we define an assembly to map points to tiles we can compose this function with an assembly to obtain a function which maps each point to a blocked version of the tile. We define the function unblocked to be the inverse of the blocked function. That is, $\text{unblocked}(\text{blocked}(t,C,\tau ))=t$. The function blocked is invertible due to our assumption distinct glues have distinct labels.

A 1-Phase BlockTAM system (1BlockTAS) is a 4-tuple $ℬ=(T,C,\sigma ,\tau )$ where $T$ is a tile set, $C$ is a blocker set, $\sigma$ is the seed assembly, and $\tau$ is the temperature. We define the equivalent TAS of $ℬ$, denoted $\text{TEQ}(ℬ)$, to be the aTAM system $𝒯=(T^{\prime },\text{blocked}(\sigma ),\tau )$ where $T^{\prime }$ consists of a modified version of $T$ such that any glue whose blocker binds with strength $\ge \tau$ is set to have strength $0$. That is $T^{\prime }=\{\text{blocked}(t,C,\tau )|t\in T\}$. Given a 1BlockTAS $ℬ=(T,C,\sigma ,\tau )$ and two $\tau$-stable assemblies $\alpha$ and $\beta$ formed from tiles in $T$, we say that $\alpha$ $ℬ$-produces $\beta$ in one step, written $\alpha {\to }_1^{ℬ}\beta$, if $\text{blocked}(\alpha ){\to }_1^{\text{TEQ}(ℬ)}\text{blocked}(\beta )$. The $ℬ$-frontier is the set ${\partial }^{\text{TEQ}(ℬ)}(\text{blocked}(\alpha ))$.

Given a 1BlockTAS $ℬ=(T,C,\sigma ,\tau )$, a sequence of $k\in {\mathbb{Z}}^{+}\cup \{\mathrm{\infty }\}$ assemblies ${\alpha }_0,{\alpha }_1,\mathrm{\dots }$ over ${𝒜}^T$ is called a $ℬ$ assembly sequence if $\text{blocked}({\alpha }_0),\text{blocked}({\alpha }_1),\mathrm{\dots }$ is a $\text{TEQ}(ℬ)$-assembly sequence. We say that $\alpha$ $ℬ$-produces $\beta$ denoted $\alpha {\to }^{ℬ}\beta$ if $\text{blocked}(\alpha ){\to }^{\text{TEQ}(ℬ)}\text{blocked}(\beta )$. We say that $\alpha$ is $ℬ$-producible if $\sigma {\to }^{ℬ}\alpha$ and write $𝒜[ℬ]$ to denote the set of $ℬ$-producible assemblies. We $\alpha$ is $ℬ$-terminal if $\text{blocked}(\alpha )$ is $\text{TEQ}(ℬ)$-terminal. We denote the set of $ℬ$-producible and $ℬ$-terminal assemblies by ${𝒜}_{\mathrm{\square }}[ℬ]$. We say that $ℬ$ is directed provided that $\text{TEQ}(ℬ)$ is directed.

The following formal definitions are an adaptation of those used to define the Multiple Temperature Model in [21].

A BlockTAM system (BlockTAS) is a 4-tuple ${ℬ}^{\ast }=(T,C,\sigma ,{⟨\tau ⟩}_{i=0}^{k-1})$ where $T$ is a tile set, $C$ is a blocker set, $\sigma$ is the seed assembly, and ${⟨\tau ⟩}_{i=0}^{k-1}$ is a sequence of non-negative binding thresholds. The number $k$ is the temperature complexity.

We define an assembly sequence for the $i^{\text{<em class="ltx\_emph" style="font-size:70\%;">th</em>}}$ temperature phase, for , of ${ℬ}^{\ast }$ as follows. For $i=0$, an assembly sequence is an assembly sequence $\overrightarrow{\alpha }$ of the 1BlockTAS ${ℬ}_0=(T,C,\sigma ,{\tau }_0)$. For $i>0$, an assembly sequence for temperature phase $i$ of ${ℬ}^{\ast }$ is a sequence of assemblies $\overrightarrow{\alpha }=({\alpha }_0,{\alpha }_1,\mathrm{\dots })$ satisfying the following conditions.

1. 1.

   There exists $l$ such that ${\alpha }_l$ is ${\tau }_{i-1}$-stable  ${\partial }^{{ℬ}_{i-1}}{\alpha }_l=\mathrm{\varnothing }$, and $({\alpha }_0,{\alpha }_1,\mathrm{\dots },{\alpha }_l)$ is an assembly sequence for temperature phase $i-1$ of ${ℬ}^{\ast }$; and

2. 2.

   for all $j>l$, either ${\alpha }_{j-1}{\to }_1^{{ℬ}_i}{\alpha }_j$ or ${\alpha }_j$ is obtained from ${\alpha }_{j-1}$ by deleting the portion of ${\alpha }_{j-1}$ which does not contain the seed across a cut having strength less than ${\tau }_i$.

Intuitively, an assembly sequence for the $i^{th}$ temperature phase is defined recursively. That is, we say that $({\alpha }_0,{\alpha }_1,\mathrm{\dots })$ is an assembly sequence for the $i^{th}$ temperature phase provided that (1) if $i=0$, then $({\alpha }_0,{\alpha }_1,\mathrm{\dots })$ is an assembly sequence of the 1BlockTAS $(T,C,\sigma ,{\tau }_0)$ and (2) if $i>0$, then two conditions must be met. The first condition says that there exists $l$ such that the sequence can be broken up at $l$ so that the sequence up to index $l$ is an assembly sequence for the ${(i-1)}^{th}$ temperature phase. Condition 2 says that the sequence after index $l$ is a sequence of assemblies such that ${\alpha }_j$ can be obtained from ${\alpha }_{j-1}$ by either (1) a single tile addition (with combined binding strength of at least ${\tau }_i$) or (2) by “melting off” a subassembly from ${\alpha }_{j-1}$ with a cut of strength .

An assembly sequence in ${ℬ}^{\ast }$ is an assembly sequence for the $i^{\text{th}}$ temperature phase of ${ℬ}^{\ast }$ for some $i\in \mathbb{N}$. We say that an assembly sequence $\overrightarrow{\alpha }$ in ${ℬ}^{\ast }$ finishes every temperature phase of ${ℬ}^{\ast }$ if $\overrightarrow{\alpha }$ is a finite assembly sequence for temperature stage $k-1$ of ${ℬ}^{\ast }$ and its final assembly, denoted $\alpha$, is ${\tau }_{k-1}$-stable and ${\partial }^{{\beta }_{k-1}}\alpha =\mathrm{\varnothing }$. In this case, we call $\alpha$ a terminal assembly and write $\alpha \in {𝒜}_{\mathrm{\square }}[{ℬ}^{\ast }]$. If $|{𝒜}_{\mathrm{\square }}[{ℬ}^{\ast }]|=1$, then we say that ${ℬ}^{\ast }$ is directed. Given system ${ℬ}^{\ast }$, let ${\tau }_{max}=\text{max}({\tau }_0,\mathrm{\dots },{\tau }_{k-1})$ (i.e. the maximum $\tau$ value of any stage). We say that ${ℬ}^{\ast }$ is ${\tau }_{max}$-robust if every terminal assembly of every temperature phase is ${\tau }_{max}$-stable. In a ${\tau }_{max}$-robust system, no temperature change causes any portions of any assemblies to dissociate and thus growth is monotone. All constructions in this paper are ${\tau }_{max}$-robust.

If for every $\alpha \in {𝒜}_{\mathrm{\square }}[{ℬ}^{\ast }]$, $\mathrm{dom}\alpha =S$, then we say that ${ℬ}^{\ast }$ self-assembles the shape $S$. Given $S$, a connected set of points in ${\mathbb{Z}}^2$, we define a version of $S$ scaled by factor $c$, and denote it by $c\cdot S$, as $c\cdot S=\{(x,y)\in {\mathbb{Z}}^2\mid (\lfloor \frac{x}{c}\rfloor ,\lfloor \frac{y}{c}\rfloor )\in X\}$. If for every $\alpha \in {𝒜}_{\mathrm{\square }}[{ℬ}^{\ast }]$, there exists $c\in \mathbb{N}$ such that $\mathrm{dom}\alpha =c\dot{S}$, then we say that ${ℬ}^{\ast }$ self-assembles the shape $S$ at scale factor $c$. Note that the Blocked Tile Assembly Model is defined so that a “blocked glue” on a tile which binds into the assembly immediately binds to any neighboring glue.

We now provide a simple example of a BlockTAM system to familiarize the reader with key ideas and notation regarding the model. This example is inspired by the system designed in [15]. Part (a) of Figure 2 shows a BlockTAS $ℬ$. In this example, we assume that all blockers bind with the same strength as the glue. If a temperature $4$ TAS $𝒯$ was defined to have the same tile set and seed as $ℬ$, the assembly shown in part (b) of Figure 2 would be an element of $𝒜[𝒯]$ (that is, the assembly is producible by $𝒯$). Parts (c) and (d) Figure 2 shows the equivalent blocked tile assembly systems for each temperature phase of $ℬ$ and the terminal assembly for each. Note that in part (c), the shown producible assembly of $\mathrm{TEQ}({ℬ}_0)$ is terminal since the blue tile lacks the strength required to attach. In part (d), the shown assembly is terminal in the context of $\mathrm{TEQ}({ℬ}_1)$ since the red tile is blocked (meaning it has strength $0$) and is consequently unable to attach.

As mentioned, the input is a set of temperatures, $\mathrm{\Gamma }$. The construction requires at least three distinct allowable temperature values since having only two possible temperatures in a BlockTAM system does not allow any way to create series of temperature sequences that are distinct from each other for different values to encode without using unary encoding, which is infeasible for all but the very smallest values.

Let $k=|\mathrm{\Gamma }|$ be the number of temperatures, and let $({\tau }_1,{\tau }_2,\mathrm{\dots },{\tau }_k)$ be $\mathrm{\Gamma }$ sorted from lowest to highest. For clarity, we will often use ${\tau }_{max}$ to refer to ${\tau }_k$. The tile set that we are creating will be specific to the values of $\mathrm{\Gamma }$, but will be able to build assemblies representing arbitrary values of $n\in \mathbb{N}$. Each such $n$ will be encoded in some base $b$, which is determined as follows: if $k=3$ then $b=2$, otherwise $b=k-2$. Let $n\in \mathbb{N}$ be an arbitrary number to eventually be encoded. In general, encoding $n$ in base $b$ requires $\lceil {\log }_{b}n\rceil$ values. However, if $k==3$ it will be necessary to represent each bit of the base $2$ representation of $n$ using $2$ bits (for reasons to be explained later). Therefore, let $v$ represent the number of values needed to represent the encoding of a given value $n$ in base $b$.

The target assembly will consist of $c=v+1$ columns. The glue exposed on the north of the top tile of the first column will be a special “start” glue, and the northern glue of each of the following $c-1$ columns will encode subsequent values of the encoding of $n$. The north-south glues binding the tiles of a column will all be of strength equal to ${\tau }_{max}$ so that each column is $\tau$-stable across all temperatures of the system. However, the glues that bind each column to another will consist of varying strengths from $⟨\tau ⟩$. Therefore, when glues of any strength are used, it will be necessary for multiple glues of that strength to bind the columns together to ensure stability if/when the system temperature is set to ${\tau }_{max}$.

Let $h$ be the height of a column (with the determination of the value $h$ to be explained later). We refer to the bottom location of a column as $r_0$ and the one above that as $r_1$, continuing up to the topmost at $r_{h-1}$. Across all columns, the row at each location $r_i$ for is dedicated to tiles whose east/west glues are of the same strength, which we’ll refer to as $s_i$. Furthermore, the binding of any pair of columns to each other will be via one or more glues all of the same strength. To compute $h$ we first determine how many instances of each temperature in $\mathrm{\Gamma }$ are required to sum to the smallest value $\ge {\tau }_{max}$. We then take the sum of that sum to be $h$. For example, if the set of possible temperatures is $\{2,3,4,5\}$, $h=3+2+2+1=8$ since it takes $3$ glues of strength $2$ to sum to $\ge {\tau }_{max}=5$, $2$ each of strength $3$ and $4$, and of course only $1$ of strength $5$. Thus, every column in a system using those temperature values would be of height $h=8$. (See Figures 3 and 4 for examples.)

With the value $h$ as the necessary height of each column, we then compute the assignment of each $s_i$, that is, which east/west strengths are assigned to each row $r_i$. Since these are the glues that bind neighboring columns to each other, we try to assign them to maximize stability. Therefore, we assign the center location to the strongest glue, $s_{max}$. Then, since each weaker glue requires two or more locations (so that the multiple copies of each can sum to $\ge {\tau }_{max}$), we assign them moving outward from the center, alternating up and down for each subsequently weaker glue until all positions are assigned. Examples can be seen in Figures 3 and 4. For instance, Figure 3 shows how the strengths $2,3,4,$ and $5$ are assigned, with the ordering from bottom to top being $2,3,4,5,4,3,2,2$.

Since the north/south glues between the tiles of each column are of strength $s_{max}$, and now we know the strengths of the east/west glues for the tiles at each height, we can determine how to create the columns necessary to represent the values of the numbers to be encoded. Note that a seemingly straightforward method would be to create one unique column for each value that needs to be represented to the north. However, then it is not possible for the encoding to contain the same symbol in two consecutive positions (e.g. the binary representation of ${14}_{10}={1110}_2$, which has two pairs of consecutive $1$s) since then the same column would have to be able to connect to a copy of itself, which would result in “pumping” into an infinite sequence of $1$s. A relatively simple fix to that problem would be to have a column that doesn’t represent any value that could then be located between each value-encoding column. However, this would double the number of temperature phases needed, and that is the primary metric that we are trying to minimize. Therefore, we use the following scheme which compresses the temperature sequence at the expense of requiring slightly more unique tile types (approximately double).

Our method of creating columns for encoded values works by permuting over all pairs of (non-identical) temperatures from $\mathrm{\Gamma }$. Let $t=|\mathrm{\Gamma }|$ be the number of unique temperatures. For each ${\tau }_i\in \mathrm{\Gamma }$, there are $t-1$ temperatures ${\tau }_j\in \mathrm{\Gamma }$ such that $t_i\ne t_j$. For each such pair we create exactly one unique column and we assign a value for that column to encode from the set . (Note that, in the case where $t=3$, no “$X$” character is explicitly used but instead the ending condition is encoded using a special sequence of bits, to be discussed in Section 3.2.) This mapping from each pair of temperatures to an encoded value is referred to as the column_transition_map (and the code used to generate it can be seen in Listing 1 in the Appendix). The resulting map ensures that any encoded symbol can follow any other, except for the “$X$” symbol which is the final symbol to be encoded by the last temperature phase. (Again, when $t==3$, there is no “$X$” symbol, just $0$s and $1$s, which will each be able to follow each symbol.) Note that the column that contains the seed tile is unique, composed of tiles that only appear in that column, and its northernmost glue encodes the start value “$S$”. The glue encoding “$S$” is of strength 2, and all other value encoding glues are of strength 1. Once the number encoding assembly is terminal, the system temperature can be set to 2, allowing for a standard aTAM tile set to attach and grow across from left to right, reading the encoded value then proceeding with arbitrary algorithmic behavior.

To generate the tile type for each location of each column, we use the previously computed glue strengths for each side of each location $r_i$ and the information in the column_transition_map. For each temperature pair $(t_i,t_j)$, again where $t_i\ne t_j$, we generate a set of $h$ distinct tile types to create a unique column. The purpose of the $(t_i,t_j)$ column is to (1) encode the value column_transition_map$(t_i,t_j)$ in the north glue of its northernmost tile, (2) to have its growth initiated by a temperature phase of temperature $t_2$, and (3) to grow immediately to the right of a column whose growth was initiated by a temperature phase of temperature $t_1$. To effect this, each north/south glue label between two tiles of a column are specific to the column type, i.e. $(t_i,t_j)$, and location $r_i$, e.g. $t_i\mathrm{\_}{t}_j,r_k$ for the glue pair between the $k$th and $k+1$th tile in the column for $(t_i,t_j)$. On the east, output side of the tile in location $r_k$ is a glue of strength $s_k$ (which is the strength value assigned to that row) for all locations except that for which $s_k==t_j$, which has no east-facing glue. As previously mentioned, this is to prevent the column from being able to initiate growth of another column to its right at the same temperature at which it grew. The label of each such glue will be $t_j\mathrm{\_}{s}_k,k$, so that it can bind to a tile in the $k$th location of the column for temperature sequence $(t_j,s_k)$ (assuming that the next phase is at temperature $s_k$). Figure 4 shows an example of these glues.

In this way, the full tile set is constructed. Next, the blocker set is created. This simply consists of a blocker for every west-facing glue that is strength $s-1$ if the glue’s strength is $s$. This ensures that those “input” glues, which initiate the growth of each new column, are only active during phases of the temperatures for which their columns were designed, and growth proceeds with a single column forming for each phase.

With the designated seed tile being a tile of the type designed for the middle of the leftmost column, the resulting tile set, blocker set, and seed is a universal number encoder for $\mathrm{\Gamma }$. We next describe how to, given a specific value of $n$ to encode, compute the temperature sequence necessary for a BlockTAS to assemble an assembly encoding $n$.

The input to this portion of the construction is a number $n\in \mathbb{N}$ and a universal number encoder from the previous portion. From that encoder, we can determine the base $b$ in which to encode $n$. Additionally, we can know which of two paths to take to compute the encoding $e$ of $n$: If the number of temperatures, $t$, is $3$, then $e$ will consist of a “doubled” base $2$ encoding, otherwise $e$ will simply be the encoding of $n$ in base $b$ (which is set to $t-2$), with the character “$X$” appended to the end. Note that in either case, the encoding will begin with the “$S$” symbol which is encoded by the column with the seed tile.

To compute the doubled encoding for the case of $t==3$, we note that with only three temperatures to select from, once a given phase of assembly completes, which is necessarily at some $t_i\in \mathrm{\Gamma }$, then there are only two choices for some other $t_j\in \mathrm{\Gamma }$ such that $t_i\ne t_j$. Because of this, we can’t directly encode a symbol to mark the end of sequence, which makes it difficult or impossible for an algorithmic (aTAM-style) tile set to then read the encoded value and effectively use it as input that controls its algorithmic behavior. (It would either have to pause at the end of the assembly “waiting” for a stop symbol, or instead be able to grow on its own past the last symbol without cooperating with the assembly which means that at other points of growth it could “ignore” the assembly and grow without cooperation, yielding an invalid input. This is a well-known problem in the domain of tile-based self-assembly.) Therefore, we utilize the method of representing each bit of the binary encoding of $n$ as follows. We represent each $0$ by $00$, and each $1$ by a $01$. We build our encoding in this way, and to indicate the end of the sequence, after all bits have been encoded this way, we append two consecutive $1$s. In this way, a tile set growing over the north of the terminal assembly and reading the encoding will be able to detect when it has read the final position.

Now with the encoded string $e_0,e_1,\mathrm{\dots },e_v$, we convert that into a series of temperatures over $\mathrm{\Gamma }$. Because there are no blockers for tiles in the column containing the seed, that column grows at any temperature in $\mathrm{\Gamma }$, as all north/south glues are of strength ${\tau }_{max}$. This means that no separate temperature phase is necessary to account for the placement of the “$S$” symbol and the first temperature phase is used to grow the column of the first encoded value of $n$. Additionally, the east-facing, output glues of the seed column use the same labels as a column that grew at the second highest temperature so that new glues do not need to be designed for tiles to attach to that column. Thus, for the first, and then each subsequent, encoded value we simply iterate over the values $e_0,e_1,\mathrm{\dots },e_v$ and examine the column_transition_map keeping track of which temperature $t_i$ was used to grow the previous column (pretending it was the second largest temperature if that was the seed column). For each $e_m$, We find the unique $t_j$ such that column_transition_map$(t_i,t_j)=e_m$. We then append that $t_J$ as the next temperature in the sequence. Iterating through the full encoded string, the resulting temperature sequence is the exact sequence that will cause the universal number encoder to build an assembly of columns expressing the encoded value of $n$ in its northern glues. (For details of a few examples of systems, please see Section A.1 of the Appendix.)

In [21] it was shown how, beginning with an arbitrary input shape $S$, $S$ can be scaled by a factor of two to $S^2$, and then a Hamiltonian path through $S^2$ can be created that visits each point in $S^2$ exactly once. (Note that any shape $S$ that already has a Hamiltonian path through it does not require the scaling by two, but we’ll assume that, in the worst case for an arbitrary $S$, the scaling is required.) Using the technique of [21] we can convert that path into a series of “turtle graphics” instructions. That is, starting on the first point of the path, we simply follow a series of instructions taken from the set $\{\text{Straight},\text{Right},\text{Left}\}$ (which we’ll abbreviate as $\{S,R,L\}$) to visit every point on the path (and thus in $S^2$) exactly once. Let $p=|S|$ be the number of locations, or pixels, in the original shape $S$. The output of this step is an ordered list $L\in {\{S,R,L\}}^{4p-1}$, that is, a list of $4p-1$ directions that allow one to begin at one point in $S^2$ and visit every other (since each pixel in $S$ is composed of 4 in $S^2$, and we don’t need an instruction to get to the pixel from which the path begins).

We now describe the tile set and blockers of the universal shape builder by explaining how they are able to follow such a path. The assembly that follows $L$ is composed of macrotiles that are $3\times 3$ squares of tiles. That is, each pixel of $S^2$ is represented by a $3\times 3$ square of tiles (yielding an overall scale factor of $6$ from $S$). Starting from the seed tile and with a temperature phase of $\tau =4$, the first macrotile grows the base portion of a macrotile, which is composed of 3 tiles (that can be seen as green in the macrotiles in Figure 5). The macrotile then becomes terminal, until the next temperature phase begins. A phase of 3 causes the blue tiles to become unblocked and attach, finishing the macrotile and orienting the output glue toward the left. A phase of 2 causes the blue and pink tiles to be blocked but allows the yellow tiles to attach, after which the macrotile becomes terminal. Then, a next temperature phase of $\tau =4$ allows the orange tiles to become unblocked and attach, exposing the macrotile’s output glue straight ahead. A phase of $\tau =3$ would instead cause the orange tiles to be blocked and the pink tiles to be unblocked and thus attach. They expose a right-facing output glue for the macrotile. Refer to Figure 5 to see that all portions of macrotile growth are fully stabilized before the temperature can increase.

The result of the temperature phases described are that the macrotile completes, is fully stable at all temperatures (at the end of each intermediate temperature phase and the final), and exposes exactly one output glue of strength 4 that can initiate the growth of the next macrotile. While growth of the next macrotile begins with a temperature phase of $\tau =4$, note that in the case of the direction being $S$, the final phase of growth of the current macrotile is also at $\tau =4$. In this case, the base portion of the next macrotile forms during the same phase that the current macrotile completes. This is not a problem and is easily accounted for when designing our temperature sequence.

The final, and relatively straightforward, aspect of the construction is necessary to handle growth of macrotiles following one or more $R$ or $L$ turns. For each clockwise rotation of $90,180,$ and $270$ degrees, we simply create a new copy of each tile making up any of the three versions of the macrotile. We give each copy new glue labels that are specific for that rotation, with the only glue labels that are shared between tiles intended for different rotations being the four glues on the exteriors. These glue labels are designed so that each macrotile output glue is specific to the input glue (i.e. the glue exposed by the green tile) of the correctly oriented version. Since the output locations for $R$ and $L$ turns are not symmetrically located on the macrotile exterior, it is also necessary to make a reflected version of the basic macrotile, and copies of that for each of the rotations. (An example of the full set of rotations and reflections can be seen in Figure 7 in the Appendix.) We use an additional glue prefix of “$x$” for all of the labels of glues on tiles of the reflected copies so that tiles intended for a macrotile of one rotation and/or reflection are not able to bind inside of macrotiles with different rotations and/or reflections, but again we make sure that each rotated and/or reflected macrotile’s output glue labels correctly match those of the properly rotated and/or reflected macrotile input glues to match their output directions (relative to their orientations). (A complete simple example can be seen in Figure 8 of the Appendix.)

From the above description, it is clear that the universal shape builder can correctly follow an arbitrary turtle graphics path. Thus, all that remains is to show how a shape’s path can be turned into a proper temperature sequence. This is also quite trivial, as we have already seen which temperature sequences are necessary for each movement of $S,R,$ or $L$. Since we require that every step is either $S,R$, or $L$, if the path through $S^2$ starts with a backward step we simply rotate the shape so that the first step is $S,R$, or $L$, which doesn’t change the shape since shapes are invariant up to rotation. The first temperature is $4$, allowing the base of the first macrotile to grow. Then, for $L$ a $3$ is appended; for $S$, a $2$ and $4$ are appended; and for R $2$ and $3$. To initiate the next macrotile, if the last direction was $L$ or $R$, we append $4$, but if it was $S$ we don’t need to do that. The final main consideration is for handling reflected macrotiles. We keep track of each turn that uses the $L$ version of the macrotile, as that causes a flip between reflected and non-reflected versions, and note that, when in a reflected macrotile it is an $R$ turn that uses the blue $L$ tiles and flips the reflection status. Finally, to make sure that the final macrotile is complete, after a $\tau =4$ phase to grow its base, we include a $\tau =3$ phase to cause it to complete. (The code used to compute the temperature sequence can be seen in Listing 2 in the Appendix.) We’ve made software freely available that allows one to draw a path, save it as a BlockTAM system [13], then simulate it in a web-based simulator [8]. (Figure 9 of the Appendix shows a screenshot.)

Thus, we have demonstrated a universal shape builder. While only requiring 145 tile types and 32 blockers, it requires an average of just over 2 temperature phases per pixel of $S^2$ (or $S$ if scaling isn’t required). While infeasible for experimental implementations of large shapes, the design techniques may provide tools useful for other and improved constructions.