View source for Strict self-assembly of discrete self-similar fractals

__TOC__

==Strict Self-Assembly of Discrete Self-Similar Fractals==

[[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 <ref name=jSSADST/> it was shown that the infinite Sierpinski triangle cannot strictly self-assemble in the aTAM, but a ''fibered'' approximation can be. In <ref name=jSADSSF/> 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 <ref name=LutzShutters12/><ref name=KautzShutters11/><ref name=SFractals/><ref name=chalk2016strict/><ref name=hader2023fractalNACO/>.

While in <ref name=hader2023fractalNACO/> 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 <ref name=FlorentFractals/>

==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 [[Intrinsic_Universality_of_the_aTAM | 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:

[http://self-assembly.net/software/aTAM_quine/ 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==

<references>

<ref name =FlorentFractals><bibtex>
@misc{FlorentFractals,
      title={Strict Self-Assembly of Discrete Self-Similar Fractal Shapes}, 
      author={Florent Becker},
      year={2024},
      eprint={2405.08548},
      archivePrefix={arXiv},
      primaryClass={id='cs.DM' full_name='Discrete Mathematics' is_active=True alt_name=None in_archive='cs' is_general=False description='Covers combinatorics, graph theory, applications of probability. Roughly includes material in ACM Subject Classes G.2 and G.3.'}
}
</bibtex></ref>


<ref name =jSSADST><bibtex>
@article{jSSADST,
  author =   "James I. Lathrop and Jack H. Lutz and Scott M. Summers",
  title =    "Strict Self-Assembly of Discrete Sierpinski Triangles",
  journal = "Theoretical Computer Science",
  volume = "410",
  year = "2009",
  pages = "384--405"
}
note = "Preliminary version appeared in Proceedings of The Third Conference on Computability in Europe (Siena, Italy, June 18-23, 2007)"
</bibtex></ref>

<ref name =jSADSSF><bibtex>
@article{jSADSSF,
  author    = {Matthew J. Patitz and Scott M. Summers},
  title     = {Self-assembly of discrete self-similar fractals},
  journal   = {Natural Computing},
  volume = {1}
  year      = {2010},
  pages     = {135--172},

}
</bibtex></ref>


<ref name =LutzShutters12><bibtex>
@article{LutzShutters12,
  author    = {Jack H. Lutz and Brad Shutters},
  title     = {Approximate self-assembly of the sierpinski triangle},
  journal   = {Theory Comput. Syst.},
  volume = {51}
  number {3}
  year      = {2012},
  pages     = {372--400},

}
</bibtex></ref>


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

}
</bibtex></ref>


<ref name=SFractals><bibtex>
@article{SFractals,
    title={Hierarchical Self-Assembly of Fractals with Signal-Passing Tiles},
    author={Hendricks, Jacob and Olsen, Meagan and Patitz, Matthew and Rogers, Trent and Thomas, Hadley},
    year = {2017},
    month = {11},
    pages = {},
    volume = {17},
    journal = {Natural Computing},
    doi = {10.1007/s11047-017-9663-9}
}
</bibtex></ref>


<ref name=chalk2016strict><bibtex>
@article{chalk2016strict,
  title={Strict self-assembly of fractals using multiple hands},
  author={Chalk, Cameron T and Fernandez, Dominic A and Huerta, Alejandro and Maldonado, Mario A and Schweller, Robert T and Sweet, Leslie},
  journal={Algorithmica},
  volume={76},
  number={1},
  pages={195--224},
  year={2016},
  publisher={Springer}
}
</bibtex></ref>


<ref name=hader2023fractalNACO><bibtex>
@article{hader2023fractalNACO,
  title={Fractal dimension of assemblies in the abstract tile assembly model},
  author={Hader, Daniel and Patitz, Matthew J and Summers, Scott M},
  journal={Natural Computing},
  pages={1--16},
  year={2023},
  publisher={Springer}
}
</bibtex></ref>


</references>

[[Category:Results in the aTAM]]
[[Category:Self-assembly]]
[[Category: Simulation in Self-assembly]]