2009/04/10 by Aaron Sterling, Sterling, Aaron
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · #Cellular Automata and Applications #Computational Complexity (cs.CC) #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Modular Robots and Swarm Intelligence #Other Computer Science (cs.OH) #cs.CC #cs.DS #cs.OH
paper · pdf · doi:10.48550/arxiv.0904.1630
I am withdrawing all work I would like to polish before resubmitting, including this paper. Several typos fixed
openalex publication_date 2009/04/10 · arxiv created 2011/07/20 · arxiv updated 2011/07/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We demonstrate existence of a tile assembly system that self-assembles the statistically self-similar Sierpinski Triangle in the Winfree-Rothemund Tile Assembly Model. This appears to be the first paper that considers self-assembly of a random fractal, instead of a deterministic fractal or a finite, bounded shape. Our technical contributions include a way to remember, and use, unboundedly-long prefixes of an infinite coding sequence at each stage of fractal construction; a tile assembly mechanism for nested recursion; and a definition of "almost-everywhere local determinism," to describe a tileset whose assembly is locally determined, conditional upon a zeta-dimension zero set of (infinitely many) "input" tiles. This last is similar to the definition of randomized computation for Turing machines, in which an algorithm is deterministic relative to an oracle sequence of coin flips that provides advice but does not itself compute. Keywords: tile self-assembly, statistically self-similar Sierpinski Triangle.