Building infinite shapes

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 , 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 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.

The tile types which form the border of the counter

A portion of the approximate Sierpinski triangle of

A portion of the approximate Sierpinski triangle of

Various patterns corresponding to the Sierpinski triangle

Despite the impossibility of strictly self-assembling the discrete Sierpinski triangle, in 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 , the fibering construction was extended to an entire class of fractals. Along a similar line, Shutters and Lutz 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 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 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.

How to Build the Discrete Sierpinski Triangle in the STAM

In a paper by Hendricks, Olsen, Patitz, Rogers, and Thomas, it is shown that the infinite Sierpinski triangle can be assembled in the STAM. Their result is as follows.

Theorem 1. There exists an STAM system T∆ = (T, 1) such that T∆ has exactly one infinite terminal supertile α∆, and dom (α∆) = S∆, i.e. is exactly the discrete Sierpinski triangle, and for all α ∈ A✷[T ] such that α 6= α∆, |dom (α)| ≤ 4.

This construction uses the ability of signal passing tiles in the STAM to turn off their glues and allow for pieces of the assembly to break away after they helped to assemble pieces of the shape.