Difference between revisions of "Polyomino Tile Assembly Model (polyTAM)"

From self-assembly wiki
Jump to navigation Jump to search
 
(18 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
__TOC__
 
__TOC__
  
−
==The Polyomino Tile Assembly Model==
+
__TOC__
  
−
Here we present the Polyomino Tile Assembly Model. square tile version. A polyomino is a finite subset of the regular square tiling of the 2D plane with a connected interior.
+
In this section we define the Polyomino Tile Assembly Model (polyTAM) and relevant terminology.
−
graph version. A polyomino is a subgraph $P$ of the grid graph such that for any cut of $P$, there is an edge that crosses the cut. For convenience, we always assume that any polyomino is such that leftmost vertex of the bottommost vertices lies at the origin $(0,0)$. Note that any polyomino can be translated in the plane so that this assumption holds. Then, relative to the vertex of a polyomino $P$ that lies at the origin, we assign a coordinate pair to each of the vertices of $P$ and.
 
  
  
−
In the Polyomino Tile Assembly Model, a $\emph{polyomino tile type}$ (or simply $\emph{tile type}$) is a polyomino, along with an assignment of a $\emph{glue label}$ -- often represented as a finite string, and a nonnegative integer $\emph{strength}$ to each edge of the polyomino. A glue~$g$ that appears on multiple tile types always has the same strength~$s_g$.
+
==Polyomino Tiles==
−
There are a finite set $T$ of tile types, but an infinite number of copies of each tile type, with each copy being referred to as a $\emph{polyomino tile}$ (or simply $\emph{tile}$).
 
  
  
−
A partial function $f:\Z^2 \dashrightarrow T \times \Z^2$ is said to be $\emph{consistent}$ with $T$ if the following holds.
+
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$.
  
  
−
If $f(\vec{v}) = (P,\vec{0}\, )$ and $P$ has a vertex at $\vec{t}$, then $f(\vec{v} + \vec{t}) = (P, \vec{t}\, )$.
+
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$.
  
  
−
An $\emph{assembly}$ is a positioning of polyomino tiles on the integer lattice $\Z^2$, described formally as a partial function $\alpha:\Z^2 \dashrightarrow T$. Let $\mathcal{A}^T$ denote the set of all assemblies of tiles from $T$, and let $\mathcal{A}^T_{< \infty}$ denote the set of finite assemblies of tiles from $T$. We write $\alpha \sqsubseteq \beta$ to denote that $\alpha$ is a $\emph{subassembly}$ of $\beta$, which means that $\dom\alpha \subseteq \dom\beta$ and $\alpha(p)=\beta(p)$ for all points $p\in\dom\alpha$. Two adjacent tiles in an assembly $\emph{interact}$, or are $\emph{attached}$, if the glue labels on their abutting sides are equal and have positive strength. Each assembly induces a $\emph{binding graph}$, a grid graph whose vertices are tiles, with an edge between two tiles if they interact. The assembly is $\emph{tau-stable}$ if every cut of its binding graph has strength at least $\tau$, where the strength of a cut is the sum of all of the individual glue strengths in the cut. When $\tau$ is clear from context, we simply say that a $\tau$-stable assembly is stable.
+
==Tile System==
  
  
−
The $\emph{frontier} \partial\alpha \subseteq \Z^2 \setminus \dom\alpha$ of $\alpha$ is the set of empty locations adjacent to $\alpha$ at which a single tile could bind stably.
+
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)$).
  
  
−
A $\emph{tile assembly system}$ (TAS) is a triple $\calT = (T,\sigma,\tau)$, where $T$ is a finite set of tile types, $\sigma:\Z^2 \dashrightarrow T$ is a finite, $\tau$-stable $\emph{seed assembly}$, and $\tau$ is the $\emph{temperature}$. An assembly $\alpha$ is $\emph{producible}$ if either $\alpha = \sigma$ or if $\beta$ is a producible assembly and $\alpha$ can be obtained from $\beta$ by the stable binding of a single tile. In this case we write $\beta\to_1^\calT \alpha$ (to mean~$\alpha$ is producible from $\beta$ by the attachment of one tile), and we write $\beta\to^\calT \alpha$ if $\beta \to_1^{\calT*} \alpha$ (to mean $\alpha$ is producible from $\beta$ by the attachment of zero or more tiles). When $\calT$ is clear from context, we may write $\to_1$ and $\to$ instead. We let $\prodasm{\calT}$ denote the set of producible assemblies of $\calT$. An assembly is $\emph{terminal}$ if no tile can be $\tau$-stably attached to it. We let $\termasm{calT} \subseteq \prodasm{\calT}$ denote  the set of producible, terminal assemblies of $\calT$. A TAS $\calT$ is $\emph{directed}$ if $|\termasm{\calT}| = 1$. Hence, although a directed system may be nondeterministic in terms of the order of tile placements,  it is deterministic in the sense that exactly one terminal assembly is producible (this is analogous to the notion of ${\em confluence}$ in rewriting systems).
+
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.
−
 
 
−
 
 
−
In this section we define the Polyomino Tile Assembly Model (polyTAM) and relevant terminology.
 
−
 
 
  
−
A $\emph{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 $\emph{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 $\emph{polyomino tile}$ is a polyomino 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 $\emph{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 $\emph{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 $\emph{tau-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 polyominoes) must separate bound glues whose strengths sum to $\ge \tau$.
 
  
 +
==Assembly Process==
  
−
The $\emph{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 $\emph{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$.
 
  
 +
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.
  
−
A $\emph{tile assembly system}$ (TAS) is an ordered triple $\calT = (T,\sigma,\tau)$ (where $T$ is a set of polyomino tiles, and $\sigma$ is a $\tau$-stable assembly called the
 
−
$\emph{seed}$) that consists of integer translations of elements of $T$. $\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. $\calT = (T,\sigma)$).
 
  
 +
Note that the aTAM is simply a specific case of the polyTAM in which all tiles are monominoes, i.e., single unit squares. <ref name="SJMTR"/>
  
−
If the tiles in $T$ all have the same polyomino shape, $\calT$ is said to be a $\emph{single-shape}$ system; more generally $\calT$ 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, $\calT$ is said to be a $\emph{monomino}$ system.
 
  
 +
==Results==
  
−
Given a tile-assembly system $\calT = (T,\sigma,\tau)$, we now define the set of $\emph{producible}$ assemblies $\prodasm{T}$ that can be derived from $\calT$, as well as the $\emph{terminal}$ assemblies, $\termasm{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 $\calT$ and assembly $A$, if such a $t\in T$ exists, we say $A \rightarrow^\calT_1 A'$ (i.e. $A$ grows to $A'$ via a single tile attachment).  We use the notation
+
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.
  
−
A $\rightarrow^\calT 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 $\emph{assembly sequence}$ for $\calT$ is any sequence of stable assemblies $\langle \sigma=A_1 , \ldots , A_k \rangle$ such that $A_i \rightarrow^1_\calT A_{i+1}$. The set of producible assemblies $\prodasm{T}$ is defined to be the set of all assemblies $A$ such that there exists an assembly sequence for $\calT$ ending with $A$ (possibly in the limit). The set of $\emph{terminal}$ assemblies $\termasm{T} \subseteq \prodasm{T}$ is the set of producible assemblies such
+
==Software==
−
that for all $A \in \termasm{T}$ there exists no assembly $B \in \prodasm{T}$ in which $A\rightarrow^\calT_1 B$.  A system $\calT$ is said to be directed if $|\termasm{T}|=1$, i.e., if it has exactly one terminal assembly.
+
The following link allows you to access a directory containing various versions of a polyomino tile simulator, PolyominoTAS.
 +
http://self-assembly.net/software/PolyominoTAS/
  
  
−
[RTS: there seems to be an issue with this definition of directed, maybe. Think of a system that grows either an infinite random growth, or 1 terminal finite assembly. It seems this satisfies $|\termasm{T}|=1$. Possible alternate definition: A system is said to be directed if for all $X \subseteq \prodasm{T}$, there exists a producible assembly $A_x \in \prodasm{T}$ such that for each $a \in X$ it is the case that $a \rightarrow^*_\calT A_x$.] [MJP: I changed the definition of assembly sequence and producible assembly to allow for infinite assemblies (which we normally do in the aTAM) and now I think the original definition is okay, but would like Robbie to see if he agrees.]
+
==References==
  
 +
<references>
 +
<ref name="SJMTR"><bibtex>
 +
@article{SJMTR,
 +
  author = "Sándor P. Fekete, Jacob Hendricks, Matthew J. Patitz, Trent A. Rogers, Robert T. Schweller",
 +
  title = "Universal Computation with Arbitrary Polyomino Tiles in Non-Cooperative Self-Assembly",
 +
  journal = "arXiv",
 +
  number = "1408.3351",
 +
  year = "2014",
 +
}
 +
</bibtex></ref>
 +
</references>
  
−
Note that the aTAM is simply a specific case of the polyTAM in which all tiles are monominoes, i.e., single unit squares.
+
[[category:Tile Assembly Models]]
 +
[[Category:Self-assembly]]

Latest revision as of 10:31, 29 June 2022


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. [1]


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/


References

  1. ↑ 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
    arXiv (1408.3351),2014
    Bibtex
    Author : Sándor P. Fekete, Jacob Hendricks, Matthew J. Patitz, Trent A. Rogers, Robert T. Schweller
    Title : Universal Computation with Arbitrary Polyomino Tiles in Non-Cooperative Self-Assembly
    In : arXiv -
    Address :
    Date : 2014
Retrieved from "http://self-assembly.net/wiki/index.php?title=Polyomino_Tile_Assembly_Model_(polyTAM)&oldid=1862"