Difference between revisions of "Building infinite shapes"

From self-assembly wiki
Jump to navigation Jump to search
(References)
(References)
Line 111: Line 111:
 
   year      = {2012},
 
   year      = {2012},
 
   pages    = {372--400},
 
   pages    = {372--400},
 +
 +
}
 +
</bibtex></ref>
 +
</references>
 +
 +
<ref name =KautzShutters11><bibtex>
 +
@article{KautzShutters11,
 +
  author    = {Steven M. Kautz and Brad Shutters},
 +
  title    = {Self-assembling rulers for approximating generalized sierpinski carpets},
 +
  journal  = {Lecture Notes in Computer Science},
 +
  volume = {6842}
 +
  year      = {2011},
 +
  pages    = {284--296},
  
 
}
 
}

Revision as of 17:18, 11 June 2013

Building infinite shapes

As it has been shown that any finite shape can self-assemble in the aTAM, in order to test the limits of the model and find shapes which are impossible to self-assemble, it is necessary to look at infinite shapes. While the self-assembly of infinite shapes may not have typical practical (i.e. physical, laboratory) applications, the study provides insights into fundamental limitations of self-assembling systems, in particular regarding their ability to propagate information through the growth fronts of assemblies.

Due to their complex, aperiodic nature, discrete self-similar fractals have provided an interesting set of infinite shapes to explore. In [1], Lathrop, Lutz, and Summers showed that it is impossible for the discrete Sierpinski triangle (see first image in the figure below) to strictly self-assemble in the aTAM (at any temperature). Note that this is in contrast to the fact that it can weakly self-assemble, with a very simple tile set of 7 tile types. The proof relies on the fact that at each successive stage, as the stages of the fractal structure grow larger, each is connected to the rest of the assembly by a single tile. Since there are an infinite number of stages, all of different sizes, it is impossible for the single tiles connecting each of them to the assembly to transmit the information about how large the newly forming stage should be, and thus it is impossible for the fractal to self-assemble. Patitz and Summers [2] extended this proof technique to cover a class of similar fractals. It is conjectured by the author of this paper that no discrete self-similar fractal strictly self-assembles in the aTAM, but that remains an open question.

A portion of the discrete Sierpinski triangle
The tile types which form the border of the counter
Red cartouche
A portion of the approximate Sierpinski triangle of [1]
Red cartouche
A portion of the approximate Sierpinski triangle of [3]
Various patterns corresponding to the Sierpinski triangle

Despite the impossibility of strictly self-assembling the discrete Sierpinski triangle, in [1] it was shown that an approximation of that fractal, which the authors called the fibered Sierpinski triangle, does in fact strictly self-assemble. The fibered version is simply a rough visual approximation of the original but with one additional row and column of tiles added to each subsequent stage of the fractal during assembly (see second image in the above figure). Not only does the approximation look similar to the original, it was shown to have the same fractal (or zeta) dimension. In [2], the fibering construction was extended to an entire class of fractals. Along a similar line, Shutters and Lutz [3] showed that a different type of approximation of the Sierpinski triangle strictly self-assembles. This approximation also retains the same approximate appearance and fractal dimension, but instead of "spreading" out successive stages of the fractal with fibering, it utilizes a small portion of each hole in the definition of the shape (see third image in the above figure). In [4] Kautz and Shutters further extended this construction to an entire class of fractals.

Similar to their result about finite shapes mentioned in Section~\ref{sec:finite-shapes}, in [5] Bryans, Chiniforooshan, Doty, Kari, and Seki also showed a result about the power of nondeterminism in forming infinite structures, proving that there exist infinite shapes which can only self-assemble in non-deterministic systems. This means that no deterministic system is able to self-assemble such shapes, and is a further testament to the fact that nondeterminism is a source of increased power in the aTAM.

References

  1. 1.0 1.1 1.2 James I. Lathrop, Jack H. Lutz, Scott M. Summers - Strict Self-Assembly of Discrete Sierpinski Triangles
    Theoretical Computer Science 410:384--405,2009
    Bibtex
    Author : James I. Lathrop, Jack H. Lutz, Scott M. Summers
    Title : Strict Self-Assembly of Discrete Sierpinski Triangles
    In : Theoretical Computer Science -
    Address :
    Date : 2009
  2. 2.0 2.1 Matthew J. Patitz, Scott M. Summers - Self-assembly of discrete self-similar fractals
    Natural Computing 1:135--172,2010
    Bibtex
    Author : Matthew J. Patitz, Scott M. Summers
    Title : Self-assembly of discrete self-similar fractals
    In : Natural Computing -
    Address :
    Date : 2010
  3. 3.0 3.1 Jack H. Lutz, Brad Shutters - Approximate self-assembly of the sierpinski triangle
    Theory Comput. Syst. 51:372--400
    Bibtex
    Author : Jack H. Lutz, Brad Shutters
    Title : Approximate self-assembly of the sierpinski triangle
    In : Theory Comput. Syst. -
    Address :
    Date :
  4. Cite error: Invalid <ref> tag; no text was provided for refs named KautzShutters11
  5. Cite error: Invalid <ref> tag; no text was provided for refs named BryChiDotKarSek10

Cite error: <ref> tag with name "Winf98" defined in <references> is not used in prior text.
Cite error: <ref> tag with name "RotWin00" defined in <references> is not used in prior text.
Cite error: <ref> tag with name "RotWin00" defined in <references> is not used in prior text.
Cite error: <ref> tag with name "Roth01" defined in <references> is not used in prior text.

[1]

</references>

  1. Steven M. Kautz, Brad Shutters - Self-assembling rulers for approximating generalized sierpinski carpets
    Lecture Notes in Computer Science 6842:284--296,2011
    Bibtex
    Author : Steven M. Kautz, Brad Shutters
    Title : Self-assembling rulers for approximating generalized sierpinski carpets
    In : Lecture Notes in Computer Science -
    Address :
    Date : 2011