caa a22 4500 44584311X CHVBK 20180317145350.0 cr unu---uuuuu 170323e20110601xx s 000 0 eng 10.1007/s11047-010-9218-9 doi (NATIONALLICENCE)springer-10.1007/s11047-010-9218-9 Self-assembly of decidable sets [Elektronische Daten] [Matthew Patitz, Scott Summers] The theme of this paper is computation in Winfree's Abstract Tile Assembly Model (TAM). We first review a simple, well-known tile assembly system (the "wedge construction”) that is capable of universal computation. We then extend the wedge construction to prove the following result: if a set of natural numbers is decidable, then it and its complement's canonical two-dimensional representation self-assemble. This leads to a novel characterization of decidable sets of natural numbers in terms of self-assembly. Finally, we show that our characterization is robust with respect to various (restrictive) geometrical constraints. Springer Science+Business Media B.V., 2010 Computability nationallicence Tile assembly nationallicence Self-assembly nationallicence DNA computing nationallicence Decidability nationallicence Universality nationallicence Space complexity nationallicence Patitz Matthew Department of Computer Science, University of Texas-Pan American, 78539, Edinburg, TX, USA aut Summers Scott Department of Computer Science and Software Engineering, University of Wisconsin-Platteville, 53818, Platteville, WI, USA aut Natural Computing Springer Netherlands 10/2(2011-06-01), 853-877 1567-7818 10:2<853 2011 10 11047 https://doi.org/10.1007/s11047-010-9218-9 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s11047-010-9218-9 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Patitz Matthew Department of Computer Science, University of Texas-Pan American, 78539, Edinburg, TX, USA aut NATIONALLICENCE 700 1- Summers Scott Department of Computer Science and Software Engineering, University of Wisconsin-Platteville, 53818, Platteville, WI, USA aut NATIONALLICENCE 773 0- Natural Computing Springer Netherlands 10/2(2011-06-01), 853-877 1567-7818 10:2<853 2011 10 11047 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer