Directed Tile Assembly Systems

Overview

Informally, a directed TAS is a TAS that can only produce exactly one terminal assembly. 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.

Definition

Let \(\mathcal{T} = (T, \sigma, \tau)\) be a TAS. The set \(\prodasm}[1]{\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 (a.k.a. deterministic}, confluent, produces a unique assembly}) 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\).

Local Determinism

Soloveichik and Winfree have defined a property, {\it local determinism}, of assembly sequences and proven the remarkable fact that, if a TAS \(\mathcal{T}\) has {\it 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 \({\it 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.