Tag: dna

Posted on

Verification and Computation in Restricted Tile Automata

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.

Posted on

Freezing Simulates Non-freezing Tile Automata

Title: Freezing Simulates Non-freezing Tile Automata

Authors: Cameron Chalk, Austin Luchsinger, Eric Martinez, Robert Schweller, Andrew Winslow, and Tim Wylie
Abstract:

Citation: Proc. of 24th Inter. Conf. on DNA Computing and Molecular Programming (DNA’18)
Bibtex:
PDF:

Posted on

Concentration Independent Random Number Generation in Tile Self-Assembly

Title: Concentration Independent Random Number Generation in Tile Self-Assembly
Authors:
In this paper we introduce the robust random number generation problem where the goal is to design an abstract tile assembly system (aTAM system) whose terminal assemblies can be split into n partitions such that a resulting assembly of the system lies within each partition with probability 1/n , regardless of the relative concentration assignment of the tile types in the system. First, we show this is possible for n=2n=2 (a robust fair coin flip ) within the aTAM, and that such systems guarantee a worst case O(1)O(1) space usage. We accompany our primary construction with variants that show trade-offs in space complexity, initial seed size, temperature, tile complexity, bias, and extensibility, and also prove some negative results. As an application, we combine our coin-flip system with a result of Chandran, Gopalkrishnan, and Reif to show that for any positive integer n , there exists a O(log⁡n)O(log⁡n) tile system that assembles a constant-width linear assembly of expected length n for any concentration assignment. We then extend our robust fair coin flip result to solve the problem of robust random number generation in the aTAM for all n. Two variants of robust random bit generation solutions are presented: an unbounded space solution and a bounded space solution which incurs a small bias. Further, we consider the harder scenario where tile concentrations change arbitrarily at each assembly step and show that while this is not possible in the aTAM, the problem can be solved by exotic tile assembly models from the literature.

Bibtex:
PDF:
URL: