Difference between revisions of "Simulation in the aTAM"

From self-assembly wiki
Jump to navigation Jump to search
(Formal Definition)
(Formal Definition)
Line 9: Line 9:
 
Let $B^T_m$ be the set of all $m$-block supertiles over $T$.
 
Let $B^T_m$ be the set of all $m$-block supertiles over $T$.
 
The $m$-block with no domain is said to be ''empty''.
 
The $m$-block with no domain is said to be ''empty''.
For a general assembly $\alpha:\mathbb{Z}^d \dashrightarrow T$ and $(x_0,\ldots x_{d-1})\in\mathbb{Z}^d$, define $\alpha^m_{x_0,\ldots x_{d-1}}$ to be the $m$-block supertile defined by $\alpha^m_{x_0,\ldots, x_{d-1}}(i_0,\ldots, i_{d-1}) = \alpha(mx_0+i_0,\ldots, mx_{d-1}+i_{d-1})$ for $0 \leq i_0, \ldots, i_{d-1}< m$.
+
For a general assembly $\alpha:\mathbb{Z}^d \dashrightarrow T$ and $(x_0,\ldots x_{d-1})\in\mathbb{Z}^d$, define $\alpha^m_{x_0,\ldots x_{d-1}}$ to be the $m$-block supertile defined by $\alpha^m_{x_0,\ldots, x_{d-1}}(i_0,\ldots, i_{d-1}) = \alpha(mx_0+i_0,\ldots, mx_{d-1}+i_{d-1})$ for $0 \leq i_0, \ldots, i_{d-1}< m.$
 +
For some tile set $S$ of dimension $d' \geq d$, a partial function $R: B^{S}_m \dashrightarrow T$ is said to be a ''valid $m$-block supertile representation'' from $S$ to $T$ if for any $\alpha,\beta \in B^{S}_m$ such that $\alpha \sqsubseteq \beta$ and $\alpha \in \dom R$, then $R(\alpha) = R(\beta)$.
  
For some tile set $S$ of dimension $d' \geq d$, a partial function $R: B^{S}_m \dashrightarrow T$ is said to be a ''valid $m$-block supertile representation'' from $S$ to $T$ if for any $\alpha,\beta \in B^{S}_m$ such that $\alpha \sqsubseteq \beta$ and $\alpha \in \dom R$, then $R(\alpha) = R(\beta)$.
+
 
 +
 
 +
Let  $d' \in \{ 2,3 \}$ and $d \in \{ d' -1, d' \} $.
 +
Let $f: \mathbb{Z}^{d'} \rightarrow \mathbb{Z}^{d}$, where $f(x_0,\ldots,x_{d'-1}) = (x_0,\ldots,x_{d'-1})$ if $d'=d$ and $f(x_0,\ldots,x_{d'-1}) = (x_0,\ldots,x_{d-1},0)$ if $d = d' -1$, and undefined otherwise.
 +
For a given valid $m$-block supertile representation function $R$ from tile set $S$ to tile set $T$, define the ''assembly representation function''
 +
$R^*: \mathcal{A}^{S} \rightarrow \mathcal{A}^T$ such that $R^*(\alpha') = \alpha$ if and only if $\alpha(x_0,\ldots, x_{d-1}) = R\left(\alpha'^m_{x_0,\ldots, x_{d'-1}}\right)$ for all $(x_0,\ldots x_{d'-1}) \in \Z^{d'-1}$.
 +
Note that $R^*$ is a total function since every assembly of $S$ represents ''some'' assembly of $T$; the functions $R$ and $\alpha$ are partial to allow undefined points to represent empty space.
 +
 
 +
For an assembly $\alpha' \in \mathcal{A}^{S}$ such that $R(\alpha') = \alpha$, $\alpha'$ is said to map ''cleanly'' to $\alpha \in \mathcal{A}^T$ under $R^*$ if for all non empty blocks $\alpha'^m_{x_0,\ldots, x_{d'-1}},$ $(f(x_0,\ldots,x_{d'-1})+f(u_0,\ldots,u_{d'-1})) \in \dom \alpha$ for some $u_0,\ldots, u_{d'-1} \in \{-1,0,1\}$ such that $u_0^2 + \cdots + u_{d'-1}^2 \leq 1$, or if $\alpha'$ has at most one non-empty $m$-block $\alpha^m_{0, \ldots, 0}$.
 +
In other words, $\alpha'$ may have tiles on supertile blocks representing empty space in $\alpha$, but only if that position is adjacent to a tile in $\alpha$.  We call such growth "around the edges" of $\alpha'$ ''fuzz'' and thus restrict it to be adjacent to only valid supertiles, but not diagonally adjacent (i.e. we do not permit ''diagonal fuzz'').
  
 
==References==
 
==References==

Revision as of 11:56, 12 July 2013

Informal Definition of Simulation

Formal Definition

From this point on, let \(T\) be a \(d\)-dimensional tile set, and let \(m\in\mathbb{Z}^+\). An \(m\)-block supertile over \(T\) is a partial function \(\alpha:\mathbb{Z}_m^d \dashrightarrow T\), where \(\mathbb{Z}_m = \{0,1,\ldots,m-1\}\). Note that the dimension of the \(m\)-block is implicitly defined by the dimension of \(T\). Let \(B^T_m\) be the set of all \(m\)-block supertiles over \(T\). The \(m\)-block with no domain is said to be empty. For a general assembly \(\alpha:\mathbb{Z}^d \dashrightarrow T\) and \((x_0,\ldots x_{d-1})\in\mathbb{Z}^d\), define \(\alpha^m_{x_0,\ldots x_{d-1}}\) to be the \(m\)-block supertile defined by \(\alpha^m_{x_0,\ldots, x_{d-1}}(i_0,\ldots, i_{d-1}) = \alpha(mx_0+i_0,\ldots, mx_{d-1}+i_{d-1})\) for \(0 \leq i_0, \ldots, i_{d-1}< m.\) For some tile set \(S\) of dimension \(d' \geq d\), a partial function \(R: B^{S}_m \dashrightarrow T\) is said to be a valid \(m\)-block supertile representation from \(S\) to \(T\) if for any \(\alpha,\beta \in B^{S}_m\) such that \(\alpha \sqsubseteq \beta\) and \(\alpha \in \dom R\), then \(R(\alpha) = R(\beta)\).


Let \(d' \in \{ 2,3 \}\) and \(d \in \{ d' -1, d' \} \). Let \(f: \mathbb{Z}^{d'} \rightarrow \mathbb{Z}^{d}\), where \(f(x_0,\ldots,x_{d'-1}) = (x_0,\ldots,x_{d'-1})\) if \(d'=d\) and \(f(x_0,\ldots,x_{d'-1}) = (x_0,\ldots,x_{d-1},0)\) if \(d = d' -1\), and undefined otherwise. For a given valid \(m\)-block supertile representation function \(R\) from tile set \(S\) to tile set \(T\), define the assembly representation function \(R^*: \mathcal{A}^{S} \rightarrow \mathcal{A}^T\) such that \(R^*(\alpha') = \alpha\) if and only if \(\alpha(x_0,\ldots, x_{d-1}) = R\left(\alpha'^m_{x_0,\ldots, x_{d'-1}}\right)\) for all \((x_0,\ldots x_{d'-1}) \in \Z^{d'-1}\). Note that \(R^*\) is a total function since every assembly of \(S\) represents some assembly of \(T\); the functions \(R\) and \(\alpha\) are partial to allow undefined points to represent empty space.

For an assembly \(\alpha' \in \mathcal{A}^{S}\) such that \(R(\alpha') = \alpha\), \(\alpha'\) is said to map cleanly to \(\alpha \in \mathcal{A}^T\) under \(R^*\) if for all non empty blocks \(\alpha'^m_{x_0,\ldots, x_{d'-1}},\) \((f(x_0,\ldots,x_{d'-1})+f(u_0,\ldots,u_{d'-1})) \in \dom \alpha\) for some \(u_0,\ldots, u_{d'-1} \in \{-1,0,1\}\) such that \(u_0^2 + \cdots + u_{d'-1}^2 \leq 1\), or if \(\alpha'\) has at most one non-empty \(m\)-block \(\alpha^m_{0, \ldots, 0}\). In other words, \(\alpha'\) may have tiles on supertile blocks representing empty space in \(\alpha\), but only if that position is adjacent to a tile in \(\alpha\). We call such growth "around the edges" of \(\alpha'\) fuzz and thus restrict it to be adjacent to only valid supertiles, but not diagonally adjacent (i.e. we do not permit diagonal fuzz).

References