Polyomino Tile Assembly Model (polyTAM)

In this section we define the Polyomino Tile Assembly Model (polyTAM) and relevant terminology.

Polyomino Tiles

A \(polyomino\) is a plane geometric figure formed by joining one or more equal unit squares edge to edge; it can also be considered a finite subset of the regular square tiling with a connected interior. For convenience, we will assume that each unit square is centered on a point in \(Z^2\). We define the set of \(edges\) of a polyomino to be the set of faces from the constituent unit squares of the polyomino that lie on the boundary of the polyomino shape. A \(polyomino\) \(tile\) is a polyomino with a subset of its edges labeled from some \(glue\) alphabet \(\Sigma\), with each glue having an integer \(strength\) value. Two tiles are said to \(bind\) when they are placed so that they have non-overlapping interiors and adjacent edges with matching glues; each matching glue binds with force equal to its strength value. An \(assembly\) is any connected set of polyominoes whose interiors do not overlap. Given a positive integer \(\tau \in \mathbb{N}\), an assembly is said to be \(tau-stable\) or (just \(stable\) if \(\tau\) is clear from context), if any partition of the assembly into two non-empty groups (without cutting individual polyominoes) must separate bound glues whose strengths sum to \(\ge \tau\).

The \(bounding\) \(rectangle\) \(B\) around a polyomino \(P\) is the rectangle with minimal area (and corners lying in \(\mathbb{Z}^2\)) that contains \(P\). For each polyomino shape, we designate one pixel (i.e. one of the squares making up \(P\)) \(p\) as a distinguished pixel that we use as a reference point. More formally, a \(pixel\) \(p\) in a polyomino \(P\) (or polyomino tile) is defined in the following manner. Place \(P\) in the plane so that the southwest corner of the bounding rectangle of \(P\) lies at the origin. Then a pixel \(p=(p_1,p_2) \in P\) is a point in \(\mathbb{Z}^2\) which is occupied by a unit square composing the polyomino \(P\). We say that a pixel \(p' \in P\) lies on the perimeter of the bounding rectangle \(B\) if an edge of the pixel \(p'\) lies on an edge of \(B\).

Tile System

A \(tile\) \(assembly\) \(system\) (TAS) is an ordered triple \(\mathcal{T} = (T,\sigma,\tau)\) (where \(T\) is a set of polyomino tiles, and \(\sigma\) is a \(\tau\)-stable assembly called the \(seed\)) that consists of integer translations of elements of \(T\). \(\tau\) is the \(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 polyomino shape, \(\mathcal{T}\) is said to be a \(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. If \(T\) consists of unit-square tiles, \(\mathcal{T}\) is said to be a \(monomino\) system.

Assembly Process

Given a tile-assembly system \(\mathcal{T} = (T,\sigma,\tau)\), we now define the set of \(producible\) assemblies \(A[\mathcal{T}]\) that can be derived from \(\mathcal{T}\), as well as the \(terminal\) assemblies, \(A_t[\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 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 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. An \(assembly sequence\) for \(\mathcal{T}\) is any sequence of stable assemblies \(\langle \sigma=A_1 , \ldots , A_k \rangle\) such that \(A_i \rightarrow^1_\mathcal{T} A_{i+1}\). The set of producible assemblies \(A[\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 \(terminal\) assemblies \(A_t[\mathcal{T}] \subseteq A[\mathcal{T}]\) is the set of producible assemblies such that for all \(A \in A_t[\mathcal{T}]\) there exists no assembly \(B \in A[\mathcal{T}]\) in which \(A\rightarrow^\mathcal{T}_1 B\). A system \(\mathcal{T}\) is said to be directed if \(|A_t[\mathcal{T}]|=1\), i.e., if it has exactly one terminal assembly.

Note that the aTAM is simply a specific case of the polyTAM in which all tiles are monominoes, i.e., single unit squares.

Results

We can now proceed to state our main result: any polyomino P of size at least three can be used for polyomino tile-assembly systems that are computationally universal at temperature 1. Formally stated\[Theorem 5.1\] Let P be a polyomino such that \(|P| \ge 3\). Then for every standard Turing Machine M and input w, there exists a TAS with \(\tau = 1\) consisting only of tiles of shape P that simulates M on w.

Software

The following link allows you to access a directory containing various versions of a polyomino tile simulator, PolyominoTAS. http://self-assembly.net/software/PolyominoTAS/