Strict self-assembly of discrete self-similar fractals

Strict Self-Assembly of Discrete Self-Similar Fractals

Discrete self-similar fractals (DSSFs) are infinite aperiodic shapes that have received much interest in the domain of tile self-assembly. For instance, in it was shown that the infinite Sierpinski triangle cannot strictly self-assemble in the aTAM, but a fibered approximation can be. In it was shown that additional DSSFs cannot strictly self-assemble in the aTAM, but their fibered approximations can. Just a few of the additional results related to DSSFs, including more impossibility results, other approximations, and strict self-assembly in other models can be found in .

While in it was conjectured that no DSSF can strictly self-assemble in the aTAM, that conjecture has been proven false. In fact, two different methods have been demonstrated for developing aTAM systems that strictly self-assemble DSSFs, and the following two sections give overviews of each.

DSSFs via Self-describing circuits

TODO: describe the work by Florent Becker in

DSSFs via Quines

A standard aTAM system is an aTAM system that is directed, has no glue mismatches in its terminal assembly, and has no tiles that attach using glues on opposite sides of the tile as input glues. It was shown that the class of standard aTAM systems is intrinsically universal.

A quine is a computer program that, with no input, outputs a full copy of its own source code. In the context of the aTAM, a quine was defined, with respect to an intrinsically universal tile set \(U\), as a system \(\mathcal{Q} = (Q, \sigma, \tau)\) that begins from a single seed tile, (i.e. \(|\sigma| = 1)\) and grows into a terminal assembly, \(\alpha_\mathcal{Q}\), that is correctly formatted to be the seed assembly for a system \(\mathcal{S} = (U,\alpha_\mathcal{Q}, \tau)\) that uses \(U\) and its associated representation function \(R\) such that \(R\) maps \(\alpha_\mathcal{Q}\) to \(\sigma\) (i.e. \(R(\alpha_\mathcal{Q}) = \sigma)\) and \(\mathcal{S}\) intrinsically simulates \(\mathcal{Q}\). This requires that the terminal assembly of \(\mathcal{Q}\), \(\alpha_\mathcal{Q}\), contains an encoding of the entire system in the glues on its perimeter, in a format that is compatible with a system that can simulate it (i.e. in a glue lookup table), which is analogous to a computer program printing out its own source code (since that code must be executable by some program, namely the program executing it to cause the code to be output).

First, a quine \(\mathcal{Q}\) was given with respect to the tile set \(U\) that was shown to be intrinsically universal for standard systems (meaning that \(\mathcal{Q}\) is a standard aTAM system). Then, the following slight modifications were made:

• The tile set \(U\) was added to \(\mathcal{Q}\) so that the tiles of \(U\) are also encoded in the glue lookup table. This was shown to cause the simulation to continue at an infinite series of increasingly larger scale factors, similar to the recursive structure of the stages of a DSSF.
• In order to make the DSSF non-trivial by having fractal dimension between 1 and 2, it was then shown how \(\mathcal{Q}\) and the macrotiles of the simulation could be modified to have arbitrarily large proportions of empty space. In this way, it is possible to have the resulting system be a DSSF was target fractal dimension up to any specified \(0 < \epsilon < 1\).

Tile sets and software

Tile sets for the IU set \(U\), the quine, and the DSSF generating system were created. They, along with software used to generate them, can be downloaded here:

Software to generate aTAM quine and DSSF tile sets and test systems (The latest version can be found at the bottom of the list of packages.)