Strict self-assembly of discrete self-similar fractals
Contents
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 [1] it was shown that the infinite Sierpinski triangle cannot strictly self-assemble in the aTAM, but a fibered approximation can be. In [2] 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 [3][4][5][6][7].
While in [7] 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 [8]
DSSFs via Quines
TODO: describe the work by Hader and Patitz, in progress...
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:
DSSF tile sets and generation software (The latest version can be found at the bottom of the list of packages.)
References
- ↑
James I. Lathrop, Jack H. Lutz, Scott M. Summers - Strict Self-Assembly of Discrete Sierpinski Triangles
- Theoretical Computer Science 410:384--405,2009
- BibtexAuthor : James I. Lathrop, Jack H. Lutz, Scott M. Summers
Title : Strict Self-Assembly of Discrete Sierpinski Triangles
In : Theoretical Computer Science -
Address :
Date : 2009
- ↑
Matthew J. Patitz, Scott M. Summers - Self-assembly of discrete self-similar fractals
- ↑
Jack H. Lutz, Brad Shutters - Approximate self-assembly of the sierpinski triangle
- ↑
Steven M. Kautz, Brad Shutters - Self-assembling rulers for approximating generalized sierpinski carpets
- Lecture Notes in Computer Science 6842:284--296,2011
- BibtexAuthor : Steven M. Kautz, Brad Shutters
Title : Self-assembling rulers for approximating generalized sierpinski carpets
In : Lecture Notes in Computer Science -
Address :
Date : 2011
- ↑
Hendricks, Jacob, Olsen, Meagan, Patitz, Matthew, Rogers, Trent, Thomas, Hadley - Hierarchical Self-Assembly of Fractals with Signal-Passing Tiles
- ↑
Chalk, Cameron T, Fernandez, Dominic A, Huerta, Alejandro, Maldonado, Mario A, Schweller, Robert T, Sweet, Leslie - Strict self-assembly of fractals using multiple hands
- ↑ 7.0 7.1
Hader, Daniel, Patitz, Matthew J, Summers, Scott M - Fractal dimension of assemblies in the abstract tile assembly model
- ↑
Florent Becker - Strict Self-Assembly of Discrete Self-Similar Fractal Shapes