Strict self-assembly of discrete self-similar fractals

From self-assembly wiki
Revision as of 15:24, 27 June 2024 by \('"2\)'"7
(\(1) \)2 | \(3 (\)4) | \(5 (\)6)
Jump to navigation Jump to search

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:

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


References

  1. 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. 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. 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. 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
  5. Hendricks, Jacob, Olsen, Meagan, Patitz, Matthew, Rogers, Trent, Thomas, Hadley - Hierarchical Self-Assembly of Fractals with Signal-Passing Tiles
    Natural Computing 17, 11 2017
    Bibtex
    Author : Hendricks, Jacob, Olsen, Meagan, Patitz, Matthew, Rogers, Trent, Thomas, Hadley
    Title : Hierarchical Self-Assembly of Fractals with Signal-Passing Tiles
    In : Natural Computing -
    Address :
    Date : 11 2017
  6. Chalk, Cameron T, Fernandez, Dominic A, Huerta, Alejandro, Maldonado, Mario A, Schweller, Robert T, Sweet, Leslie - Strict self-assembly of fractals using multiple hands
    Algorithmica 76(1):195--224,2016
    Bibtex
    Author : Chalk, Cameron T, Fernandez, Dominic A, Huerta, Alejandro, Maldonado, Mario A, Schweller, Robert T, Sweet, Leslie
    Title : Strict self-assembly of fractals using multiple hands
    In : Algorithmica -
    Address :
    Date : 2016
  7. 7.0 7.1 Hader, Daniel, Patitz, Matthew J, Summers, Scott M - Fractal dimension of assemblies in the abstract tile assembly model
    Natural Computing pp. 1--16,2023
    Bibtex
    Author : Hader, Daniel, Patitz, Matthew J, Summers, Scott M
    Title : Fractal dimension of assemblies in the abstract tile assembly model
    In : Natural Computing -
    Address :
    Date : 2023
  8. Florent Becker - Strict Self-Assembly of Discrete Self-Similar Fractal Shapes
    ,2024
    Bibtex
    Author : Florent Becker
    Title : Strict Self-Assembly of Discrete Self-Similar Fractal Shapes
    In : -
    Address :
    Date : 2024