Polygonal Tile Assembly Model (Polygonal TAM)

In this section we define the Polygonal Tile Assembly Model (polygonal TAM) and relevant terminology.

Polygonal Tiles

A \(\emph{simple polygon}\) is a plane geometric figure consisting of straight, non-intersecting line segments or sides that are joined pair-wise to form a closed path. As is commonly the case, we omit the qualifier simple and refer to simple polygons as polygons. A polygon encloses a region called its \(\emph{interior}\). The line segments that make-up a polygon meet only at their endpoints. Exactly two edges meet at each vertex. We define the set of \(\emph{edges}\) of a polygon to be the line segments that make-up a polygon. In our definition we find it useful to give a polygon a default position and rotation. First, we assume that the centroid, \(c\) say, of any polygon is at the origin in \(\mathbb{R}^2\). Then, for a polygon \(P_n\) with \(n\) edges, let \(v=(x,y)\in \mathbb{R}^2\) be some vertex of \(P_n\) such that \(v\neq c\). By possibly rotating \(P_n\) about \(c\), we can ensure that \(y = 0\) and \(x>0\). For a given polygon \(P\) and some vertex \(v\) of \(P\) that is not equal to the centroid of \(P\), we call this position and rotation the \(\emph{standard position}\) for \(P\) given \(v\).

A \(\emph{polygonal tile}\) is a polygon with a subset of its edges labeled from some {\(\em glue\)} alphabet \(\Sigma\), with each glue having an integer \(\emph{strength}\) value. Two tiles are said to be \(\emph{adjacent}\) if they are placed so that two edges, one on each tile, intersect completely. Two tiles are said to \(\emph{bind}\) when they are placed so that they have non-overlapping interiors and have adjacent edges with complementary glues and matching lengths; each complementary glue pair binds with force equal to its strength value. Note that tiles are not necessarily convex which means that two tiles could bind along more than one edge. An \(\emph{assembly}\) is any connected set of polygons whose interiors do not overlap such that every tile is adjacent to some other tile. Given a positive integer \(\tau \in \mathbb{N}\), an assembly is said to be \(\tau\)-\(\emph{stable}\) or (just \(\emph{stable}\) if \(\tau\) is clear from context), if any partition of the assembly into two non-empty groups (without cutting individual polygons) must separate bound glues whose strengths sum to \(\ge \tau\). We say a tile is in \emph{standard position} if the underlying polygon defining its shape is in standard position. We also refer to the centroid of a polygonal tile as the centroid of the underlying polygon defining the shape of the tile.

Tile System

A \(\emph{tile assembly system}\) (TAS) is an ordered triple \(\mathcal{T} = (T,\sigma,\tau)\) where \(T\) is a set of polygonal tiles, and \(\sigma\) is a \(\tau\)-stable assembly called the \(\emph{seed}\). \(\tau\) is the \(\emph{temperature}\) of the system, specifying the minimum binding strength necessary for a tile to attach to an assembly. Throughout this paper, the temperature of all systems is assumed to be \(1\), and we therefore frequently omit the temperature from the definition of a system (i.e. \(\mathcal{T} = (T,\sigma)\)). If the tiles in \(T\) all have the same polygonal shape, \(\mathcal{T}\) is said to be a \(\emph{single-shape}\) system; more generally \(\mathcal{T}\) is said to be a \(c\)-shape system if there are \(c\) distinct shapes in \(T\). If not stated otherwise, systems described in this paper should by default be assumed to be single-shape systems.

We define a \(\emph{configuration}\) of \(\mathcal{T}\) to be a (possibly empty) arrangement of tiles in \(\mathbb{R}^2\) where tiles of this arrangement are translations and/or rotations of copies of tiles in \(T\). Formally, we define a configuration of \(\mathcal{T}\) as follows. For a \(c\)-shaped system \(\mathcal{T} = (T,\sigma,\tau)\), let \(P_1\), \(P_2\), \(\dots\), \(P_c\) denote the polygons that make up the shapes of \(\mathcal{T}\). For each \(i\) such that \(1\leq i \leq c\), assume that each \(P_i\) is in standard position given some vertex \(v_i\) of \(P_i\). Then, a configuration of \(\mathcal{T}\) is a partial function \(\pfunc{\alpha}{\mathbb{R}^2\times \left[ 0, 2\pi \right)}{T}\). One should think of this function as mapping centroid locations and an angle of rotation, \((r,\theta)\) say, to a tile in \(T\) as follows. Starting from \(t\) in standard position, \(t\) is rotated counter-clockwise by \(\theta\) and translated so that the centroid of \(t\) is at \(r\). Note that the definition of configuration makes no claim as to whether or not two tiles of a configuration have overlapping interiors or have matching glues. Similarly, we can define an assembly to be a configuration such that every tile is adjacent to some other tile and the intersection of the interiors of any two distinct tiles is empty. Then an assembly \(\alpha'\) is a \(\emph{subassembly}\) of \(\alpha\) if \(\dom(\alpha')\subseteq \dom(\alpha)\) and if \((r,\theta)\in \dom(\alpha')\) then \(\alpha((r,\theta)) = \alpha'((r,\theta))\). We define subconfiguration analogously to the way we defined subassembly.

Assembly Process

Given a tile-assembly system \(\mathcal{T} = (T,\sigma,\tau)\), we now define the set of \(\emph{producible}\) assemblies \(\mathcal{A}_{\Box}[\mathcal{T}]\) that can be derived from \(\mathcal{T}\), as well as the \(\emph{terminal}\) assemblies, \(\mathcal{A}[\mathcal{T}]\), which are the producible assemblies to which no additional tiles can attach. The assembly process begins from \(\sigma\) and proceeds by single steps in which any single copy of some tile \(t \in T\) may be attached to the current assembly \(A\), provided that it can be translated and/or rotated so that its placement does not overlap any previously placed tiles and it binds with strength \(\ge \tau\). For a system \(\mathcal{T}\) and assembly \(A\), if such a \(t\in T\) exists, we say \(A \rightarrow^\mathcal{T}_1 A'\) (i.e. \(A\) grows to \(A'\) via a single tile attachment). We use the notation \(A \rightarrow^\mathcal{T} A''\), when \(A\) grows into \(A''\) via \(0\) or more steps. Assembly proceeds asynchronously and nondeterministically, attaching one tile at a time, until no further tiles can attach. An \emph{assembly sequence} in a TAS \(\mathcal{T}\) is a (finite or infinite) sequence \(\vec{\alpha} = (\alpha_0 = \sigma,\alpha_1,\alpha_2,\ldots)\) of assemblies in which each \(\alpha_{i+1}\) is obtained from \(\alpha_i\) by the addition of a single tile.

The set of producible assemblies \(\mathcal{A}_{\Box}[\mathcal{T}]\) is defined to be the set of all assemblies \(A\) such that there exists an assembly sequence for \(\mathcal{T}\) ending with \(A\) (possibly in the limit). The set of \(\emph{terminal}\) assemblies \(\mathcal{A}[\mathcal{T}] \subseteq \mathcal{A}_{\Box}[\mathcal{T}]\) is the set of producible assemblies such that for all \(A \in \mathcal{A}[\mathcal{T}]\) there exists no assembly \(B \in \mathcal{A}_{\Box}[\mathcal{T}]\) in which \(A\rightarrow^\mathcal{T}_1 B\). A system \(\mathcal{T}\) is said to be directed if \(|\mathcal{A}[\mathcal{T}]|=1\), i.e., if it has exactly one terminal assembly.

Results

We now state our main results. The first set of results are positive and state that there are a variety of systems with polygons which can simulate any Turing machine, while the final result is a negative result which states that the class of systems whose tiles are composed of regular polygons with less than \(7\) sides cannot compute using known techniques in self-assembly:

Informally, our first theorem states that if \(P\) is a regular polygon with \(\ge 7\) sides, then the class of systems with tiles of shape \(P\) is computationally universal.

\(\emph{Theorem 1.}\) Let \(P_n\) be a regular polygon with \(n\) sides such that \(n \ge 7\). Then for every standard Turing machine \(M\) and input \(w\), there exists a directed TAS with \(\tau = 1\) consisting only of tiles of shape \(P_n\) that simulates \(M\) on \(w\).

The following theorem states that if we are allowed two different regular polygons as tile shapes, then the class of systems consisting only of these two shapes is computationally universal.

\(\emph{Theorem 2.}\) Let \(P_n\) and \(Q_m\) be regular polygons with \(n\) and \(m\) sides of equal length. Then for every \(n \ge 3\) and \(m \ge 3\) such that \(n \ne m\), and every standard Turing machine \(M\) with input \(w\), there exists a directed 2-shaped system \(T_n_,_m =\) (\(T_n_,_m\), \(\sigma_n_,_m\)) consisting only of tiles of shape \(P_n\) or \(Q_m\) that simulates \(M\) on \(w\).

The next theorem differs from the previous two theorems in that it discusses the computational power of polygons which are not regular. Roughly, it states that if we relax the condition that the polygon is regular (but still equilateral), then there exist polygons with only four sides which are capable of composing a class of computationally universal single shape systems. It also implies this for shapes with five and six sides as well.

\(\emph{Theorem 3.}\) Let \(M\) be a standard Turing machine with input \(w\). Then for all \(n \ge 4\), there exists an equilateral polygon \(P_n\) with \(n\) sides and a directed single-shaped system \(T_n = (T_n, \sigma_n)\) consisting only of tiles of shape \(P_n\) that simulates \(M\) on \(w\).

Our final positive result shows that there exists a class of single-shaped systems of obtuse isosceles triangle which is computationally universal.

\(\emph{Theorem 4.}\) Let \(M\) be a standard Turing machine with input \(w\). Then, there exists an obtuse isosceles triangle \(P\) and a directed single-shaped system \(T = (T, \sigma)\) consisting only of tiles of shape \(P\) that simulates \(M\) on \(w\).

We now state the negative result, which is based on the fact that regular polygonal tiles with \(\leq 6\) sides cannot form paths capable of blocking each other in specific ways allowing important geometric information encoding and decoding.

\(\emph{Theorem 5.}\) Let \(n \in N\) be such that \(3 \leq n \leq 6\). Then, there exists no temperature \(1\) single-shaped polygonal tile assembly system \(T = (T, \sigma, 1)\) where for all \(t \in T\), \(t\) is a regular polygon with \(n\) sides, and a bit-reading gadget exists for \(T\) .