Difference between revisions of "Polyomino Tile Assembly Model (polyTAM)"
(→Polynomio Tiles) |
(→Polynomio Tiles) |
||
| Line 5: | Line 5: | ||
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 $\mathbb{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 $\geq \tau$. | 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 $\mathbb{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 $\geq \tau$. | ||
| − | The ''bounding rectangle'' $B$ around a polyomino $P$ is the rectangle with minimal area (and corners lying in $\ | + | 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$. |
==References== | ==References== | ||
Revision as of 12:05, 3 July 2015
Polyomino Tile Assembly Model (polyTAM)[1] is composed of a collection of unit squares joined along their edges. This allows for tiles with arbitrary geometric complexity and a much larger variety of shapes than in earlier work involving systems composed of both square and 2×1 rectangular tiles, or those with tiles composed of square bodies and edges with bumps and dents. geometry, in the polyTAM as in natural self-assembling systems, affords great power. Namely, any polyomino shape which is composed of only 3 or more unit squares has enough geometric complexity to allow a polyTAM system at temperature 1, composed only of tiles of that shape, to perform Turing universal computation. This impressive potency is perhaps even more surprising when it is realized that while a single unit-square polyomino (a.k.a. a monomino, or a standard aTAM tile) is conjectured not to provide this power, the same shape expanded in scale to a 2 × 2 square polyomino does. The key to this power is the ability of arbitrary polyominoes of size 3 or greater to both combine with each other to form regular grids, as well as to combine in a variety of relative offsets that allow some tiles to be shifted relatively to those grids and then perform geometric blocking of the growth of specific configurations of paths of tiles, while allowing other paths to complete their growth. With just this seemingly simple property, it is possible to design temperature-1 systems of polyominoes that can simulate arbitrary Turing machines.
Polynomio 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 \(\mathbb{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 \(\geq \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\).
References
- ↑
Sándor P. Fekete, Jacob Hendricks, Matthew J. Patitz, Trent A. Rogers, Robert T. Schweller - Universal Computation with Arbitrary Polyomino Tiles in Non-Cooperative Self-Assembly
