Title: Verification and Computation in Restricted Tile Automata
Authors: David Caballero, Timothy Gomez, Robert Schweller, and Tim Wylie
Conference: The 26th International Conference on DNA Computing and Molecular Programming (DNA’20), 2020
Abstract:
Many models of self-assembly have been shown to be capable of performing computation. Tile Automata was recently introduced combining features of both Celluar Automata and the 2-Handed Model of self-assembly both capable of universal computation. In this work we study the complexity of Tile Automata utilizing features inherited from the two models mentioned above. We first present a construction for simulating Turing Machines that performs both covert and fuel efficient computation. We then explore the capabilities of limited Tile Automata systems such as 1-Dimensional systems (all assemblies are of height $1$) and freezing Systems (tiles may not repeat states). Using these results we provide a connection between the problem of finding the largest uniquely producible assembly using $n$ states and the busy beaver problem for non-freezing systems and provide a freezing system capable of uniquely assembling an assembly whose length is exponential in the number of states of the system. We finish by exploring the complexity of the Unique Assembly Verification problem in Tile Automata with different limitations such as freezing and systems without the power of detachment.