2015/03/15 by Jacob Hendricks, Hendricks, Jacob, Matthew J. Patitz +3
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Cellular Automata and Applications #Computational Geometry (cs.CG) #DNA and Biological Computing #Emerging Technologies (cs.ET) #FOS: Computer and information sciences #Stochastic processes and statistical mechanics #cs.CG #cs.ET
paper · pdf · doi:10.48550/arxiv.1503.04502
openalex publication_date 2015/03/15 · arxiv created 2015/03/16 · arxiv updated 2015/03/17 · openalex created_date 2022/10/04 · openalex updated_date 2026/07/28
In this paper, we extend existing results about simulation and intrinsic universality in a model of tile-based self-assembly. Namely, we work within the 2-Handed Assembly Model (2HAM), which is a model of self-assembly in which assemblies are formed by square tiles that are allowed to combine, using glues along their edges, individually or as pairs of arbitrarily large assemblies in a hierarchical manner, and we explore the abilities of these systems to simulate each other when the simulating systems have a higher "temperature" parameter, which is a system wide threshold dictating how many glue bonds must be formed between two assemblies to allow them to combine. It has previously been shown that systems with lower temperatures cannot simulate arbitrary systems with higher temperatures, and also that systems at some higher temperatures can simulate those at particular lower temperatures, creating an infinite set of infinite hierarchies of 2HAM systems with strictly increasing simulation power within each hierarchy. These previous results relied on two different definitions of simulation, one (strong simulation) seemingly more restrictive than the other (standard simulation), but which have previously not been proven to be distinct. Here we prove distinctions between them by first fully characterizing the set of pairs of temperatures such that the high temperature systems are intrinsically universal for the lower temperature systems (i.e. one tile set at the higher temperature can simulate any at the lower) using strong simulation. This includes the first impossibility result for simulation downward in temperature. We then show that lower temperature systems which cannot be simulated by higher temperature systems using the strong definition, can in fact be simulated using the standard definition, proving the distinction between the types of simulation.