Difference between revisions of "Zig-Zag Systems"
| Line 2: | Line 2: | ||
A tile assembly system $\mathcal{T} = (T, \sigma, 2)$ is called a zig-zag tile assembly system if (1) $\mathcal{T}$ is directed, (2) there is a single assembly sequence $\vec{\alpha}$ in $\mathcal{T}$ , with $A_t[\mathcal{T}] = {\alpha}$, and (3) for every $\vec{x} \in$ dom $\alpha$, (0, 1) $\notin $IN$^{\vec{\alpha}} (\vec{x})$. Intuitively, zig-zag systems are those that grow one horizontal row at a time, alternating left-to-right and right-to-left growth, always adding new rows to the north and never growing south. Zig-zag systems are capable of simulating universal Turing machines, and thus universal computation. If $\mathcal{T}$ is a zig-zag system with $A_t[\mathcal{T}] = {\alpha}$ and for every $\vec{x} \in$ dom $\alpha$ and every $\vec{u} \in U_2,$ $str_{α(\vec{x})}(\vec{U})$ + $str_{α(\vec{x})}(-\vec{U})$ < 4, then we say that $\mathcal{T}$ is compact. Intuitively, compact zig-zag systems are zig-zag systems that only extend the width of each row by one over the length of the previous row, and only grow upward by one tile before continuing horizontal growth. Compact zig-zag systems are capable of simulating universal Turing machines. <ref name="NegaGlue"/> | A tile assembly system $\mathcal{T} = (T, \sigma, 2)$ is called a zig-zag tile assembly system if (1) $\mathcal{T}$ is directed, (2) there is a single assembly sequence $\vec{\alpha}$ in $\mathcal{T}$ , with $A_t[\mathcal{T}] = {\alpha}$, and (3) for every $\vec{x} \in$ dom $\alpha$, (0, 1) $\notin $IN$^{\vec{\alpha}} (\vec{x})$. Intuitively, zig-zag systems are those that grow one horizontal row at a time, alternating left-to-right and right-to-left growth, always adding new rows to the north and never growing south. Zig-zag systems are capable of simulating universal Turing machines, and thus universal computation. If $\mathcal{T}$ is a zig-zag system with $A_t[\mathcal{T}] = {\alpha}$ and for every $\vec{x} \in$ dom $\alpha$ and every $\vec{u} \in U_2,$ $str_{α(\vec{x})}(\vec{U})$ + $str_{α(\vec{x})}(-\vec{U})$ < 4, then we say that $\mathcal{T}$ is compact. Intuitively, compact zig-zag systems are zig-zag systems that only extend the width of each row by one over the length of the previous row, and only grow upward by one tile before continuing horizontal growth. Compact zig-zag systems are capable of simulating universal Turing machines. <ref name="NegaGlue"/> | ||
| − | <ref name="ZZSim"/> | + | In a paper by Cook, Fu, and Schweller<ref name="ZZSim"/>, it is shown that 2D zig-zag systems at temperature 2 can be simulated by 3D zig-zag systems in temperature 1. |
==References== | ==References== | ||
Revision as of 16:39, 14 July 2016
Overview
A tile assembly system \(\mathcal{T} = (T, \sigma, 2)\) is called a zig-zag tile assembly system if (1) \(\mathcal{T}\) is directed, (2) there is a single assembly sequence \(\vec{\alpha}\) in \(\mathcal{T}\) , with \(A_t[\mathcal{T}] = {\alpha}\), and (3) for every \(\vec{x} \in\) dom \(\alpha\), (0, 1) \(\notin \)IN\(^{\vec{\alpha}} (\vec{x})\). Intuitively, zig-zag systems are those that grow one horizontal row at a time, alternating left-to-right and right-to-left growth, always adding new rows to the north and never growing south. Zig-zag systems are capable of simulating universal Turing machines, and thus universal computation. If \(\mathcal{T}\) is a zig-zag system with \(A_t[\mathcal{T}] = {\alpha}\) and for every \(\vec{x} \in\) dom \(\alpha\) and every \(\vec{u} \in U_2,\) \(str_{α(\vec{x})}(\vec{U})\) + \(str_{α(\vec{x})}(-\vec{U})\) < 4, then we say that \(\mathcal{T}\) is compact. Intuitively, compact zig-zag systems are zig-zag systems that only extend the width of each row by one over the length of the previous row, and only grow upward by one tile before continuing horizontal growth. Compact zig-zag systems are capable of simulating universal Turing machines. [1]
In a paper by Cook, Fu, and Schweller[2], it is shown that 2D zig-zag systems at temperature 2 can be simulated by 3D zig-zag systems in temperature 1.
