{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,2]],"date-time":"2024-08-02T19:40:19Z","timestamp":1722627619558},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,2,22]],"date-time":"2022-02-22T00:00:00Z","timestamp":1645488000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,2,22]],"date-time":"2022-02-22T00:00:00Z","timestamp":1645488000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["772766"],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001602","name":"Science Foundation Ireland","doi-asserted-by":"crossref","award":["18\/ercs\/5746"],"id":[{"id":"10.13039\/501100001602","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001633","name":"National University of Ireland Maynooth","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001633","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Nat Comput"],"published-print":{"date-parts":[[2024,6]]},"abstract":"Abstract<\/jats:title>Molecular robotics is challenging, so it seems best to keep it simple. We consider an abstract molecular robotics model based on simple folding instructions that execute asynchronously. Turning Machines are a simple 1D to 2D folding model, also easily generalisable to 2D to 3D folding. A Turning Machine starts out as a line of connected monomers in the discrete plane, each with an associated turning number. A monomer turns relative to its neighbours, executing a unit-distance translation that drags other monomers along with it, and through collective motion the initial set of monomers eventually folds into a programmed shape. We provide a suite of tools for reasoning about Turning Machines by fully characterising their ability to execute line rotations: executing an almost-full line rotation of $$5\\pi \/3$$<\/jats:tex-math>\n \n 5<\/mml:mn>\n \u03c0<\/mml:mi>\n \/<\/mml:mo>\n 3<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> radians is possible, yet a full $$2\\pi$$<\/jats:tex-math>\n \n 2<\/mml:mn>\n \u03c0<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> rotation is impossible. Furthermore, line rotations up to $$5\\pi \/3$$<\/jats:tex-math>\n \n 5<\/mml:mn>\n \u03c0<\/mml:mi>\n \/<\/mml:mo>\n 3<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> are executed efficiently, in $$O(\\log n)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> expected time in our continuous time Markov chain time model. We then show that such line-rotations represent a fundamental primitive in the model, by using them to efficiently and asynchronously fold shapes. In particular, arbitrarily large zig-zag-rastered squares and zig-zag paths are foldable, as are y<\/jats:italic>-monotone shapes albeit with error (bounded by perimeter length). Finally, we give shapes that despite having paths that traverse all their points, are in fact impossible to fold, as well as techniques for folding certain classes of (scaled) shapes without error. Our approach relies on careful geometric-based analyses of the feats possible and impossible by a very simple robotic system, and pushes conceptional hardness towards mathematical analysis and away from molecular implementation.<\/jats:p>","DOI":"10.1007\/s11047-022-09880-8","type":"journal-article","created":{"date-parts":[[2022,2,22]],"date-time":"2022-02-22T06:03:38Z","timestamp":1645509818000},"page":"407-430","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Turning machines: a simple algorithmic model for molecular robotics"],"prefix":"10.1007","volume":"23","author":[{"given":"Irina","family":"Kostitsyna","sequence":"first","affiliation":[]},{"ORCID":"http:\/\/orcid.org\/0000-0003-0960-3687","authenticated-orcid":false,"given":"Cai","family":"Wood","sequence":"additional","affiliation":[]},{"given":"Damien","family":"Woods","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,2,22]]},"reference":[{"issue":"6\u20137","key":"9880_CR1","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1016\/j.comgeo.2008.11.003","volume":"42","author":"G Aloupis","year":"2009","unstructured":"Aloupis G, Collette S, Damian M, Demaine ED, Flatland R, Langerman S, O\u2019Rourke J, Ramaswami S, Sacrist\u00e1n V, Wuhrer S (2009) Linear reconfiguration of cube-style modular robots. Comput Geom 42(6\u20137):652\u2013663","journal-title":"Comput Geom"},{"doi-asserted-by":"crossref","unstructured":"Aloupis G, Collette S, Demaine ED, Langerman S, Sacrist\u00e1n V, Wuhrer S (2008) Reconfiguration of cube-style modular robots using O(log n) parallel moves. In: International symposium on algorithms and computation, pp 342\u2013353. Springer","key":"9880_CR2","DOI":"10.1007\/978-3-540-92182-0_32"},{"doi-asserted-by":"crossref","unstructured":"Chen H-L, Doty D, Holden D, Thachuk C, Woods D, Yang C-T (2014a) Fast algorithmic self-assembly of simple shapes using random agitation. In: DNA20: the 20th international conference on DNA computing and molecular programming. LNCS, vol 8727, pp 20\u201336, Kyoto, Japan, September 2014. Springer. Full version: arXiv:1409.4828","key":"9880_CR3","DOI":"10.1007\/978-3-319-11295-4_2"},{"issue":"2","key":"9880_CR4","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/s11047-014-9432-y","volume":"14","author":"M Chen","year":"2014","unstructured":"Chen M, Xin D, Woods D (2014) Parallel computation using active self-assembly. Nat Comput 14(2):225\u2013250","journal-title":"Nat Comput"},{"issue":"4","key":"9880_CR5","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1109\/TRO.2011.2132951","volume":"27","author":"KC Cheung","year":"2011","unstructured":"Cheung KC, Demaine ED, Bachrach JR, Griffith S (2011) Programmable assembly with universally foldable strings (moteins). IEEE Trans Robot 27(4):718\u2013729","journal-title":"IEEE Trans Robot"},{"issue":"4","key":"9880_CR6","doi-asserted-by":"publisher","first-page":"743","DOI":"10.1007\/s11047-018-9695-9","volume":"17","author":"Y-R Chin","year":"2018","unstructured":"Chin Y-R, Tsai J-T, Chen H-L (2018) A minimal requirement for self-assembly of lines in polylogarithmic time. Nat Comput 17(4):743\u2013757","journal-title":"Nat Comput"},{"issue":"2","key":"9880_CR7","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1007\/s00454-010-9262-3","volume":"44","author":"R Connelly","year":"2010","unstructured":"Connelly R, Demaine ED, Demaine ML, Fekete SP, Langerman S, Mitchell JSB, Rib\u00f3 A, Rote G (2010) Locked and unlocked chains of planar shapes. Discrete Comput Geometry 44(2):439\u2013462","journal-title":"Discrete Comput Geometry"},{"doi-asserted-by":"crossref","unstructured":"Dabby N, Chen H-L (2012) Active self-assembly of simple units using an insertion primitive. In: SODA: the 24th annual ACM-SIAM symposium on discrete algorithms, pp 1526\u20131536, Jan 2012","key":"9880_CR8","DOI":"10.1137\/1.9781611973105.110"},{"issue":"18","key":"9880_CR9","doi-asserted-by":"publisher","first-page":"4165","DOI":"10.1242\/dev.01938","volume":"132","author":"RE Dawes-Hoang","year":"2005","unstructured":"Dawes-Hoang RE, Parmar KM, Christiansen AE, Phelps CB, Brand AH, Wieschaus EF (2005) Folded gastrulation, cell shape change and the control of myosin localization. Development 132(18):4165\u20134178","journal-title":"Development"},{"doi-asserted-by":"crossref","unstructured":"Demaine ED, Hendricks J, Olsen M, Patitz MJ, Rogers TA, Schabanel N, Seki S, Thomas H (2018) Know when to fold\u2019em: self-assembly of shapes by folding in oritatami. In: DNA: international conference on DNA computing and molecular programming, pp 19\u201336. Springer","key":"9880_CR10","DOI":"10.1007\/978-3-030-00030-1_2"},{"unstructured":"Geary C, Meunier P\u00c9, Schabanel N, Seki S (2016) Programming biomolecules that fold greedily during transcription. In: MFCS: the 41st international symposium on mathematical foundations of computer science. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik","key":"9880_CR11"},{"key":"9880_CR12","first-page":"1","volume":"19","author":"R Gmyr","year":"2019","unstructured":"Gmyr R, Hinnenthal K, Kostitsyna I, Kuhn F, Rudolph D, Scheideler C, Strothmann T (2019) Forming tile shapes with simple robots. Nat Comput 19:1\u201316","journal-title":"Nat Comput"},{"volume-title":"Concrete mathematics","year":"1989","author":"RL Graham","unstructured":"Graham RL, Knuth RL, Patashnik O (1989) Concrete mathematics. Addison-Wesley, Boston","key":"9880_CR13"},{"key":"9880_CR14","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1007\/s00453-015-0085-8","volume":"77","author":"B Hescott","year":"2017","unstructured":"Hescott B, Malchik C, Winslow A (2017) Tight bounds for active self-assembly using an insertion primitive. Algorithmica 77:537\u2013554","journal-title":"Algorithmica"},{"doi-asserted-by":"crossref","unstructured":"Hescott B, Malchik C, Winslow A (2018) Non-determinism reduces construction time in active self-assembly using an insertion primitive. In: COCOON: the 24th international computing and combinatorics conference, pp 626\u2013637. Springer","key":"9880_CR15","DOI":"10.1007\/978-3-319-94776-1_52"},{"doi-asserted-by":"crossref","unstructured":"Hou C-Y, Chen H-L (2019) An exponentially growing nubot system without state changes. In: International conference on unconventional computation and natural computation, pp 122\u2013135. Springer","key":"9880_CR16","DOI":"10.1007\/978-3-030-19311-9_11"},{"issue":"7228","key":"9880_CR17","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1038\/nature07522","volume":"457","author":"AC Martin","year":"2008","unstructured":"Martin AC, Kaschube M, Wieschaus EF (2008) Pulsed contractions of an actin\u2013myosin network drive apical constriction. Nature 457(7228):495\u2013499","journal-title":"Nature"},{"key":"9880_CR18","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/j.jcss.2018.12.001","volume":"102","author":"O Michail","year":"2019","unstructured":"Michail O, Skretas G, Spirakis PG (2019) On the transformation capability of feasible mechanisms for programmable matter. J Comput Syst Sci 102:18\u201339","journal-title":"J Comput Syst Sci"},{"key":"9880_CR19","first-page":"1","volume":"21","author":"H Ramezani","year":"2019","unstructured":"Ramezani H, Dietz H (2019) Building machines with DNA molecules. Nat Rev Genet 21:1\u201322","journal-title":"Nat Rev Genet"},{"doi-asserted-by":"crossref","unstructured":"Woods D, Chen H-L, Goodfriend S, Dabby N, Winfree E, Yin P (2013) Active self-assembly of algorithmic shapes and patterns in polylogarithmic time. In: ITCS: the 4th conference on innovations in theoretical computer science, pp 353\u2013354. ACM, 2013. Full version: arXiv:1301.2626 [cs.DS]","key":"9880_CR20","DOI":"10.1145\/2422436.2422476"}],"container-title":["Natural Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-022-09880-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11047-022-09880-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-022-09880-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,2]],"date-time":"2024-08-02T19:05:39Z","timestamp":1722625539000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11047-022-09880-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,22]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["9880"],"URL":"http:\/\/dx.doi.org\/10.1007\/s11047-022-09880-8","relation":{},"ISSN":["1567-7818","1572-9796"],"issn-type":[{"type":"print","value":"1567-7818"},{"type":"electronic","value":"1572-9796"}],"subject":[],"published":{"date-parts":[[2022,2,22]]},"assertion":[{"value":"30 September 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 February 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}
