Difference between revisions of "Zig-zag tile assembly system"
Wiki admin (talk | contribs) |
|||
| (One intermediate revision by one other user not shown) | |||
| Line 1: | Line 1: | ||
| − | 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 | + | 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. |
| − | Compact zig-zag systems are zig-zag | + | 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 the horizontal growth. Compact zig-zag systems are capable of simulating universal Turing machines. |
== formal definition == | == formal definition == | ||
Latest revision as of 14:26, 27 May 2014
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.
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 the horizontal growth. Compact zig-zag systems are capable of simulating universal Turing machines.
formal definition
A tile assembly system <m>\tau= (T,\sigma,2)</m> is called a zig-zag tile assembly system if (1) <m>\tau</m> is directed, (2) there is a single assembly sequence <m>\alpha</m> in <m>\tau</m>, with <m>A[\tau] = \{\alpha\}</m>, and (3) for every <m>x \in</m> dom <m>\alpha</m>, (0,1) <m>\notin</m> IN<m>^{\alpha}(x)</m>.
Additionally, we say that <m>\tau</m> is compact if <m>\tau</m> is a zig-zag system with <m>A[\tau] = \{\alpha\}</m> and for every <m>x \in</m> dom <m>\alpha</m> and ever <m>u \in U_{2},str_{\alpha(x)}(u)+str_{\alpha(x)}(-u)<4</m>.
