  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.
