Abstract Tile Assembly Model (aTAM)

Informal Description of the Model

The aTAM was developed to, in some sense, be an effectivization of Wang tiling. (See Wang Tiling for more about this relationship.) Namely, it provides a defined process by which an initial (called the seed) assembly can grow into a resultant structure. This is essentially accomplished by assigning a positive integer strength value to each edge color in a set of Wang tiles and stipulating that when two tile edges are adjacent, if their colors match then the edges bind with force equivalent to the strength of the edge color. Then, starting with a preformed seed assembly (usually taken to be a single tile of a specified type), additional tiles can attach one at a time as long as the sum of the strengths of the bonds that each makes with tiles already in the assembly meets a system wide threshold value called the temperature.

Formal Definition of the Model

We now give a brief formal definition of the aTAM. See for other developments of the model. Our notation is that of , which also contains a more complete definition.

Given a set \(T\) of tile types, an assembly is a partial function \({\alpha}:{\mathbb{Z}^2} \dashrightarrow {T}\). An assembly is \(\tau\)-stable if it cannot be broken up into smaller assemblies without breaking bonds of total strength at least \(\tau\), for some \(\tau \in \mathbb{N}\).

Self-assembly begins with a seed assembly \(\sigma\) and proceeds asynchronously and nondeterministically, with tiles adsorbing one at a time to the existing assembly in any manner that preserves \(\tau\)-stability at all times. A tile assembly system (TAS) is an ordered triple \(\mathcal{T} = (T, \sigma, \tau)\), where \(T\) is a finite set of tile types, \(\sigma\) is a seed assembly with finite domain, and \(\tau \in \mathbb{N}\). A generalized tile assembly system (GTAS) is defined similarly, but without the finiteness requirements. We write \(\mathcal{A}[\mathcal{T}]\) for the set of all assemblies that can arise (in finitely many steps or in the limit) from \(\mathcal{T}\). An assembly \(\alpha \in \mathcal{A}[\mathcal{T}]}\) is terminal, and we write \(\alpha \in \mathcal{A}_{\Box}[\mathcal{T}]}\), if no tile can be \(\tau\)-stably added to it. It is clear that \(\mathcal{A}_{\Box}[\mathcal{T}] \subset \mathcal{A}[\mathcal{T}]}\).

An assembly sequence in a TAS \(\mathcal{T}\) is a (finite or infinite) sequence \(\vec{\alpha} = (\alpha_0,\alpha_1,\ldots)\) of assemblies in which each \(\alpha_{i+1}\) is obtained from \(\alpha_i\) by the addition of a single tile. The result \(\res{\vec{\alpha}}\) of such an assembly sequence is its unique limiting assembly. (This is the last assembly in the sequence if the sequence is finite.) The set \({\mathcal{A}[\mathcal{T}]\) is partially ordered by the relation \(\longrightarrow\) defined by

\(\begin{eqnarray*} \alpha \longrightarrow \alpha' & \textmd{iff} & \textmd{there is an assembly sequence } \vec{\alpha} = (\alpha_0,\alpha_1,\ldots) \\& & \textmd{such that } \alpha_0 = \alpha \textmd{ and } \alpha' = \res{\vec{\alpha}}.\\ \end{eqnarray*}\)

We say that \(\mathcal{T}\) is directed if the relation \(\longrightarrow\) is directed, i.e., if for all \(\alpha,\alpha' \in \prodasm{T}\), there exists \(\alpha'' \in \prodasm{T}\) such that \(\alpha \longrightarrow \alpha''\) and \(\alpha' \longrightarrow \alpha''\). It is easy to show that \(\mathcal{T}\) is directed if and only if there is a unique terminal assembly \(\alpha \in \mathcal{A}[\mathcal{T}]\) such that \(\sigma \longrightarrow \alpha\).

In general, even a directed TAS may have a very large (perhaps uncountably infinite) number of different assembly sequences leading to its terminal assembly. This seems to make it very difficult to prove that a TAS is directed. Fortunately, Soloveichik and Winfree have defined a property, local determinism, of assembly sequences and proven the remarkable fact that, if a TAS \(\mathcal{T}\) has any assembly sequence that is locally deterministic, then \(\mathcal{T}\) is directed. Intuitively, an assembly sequence \(\vec{\alpha}\) is locally deterministic if (1) each tile added in \(\vec{\alpha}\) "just barely" binds to the existing assembly (meaning that is does so with a summed strength of bonds equal to exactly \(\tau\)); (2) if a tile of type \(t_0\) at a location \(\vec{m}\) and its immediate "output-neighbors" (i.e. those adjacent tiles which bound after the tile at \(\vec{m}\)) are deleted from the result of \(\vec{\alpha}\), then no tile of type \(t \ne t_0\) can attach itself to the thus-obtained configuration at location \(\vec{m}\); and (3) the result of \(\vec{\alpha}\) is terminal.

A set \(X \in \mathbb{Z}^2\) weakly self-assembles if there exists a TAS \({\mathcal T} = (T, \sigma, \tau)\) and a set \(B \subseteq T\) such that \(\alpha^{-1}(B) = X\) holds for every terminal assembly \(\alpha \in \termasm{T}\). Essentially, weak self-assembly can be thought of as the creation (or ``painting) of a pattern of tiles from \(B\) (usually taken to be a unique ``color) on a possibly larger ``canvas of un-colored tiles.

A set \(X\) strictly self-assembles if there is a TAS \(\mathcal{T}\) for which every assembly \(\alpha \in \mathcal{A}_{\Box}[\mathcal{T}]}\) satisfies \(\dom \alpha = X\). Essentially, strict self-assembly means that tiles are only placed in positions defined by the shape. Note that if \(X\) strictly self-assembles, then \(X\) weakly self-assembles. (Let all tiles be in \(B\).)

An example tile that has glue of strength 0 on the left (W) and bottom (S), glue of color 'a' and strength 2 on the top (N), and glue of color 'b' and strength 1 on the right (E). This tile also has label 'L'..

Tiles are often depicted as squares whose various sides contain 0, 1, or 2 attached black squares, indicating whether the glue strengths on these sides are 0, 1, or 2, respectively. Thus, for example, a tile of the type shown to the right has glue of strength 0 on the left (W) and bottom (S), glue of color `a' and strength 2 on the top (N), and glue of color `b' and strength 1 on the right (E). This tile also has a label `L', which plays no formal role but may aid our understanding and discussion of the construction.

Example: A Binary Counter

The aTAM is capable of Turing universal computation, so our first example will consist of a system which self-assembles a simple computation, namely an infinite binary counter. The figure below shows three tile types which will be used to form the boundary of the counter on its bottom and right sides. The figure below shows the additional \(4\) tile types needed to perform the actual counting and to display, via their labels, the bits of each number. We will define our binary counter tile assembly system as \(\mathcal{T} = \{T,(S,(0,0)), 2\}\), that is, it will consist of tile set \(T\) which will contain all \(7\) of the tile types defined in the figure below, it will have a seed consisting of a single copy of a tile of type \(S\) placed at position \((0,0)\), and it will be a temperature \(2\) system (meaning that free tiles need to bind with at least a single strength-\(2\) glue or two individual strength-\(1\) glues on tiles within an existing assembly in order to attach to that assembly).

The tile types which form the border of the counter

The "rule" tile types which compute and represent the values of the counter

This tile set, seeded with the S tile at τ=2, self-assembles into an infinite binary counter.

The figure below shows a small portion of the infinite assembly produced by \(\mathcal{T}\). In the figure below, the beginning of the formation of the border is shown. Starting from \(S\), border tiles \(R\) can attach and form an infinite column upward using their strength-\(2\) glues, and \(B\) tiles can do the same to the left. No rule tiles can attach until there are \(2\) strength-\(1\) bonds correctly positioned for them to bind to. The figure below also shows the first rule tile which is about to attach into the corner. In the figure below the bottom-right square of width and height \(6\) of the infinite square assembly is shown. Each horizontal row represents a single binary number in the counter, read from left to right (but which will have an infinite number of leading \(0\)'s to the left), and each row represents a binary number exactly one greater than the row immediately beneath it. The computation is performed by the rule tiles which, essentially, receive as "input" a bit from beneath (representing the current value of that column) and a bit from the right (representing the carry bit being brought in from the bit position which is immediately less significant). The labels and the northern glues of the rule tiles simply represent the (possibly new) "output" bit to be represented by that column (based on the two inputs), and the western glue represents the "output" carry bit which results. The computation is possible because of the "cooperation" between two tiles providing input, enforced by the system parameter temperature \(= 2\) and the single-strength glues of the rule tiles.

Border tiles can attach to the seed and form arbitrarily long bottom and right borders. Rule tiles can bind only once two "inputs" are available.

A view of the 6 by 6 square of tiles at the bottom right corner of the assembly produced by the binary counter. Note that the terminal assembly would actually continue infinitely far up and to the left.

Portions of the assembly formed by the binary counter.