Reflexive Tile Assembly Model (RTAM)

Informal Definition

The Reflexive Tile Assembly Model (RTAM) is essentially equivalent to the abstract Tile Assembly Model (aTAM) [13, 18, 20, 22] but with the modification that tiles are allowed to possibly “flip” across their horizontal and/or vertical axes before attaching to an assembly. Also, as in some formulations of the aTAM, it is assumed that glues bind to complementary versions of themselves (so that two tiles of the same type which are flipped relative to each other can’t simply bind to each other along the same but reflected side).

Formal Definition

We work in the 2-dimensional discrete space \(\mathbb{Z}^2\). Define the set \(U_2 = \{(0, 1), (1, 0), (0, -1), (-1, 0)\}\) to be the set of all \(\emph{unit vectors}\) in \(\mathbb{Z}^2\). We also sometimes refer to these vectors by their cardinal directions \(N, E, S, W\), respectively. All graphs in this paper are undirected. A \(\emph{grid graph}\) is a graph \(G = (V, E)\) in which \(V \subseteq \mathbb{Z}^2\) and every edge \(\{a, b\} \in E\) has the property that \(a-b \in U2\). Intuitively, a tile type \(t\) is a unit square that can be translated and flipped across its vertical and/or horizontal axes, but not rotated. This provides each tile type with a pair of North-South (\(NS\)) sides and a pair of East-West (\(EW\)) sides, such that either side \(s \in NS\) may be facing north while the other is facing south (and vice versa for the \(EW\) glues). For ease of discussion, however, we will talk about tile types as being defined in fixed orientations, but then allow them to attach to assemblies in possibly flipped orientations.

Fix a finite set \(T\) of tile types. Each side of a tile \(t\) in \(T\) has a “glue” with “label”–a string over some fixed alphabet–and “strength” –a nonnegative integer–specified by its type \(t\). Let \(R = \{D, V, H, B\}\) be the set of permissible reflections for a tile which is assumed to begin in the default orientation, where \(D\) corresponds to no change from the default, \(V\) a single vertical flip (i.e. a reflection across the x-axis), \(H\) a single horizontal flip (i.e. a reflection across the y-axis), and \(B\) a single horizontal flip and a single vertical flip. It is important to note that a glue does not have any particular orientation along the edge on which it resides, and so remains unchanged throughout reflections. Glues on adjacent edges of two tiles may bind if and only if they have complementary labels and the same strength. An \(\emph{assembly}\) is a partial function \(\alpha \colon \mathbb{Z}^2 \rightarrow T \times R\) defined on at least one input, with points \(x \in \mathbb{Z}^2\) at which \(\alpha (x)\) is undefined interpreted to be empty space, so that \(\alpha\) is the set of points with \(\emph{oriented}\) tiles.

Two assemblies \(\alpha\) and \(\beta\) are equivalent if and only if one of them can be flipped and translated so that they perfectly match at all locations. Each assembly \(\alpha\) induces a \(\emph{binding graph}\), a grid graph whose vertices are positions occupied by tiles, according to \(\alpha\), with an edge between two vertices if the tiles at those vertices have complementary glues of equal strength. Then, for some \(\tau \in N\), an assembly \(\alpha\) is \(\tau\)-\(\emph{stable}\) if every cut of the binding graph of \(\alpha\) has weight at least \(\tau\) , where the weight of an edge is the strength of the glue it represents. When \(\tau\) is clear from context, we say \(\alpha\) is \(\emph{stable}\). For a tile set \(T\), we let \(p_T \colon T \times R \rightarrow T\) be the projection map onto \(T\) (i.e. \(p_T ((t, r)) = t)\). A \(\emph{configuration}\) given by an assembly \(\alpha\) is defined to be the map from \(\mathbb{Z}^2\) to \(T\) given by \(p_T \circ \alpha\).

Assembly

Self-assembly begins with a \(\emph{seed assembly}\) \(\sigma\), in which each tile has a specified and fixed orientation, and proceeds asynchronously and nondeterministically, with tiles in any valid reflection in \(R\) adsorbing one at a time to the existing assembly in any manner that preserves \(\tau\) -stability at all times. A \(\emph{reflexive tile assembly system}\) (RTAS or just TAS when the context is clear) 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 in which each tile is given a fixed orientation, and \(\tau \in N\) is the \(\emph{temperature}\) of the system which intends to model physical temperature. We use “temperature-\(\tau\) system” to refer to any TAS with temperature \(\tau\) . We write \(\mathcal{A}[\mathcal{T}]\) for the set of all \(\tau\)-stable assemblies that can arise (in finitely many steps or in the limit) in \(\mathcal{T}\) . An assembly \(\alpha \in \mathcal{A}[\mathcal{T}]\) is \(\emph{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}] \subseteq \mathcal{A}[\mathcal{T}]\). We say that \(\mathcal{T}\) is directed if and only if all of the assemblies (upto reflection and translation) of a directed system give the same configuration.

A set \(X \subseteq \mathbb{Z}^2\) \(\emph{weakly self-assembles}\) if there exists a TAS \(\mathcal{T} = (T, \sigma , \tau )\) and a set \(B \subseteq T\) such that for each \(\alpha \in \mathcal{A}_{\Box}[\mathcal{T}]\) there exists a reflection \(r \in R\) and a translation \(v \in \mathbb{Z}^2\) such that for the assembly, \(\alpha^r\) say, corresponding to \(\alpha\) reflected according to \(r\) then translated by \(v\) and \(\alpha_r^{-1} (B) = X\) holds. 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” such as black) on a possibly larger “canvas” of un-colored tiles. Also, a set \(X\) \(\emph{strictly self-assembles}\) if there is a TAS \(\mathcal{T}\) such that for each assembly \(\alpha \in \mathcal{A}_{\Box}[\mathcal{T}]\) there exists a reflection \(r \in R\) and a translation \(v \in \mathbb{Z}^2\) such that \(\alpha_r = F(\alpha , r, v)\) and dom \(\alpha_r = 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.

Results

\(\emph{Definition 1}\). A set \(X \subseteq \mathbb{Z}^2\) is semi-doubly periodic if there exist three vectors \(b\), \(u\), and \(v\) in \(\mathbb{Z}^2\) such that \(X = \{ b + n \cdot u + m \cdot v | n, m \in N \}.\)

\(\emph{Theorem 1}\). Let \(\mathcal{T} = (T, \sigma, 1)\) be a directed RTAM system. If a set \(X \subseteq \mathbb{Z}^2\) weakly self-assembles in \(\mathcal{T}\) , then \(X\) is a finite union of semi-doubly periodic sets.

\(\emph{Theorem 2}\). The RTAM is computationally universal at \(\tau = 2\). Moreover, the class of directed RTAM systems is computationally universal at \(\tau = 2\).

\(\emph{Theorem 3}\). For all \(n \in \mathbb{Z}^+\) where \(n\) is even, there exists no RTAM system \(\mathcal{T} = (T, \sigma , 1)\) where \(|\sigma | = 1\) and \(\mathcal{T}\) weakly (or strictly) self-assembles an \(n \times n\) square.

\(\emph{Theorem 4}\). For all \(n \in \mathbb{Z}^+\) where \(n\) is odd, an \(n \times n\) square strictly self-assembles in an RTAM system \(\mathcal{T} = (T, \sigma , 1)\) where \(|T| = n\) and \(|\sigma | = 1\).

\(\emph{Theorem 5}\). For all \(n \in \mathbb{Z}^+\) where \(n\) is odd, there exists no RTAM system \(\mathcal{T} = (T, \sigma , 1)\) where \(|T| < n\) and \(|\sigma | = 1\) such that \(\mathcal{T}\) weakly (or strictly) self-assembles an \(n \times n\) square.

\(\emph{Theorem 6}\). There exists a finite connected shape \(S\) in \(\mathbb{Z}^2\) that weakly self-assembles in a singly seeded RTAM system such that there exists no singly seeded RTAM system that strictly self-assembles \(S\).

\(\emph{Theorem 7}\). There exists a finite shape \(S\) in \(\mathbb{Z}^2\) that can be strictly self-assembled by some singly seeded RTAM system such that every singly seeded RTAM system at temperature 1 which strictly self-assembles \(S\) is not directed.

\(\emph{Theorem 8}\). There exists a finite shape \(S\) in \(\mathbb{Z}^2\) such that every singly seeded RTAM system that strictly self-assembles \(S\) is not mismatch-free.

\(\emph{Definition 2}\). A tree \(T\) is \(\epsilon\)-symmetric if and only if for any axis \(a\) of \(T\), \(T\) is off-by-one symmetric across \(a\).

\(\emph{Theorem 9}\). Let \(S \subset \mathbb{Z}^2\) be a finite connected shape. There exists a mismatch-free RTAM system \(\mathcal{T} = (T, \sigma , 1)\) with \(|\sigma | = 1\) that strictly assembles \(S\) if and only if \(S\) is \(\epsilon\)-symmetric.

\(\emph{Theorem 10}\). Let \(S \subset \mathbb{Z}^2\) be a finite connected shape, and \(S^2\) be \(S\) at scale factor 2. There exists a mismatch-free RTAM system \(\mathcal{T} = (T, \sigma , 2)\) with \(|\sigma | = 1\) that strictly self-assembles \(S^2\).