Difference between revisions of "Temperature 1 Self-Assembly: Deterministic Assembly in 3D and Probabilistic Assembly in 2D"
Wiki admin (talk | contribs) |
m |
||
(7 intermediate revisions by 2 users not shown) | |||
Line 1: | Line 1: | ||
− | {{ | + | {{PaperTemplate |
− | + | |abstract=We investigate the power of the Wang tile self-assembly model at temperature 1, a threshold value that permits attachment between any two tiles that share even a single bond. When restricted to deterministic assembly in the plane, no temperature 1 assembly system has been shown to build a shape with a tile complexity smaller than the diameter of the shape. In contrast, we show that temperature 1 self-assembly in 3 dimensions, even when growth is restricted to at most 1 step into the third dimension, is capable of simulating a large class of temperature 2 systems, in turn permitting the simulation of arbitrary Turing machines and the assembly of $n \times n$ squares in near optimal $O(\log n)$ tile complexity. Further, we consider temperature 1 probabilistic assembly in 2D, and show that with a logarithmic scale up of tile complexity and shape scale, the same general class of temperature $\tau=2$ systems can be simulated with high probability, yielding Turing machine simulation and $O(\log^2 n)$ assembly of $n\times n$ squares with high probability. Our results show a sharp contrast in achievable tile complexity at temperature 1 if either growth into the third dimension or a small probability of error are permitted. Motivated by applications in nanotechnology and molecular computing, and the plausibility of implementing 3 dimensional self-assembly systems, our techniques may provide the needed power of temperature 2 systems, while at the same time avoiding the experimental challenges faced by those systems. | |
− | |abstract=We investigate the power of the Wang tile self-assembly model at temperature 1, a threshold value that permits attachment between any two tiles that share even a single bond. When restricted to deterministic assembly in the plane, no temperature 1 assembly system has been shown to build a shape with a tile complexity smaller than the diameter of the shape. In contrast, we show that temperature 1 self-assembly in 3 dimensions, even when growth is restricted to at most 1 step into the third dimension, is capable of simulating a large class of temperature 2 systems, in turn permitting the simulation of arbitrary Turing machines and the assembly of | ||
− | |||
|authors=Matthew Cook, Yunhui Fu, Robert Schweller | |authors=Matthew Cook, Yunhui Fu, Robert Schweller | ||
|date=2010/05/13 | |date=2010/05/13 | ||
− | |file=Temp1 deterministic3d probablistic2d.pdf | + | |file=[[Media:Temp1 deterministic3d probablistic2d.pdf | Temperature 1 Self-Assembly: Deterministic Assembly in 3D and Probabilistic Assembly in 2D.pdf]] |
}} | }} |
Latest revision as of 13:46, 22 June 2021
Published on: 2010/05/13
Abstract
We investigate the power of the Wang tile self-assembly model at temperature 1, a threshold value that permits attachment between any two tiles that share even a single bond. When restricted to deterministic assembly in the plane, no temperature 1 assembly system has been shown to build a shape with a tile complexity smaller than the diameter of the shape. In contrast, we show that temperature 1 self-assembly in 3 dimensions, even when growth is restricted to at most 1 step into the third dimension, is capable of simulating a large class of temperature 2 systems, in turn permitting the simulation of arbitrary Turing machines and the assembly of \(n \times n\) squares in near optimal \(O(\log n)\) tile complexity. Further, we consider temperature 1 probabilistic assembly in 2D, and show that with a logarithmic scale up of tile complexity and shape scale, the same general class of temperature \(\tau=2\) systems can be simulated with high probability, yielding Turing machine simulation and \(O(\log^2 n)\) assembly of \(n\times n\) squares with high probability. Our results show a sharp contrast in achievable tile complexity at temperature 1 if either growth into the third dimension or a small probability of error are permitted. Motivated by applications in nanotechnology and molecular computing, and the plausibility of implementing 3 dimensional self-assembly systems, our techniques may provide the needed power of temperature 2 systems, while at the same time avoiding the experimental challenges faced by those systems.
Authors
Matthew Cook, Yunhui Fu, Robert Schweller
File
Temperature 1 Self-Assembly: Deterministic Assembly in 3D and Probabilistic Assembly in 2D.pdf