Abstract

We ask the question of how small a self-assembling set of tiles can be yet have interesting computational behaviour. We study this question in a model where supporting walls are provided as an input structure for tiles to grow along: we call it the Maze-Walking Tile Assembly Model. The model has a number of implementation prospects, one being DNA strands that attach to a DNA origami substrate. Intuitively, the model suggests a separation of signal routing and computation: the input structure (maze) supplies a routing diagram, and the programmer’s tile set provides the computational ability. We ask how simple the computational part can be.
We give two tiny tile sets that are computationally universal in the Maze-Walking Tile Assembly Model. The first has four tiles and simulates Boolean circuits by directly implementing NAND, NXOR and NOT gates. Our second tile set has 6 tiles and is called the Collatz tile set as it produces patterns found in binary/ternary representations of iterations of the Collatz function. Using computer search we find that the Collatz tile set is expressive enough to encode Boolean circuits using blocks of these patterns. These two tile sets give two different methods to find simple universal tile sets, and provide motivation for using pre-assembled maze structures as circuit wiring diagrams in molecular self-assembly based computing.

@InProceedings{cook_et_al:LIPIcs.DNA.27.8,
  author =	{Cook, Matthew and St\'{e}rin, Tristan and Woods, Damien},
  title =	{{Small Tile Sets That Compute While Solving Mazes}},
  booktitle =	{27th International Conference on DNA Computing and Molecular Programming (DNA 27)},
  pages =	{8:1--8:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-205-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{205},
  editor =	{Lakin, Matthew R. and \v{S}ulc, Petr},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14675},
  URN =		{urn:nbn:de:0030-drops-146758},
  doi =		{10.4230/LIPIcs.DNA.27.8},
  annote =	{Keywords: model of computation, self-assembly, small universal tile set, Boolean circuits, maze-solving}
}