The Simulation Powers and Limitations of Higher Temperature Hierarchical Self-Assembly Systems

• Autorzy: Hendricks J. , Patitz M. , Rogers T. A.

Identyfikatory

DOI

10.3233/FI-2017-1579

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

turing machines; equivalence; arbitrary constants; cellular automata; temperature; graph theory

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 155, nr 1/2
• Strony: 131--162
• Opis fizyczny: Bibliogr. 23 poz., rys.

Twórcy

autor

Hendricks J.

• Department of Computer Science and Information Systems, University of Wisconsin-River Falls, River Falls, WI, USA

autor

Patitz M.

• Computer Science & Computer Engineering, University of Arkansas, Fayetteville, AR 72701, USA

autor

Rogers T. A.

• Computer Science & Computer Engineering, University of Arkansas, Fayetteville, AR 72701, USA

Bibliografia

• [1] Cannon S, Demaine ED, Demaine ML, Eisenstat S, Patitz MJ, Schweller RT, et al. Two Hands Are Better Than One (up to constant factors): Self-Assembly In The 2HAM vs. aTAM. In: Portier N, Wilke T, editors. STACS. vol. 20 of LIPIcs. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik; 2013. p. 172–184. URL http://dblp.uni-trier.de/db/conf/stacs/stacs2013.html#CannonDDEPSSW13.
• [2] Winfree E. Algorithmic Self-Assembly of DNA. California Institute of Technology; 1998. ISBN:0-591-96599-2.
• [3] Doty D, Lutz JH, Patitz MJ, Schweller RT, Summers SM, Woods D. The tile assembly model is intrinsically universal. In: Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science. FOCS 2012; 2012. p. 302–310. arXiv:1111.3097v2.
• [4] Demaine ED, Patitz MJ, Rogers TA, Schweller RT, Summers SM, Woods D. The two-handed assembly model is not intrinsically universal. In: 40th International Colloquium on Automata, Languages and Programming, ICALP 2013, Riga, Latvia, July 8-12, 2013. Lecture Notes in Computer Science. Springer; 2013. URI http://hdl.handle.net/1721.1/86205.
• [5] Meunier PE, Patitz MJ, Summers SM, Theyssier G, Winslow A, Woods D. Intrinsic universality in tile self-assembly requires cooperation. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), Portland, OR, USA, January 5-7, 2014, 2014. p. 752–771.
• [6] Hendricks J, Patitz MJ. On the Equivalence of Cellular Automata and the Tile Assembly Model. In: Neary T, Cook M, editors. Proceedings Machines, Computations and Universality 2013, Zürich, Switzerland, 9/09/2013-11/09/2013. vol. 128 of Electronic Proceedings in Theoretical Computer Science. Open Publishing Association; 2013. p. 167–189. doi:10.4204/EPTCS.128.21.
• [7] Hendricks J, Padilla JE, Patitz MJ, Rogers TA. Signal Transmission across Tile Assemblies: 3D Static Tiles Simulate Active Self-assembly by 2D Signal-Passing Tiles. In: Soloveichik D, Yurke B, editors. DNA Computing and Molecular Programming. vol. 8141 of Lecture Notes in Computer Science. Springer International Publishing; 2013. p. 90–104. URL http://dx.doi.org/10.1007/978-3-319-01928-4\_7.
• [8] Woods D. Intrinsic universality and the computational power of self-assembly. In: MCU: Proceedings of Machines, Computations and Universality. vol. 128. Univ. of Zürich, Switzerland. Sept. 9-12: Open Publishing Association; 2013. p. 16–22. URL http://dx.doi.org/10.4204/EPTCS.128.5dx.doi.org/10.4204/EPTCS.128.5.
• [9] Hendricks J, Patitz MJ, Rogers TA, Summers SM. The Power of Duples (in Self-Assembly): It’s Not So Hip to Be Square. In: Computing and Combinatorics-20th International Conference, (COCOON) 2014, Atlanta, GA, USA, August 4-6, 2014. Proceedings; 2014. p. 215–226. ISBN:978-3-319-08783-2, 978-3-319-08782-5.
• [10] Hendricks J, Patitz MJ, Rogers TA. Doubles and Negatives are Positive (in Self-Assembly). In: Proceeding of Unconventional Computation and Natural Computation 2014 (UCNC 2014), University of Western Ontario, London, Ontario, Canada, 7/14/2014-7/18/2014; 2014. p. 190–202. doi:10.1007/978-3-319-08123-6_16.
• [11] Mazoyer J, Rapaport I. Inducing an order on cellular automata by a grouping operation. In: STACS 98. Springer; 1998. p. 116–127.
• [12] Durand B, Róka Z. The game of life: universality revisited. In: Delorme M, Mazoyer J, editors. Cellular Automata. Kluwer; 1999. doi:10.1007/978-94-015-9153-9_2.
• [13] Delorme M, Mazoyer J, Ollinger N, Theyssier G. Bulking I: an abstract theory of bulking. Theoretical Computer Science. 2011;412(30):3866–3880. URL https://doi.org/10.1016/j.tcs.2011.02.023.
• [14] Delorme M, Mazoyer J, Ollinger N, Theyssier G. Bulking II: Classifications of cellular automata. Theoretical Computer Science. 2011;412(30):3881–3905. URL https://doi.org/10.1016/j.tcs.2011.02.024.
• [15] Goles Ch E, Meunier PE, Rapaport I, Theyssier G. Communication complexity and intrinsic universality in cellular automata. Theoretical Computer Science. 2011;412(1-2):2–21. URL https://doi.org/10.1016/j.tcs.2010.10.005.
• [16] Ollinger N. Intrinsically Universal Cellular Automata. In: The Complexity of Simple Programs, in Electronic Proceedings in Theoretical Computer Science. vol. 1; 2008. p. 199–204.
• [17] Ollinger N, Richard G. Four states are enough! Theoretical Computer Science. 2011;412(1):22–32.
• [18] Arrighi P, Schabanel N, Theyssier G. Intrinsic Simulations between Stochastic Cellular Automata. Computing Research Repository; 2012. 1208.2763. URL http://arxiv.org/abs/1208.2763.
• [19] Arrighi P, Grattage J. Intrinsically universal n-dimensional quantum cellular automata. Journal of Computer and System Sciences. 2012;78(6):1883–1898. URL https://doi.org/10.1016/j.jcss.2011.12.008.
• [20] Cheng Q, Aggarwal G, Goldwasser MH, Kao MY, Schweller RT, de Espanés PM. Complexities for Generalized Models of Self-Assembly. SIAM Journal on Computing. 2005;34(6):1493–1515. doi:10.1137/S0097539704445202.
• [21] Demaine ED, Demaine ML, Fekete SP, Ishaque M, Rafalin E, Schweller RT, et al. Staged self-assembly: nanomanufacture of arbitrary shapes with O(1) glues. Natural Computing. 2008;7(3):347–370. doi:10.1007/s11047-008-9073-0.
• [22] Lathrop JI, Lutz JH, Summers SM. Strict Self-Assembly of Discrete Sierpinski Triangles. Theoretical Computer Science. 2009;410(4-5):384–405. URL https://doi.org/10.1016/j.tcs.2008.09.062.
• [23] Rothemund PWK. Theory and Experiments in Algorithmic Self-Assembly. University of Southern California; 2001. ISBN:0-493-85360-X.