{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T05:09:28Z","timestamp":1790744968521,"version":"4.1.0"},"reference-count":53,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2009,1]]},"abstract":"<jats:p>Self-assembly, the process by which objects autonomously come together to form complex structures, is omnipresent in the physical world. Recent experiments in self-assembly demonstrate its potential for the parallel creation of a large number of nanostructures, including possibly computers. A systematic study of self-assembly as a mathematical process has been initiated by L. Adleman and E. Winfree. The individual components are modeled as square tiles on the infinite two-dimensional plane. Each side of a tile is covered by a specific \u201cglue,\u201d and two adjacent tiles will stick iff they have matching glues on their abutting edges. Tiles that stick to each other may form various two-dimensional \u201cstructures\u201d such as squares and rectangles, or may cover the entire plane. In this paper we focus on a special type of structure, called a ribbon: a non-self-crossing rectilinear sequence of tiles on the plane, in which successive tiles are adjacent along an edge and abutting edges of consecutive tiles have matching glues. We prove that it is undecidable whether an arbitrary finite set of tiles with glues (infinite supply of each tile type available) can be used to assemble an infinite ribbon. While the problem can be proved undecidable using existing techniques if the ribbon is required to start with a given \u201cseed\u201d tile, our result settles the \u201cunseeded\u201d case, an open problem formerly known as the \u201cunlimited infinite snake problem.\u201d The proof is based on a construction, due to R. Robinson, of a special set of tiles that allow only aperiodic tilings of the plane. This construction is used to create a special set of directed tiles (tiles with arrows painted on the top) with the \u201cstrong plane-filling property\u201d\u2014a variation of the \u201cplane-filling property\u201d previously defined by J. Kari. A construction of \u201csandwich\u201d tiles is then used in conjunction with this special tile set, to reduce the well-known undecidable tiling problem to the problem of the existence of an infinite directed zipper (a special kind of ribbon). A \u201cmotif\u201d construction is then introduced that allows one tile system to simulate another by using geometry to represent glues. Using motifs, the infinite directed zipper problem is reduced to the infinite ribbon problem, proving the latter undecidable. An immediate consequence of our result is the undecidability of the existence of arbitrarily large structures self-assembled using tiles from a given tile set.<\/jats:p>","DOI":"10.1137\/080723971","type":"journal-article","created":{"date-parts":[[2009,3,20]],"date-time":"2009-03-20T18:30:51Z","timestamp":1237573851000},"page":"2356-2381","source":"Crossref","is-referenced-by-count":14,"title":["The Undecidability of the Infinite Ribbon Problem: Implications for Computing by Self-Assembly"],"prefix":"10.1137","volume":"38","author":[{"given":"Leonard","family":"Adleman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jarkko","family":"Kari","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lila","family":"Kari","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dustin","family":"Reishus","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Petr","family":"Sosik","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2009,3,20]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1145\/332833.332842"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1126\/science.7973651"},{"key":"R3","unstructured":"L. Adleman,\n                      Towards a Mathematical Theory of Self-Assembly\n                      , Technical report 00-722, Department of Computer Science, University of Southern California, Los Angeles, CA, 2000."},{"key":"R4","doi-asserted-by":"crossref","unstructured":"L. Adleman, Q. Cheng, A. Goel, and M. Huang,\n                      Running time and program size for self-assembled squares\n                      , in Proceedings of the ACM Symposium on Theory of Computing (STOC), 2001, pp. 740\u2013748.","DOI":"10.1145\/380752.380881"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"L. Adleman, Q. Cheng, A. Goel, M. Huang, D. Kempe, P. Moisset de Espanes, and P. Rothemund,\n                      Combinatorial optimization problems in self-assembly\n                      , in Proceedings of the ACM Symposium on Theory of Computing (STOC), 2002, pp. 23\u201332.","DOI":"10.1145\/509907.509913"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"L. Adleman, Q. Cheng, A. Goel, M. Huang, and H. Wasserman,\n                      Linear self-assemblies: Equilibria, entropy, and convergence rates\n                      , in Proceedings of the Sixth International Conference on Difference Equations Augsburg, Germany 2001: New Progress in Difference Equations, B. Aulbach, S. Elaydi, and G. Ladas, eds., CRC Press, Boca Raton, FL, 2004, pp. 51\u201360.","DOI":"10.1201\/9780203575437.ch4"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"L. Adleman, J. Kari, L. Kari, and D. Reishus,\n                      On the decidability of self-assembly of infinite ribbons\n                      , in Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), 2002, pp. 530\u2013537.","DOI":"10.1109\/SFCS.2002.1181977"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1021\/nl052038l"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1002\/anie.200501262"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1038\/35106533"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"R. Berger,\n                      The undecidability of the domino problem\n                      , Mem. Amer. Math. Soc. 66 (1966), pp. 1\u201372.","DOI":"10.1090\/memo\/0066"},{"key":"R12","unstructured":"H. Chen, A. Goel, C. Luhrs, and E. Winfree,\n                      Self-assembling tile systems that heal from small fragments\n                      , in Preliminary Proceedings of DNA Computing 13, M. Garzon and H. Yan, eds., 2007, pp. 30\u201346."},{"key":"R13","doi-asserted-by":"crossref","unstructured":"M. Cook, P. Rothemund, and E. Winfree,\n                      Self-assembled circuit patterns\n                      , in Proceedings of DNA Computing 9, Lecture Notes in Comput. Sci. 2943, J. Chen and J. Reif, eds., Springer, Berlin, 2004, pp. 91\u2013107.","DOI":"10.1007\/978-3-540-24628-2_11"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1038\/35079541"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"H. Ebbinghaus,\n                      Domino threads and complexity\n                      , in Computation Theory and Logic, Lecture Notes in Comput. Sci. 270, E. Borger, ed., Springer, Berlin, 1987, pp. 131\u2013142.","DOI":"10.1007\/3-540-18170-9_161"},{"key":"R16","unstructured":"Y. Etzion,\n                      On the Solvability of Domino Snake Problems\n                      , M.Sc. thesis, Department of Applied Mathematics and Computer Science, The Weizmann Institute of Science, Rehovot, Israel, 1991."},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90174-0"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1021\/nl0722830"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"A. Goel and P. Moisset de Espanes,\n                      Towards minimum size self-assembled counters\n                      , in Proceedings of DNA Computing 13, M. Garzon and H. Yan, eds., Lecture Notes in Comput. Sci. 4848, Springer, Berlin, 2008, pp. 46\u201353.","DOI":"10.1007\/978-3-540-77962-9_5"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1088\/0957-4484\/7\/3\/004"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1126\/science.1120367"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1126\/science.289.5482.1170"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1529\/biophysj.106.084681"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1007\/BF01199431"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"M. Kao and R. Schweller,\n                      Reducing tile complexity for self-assembly through temperature programming\n                      , in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2006, pp. 571\u2013580.","DOI":"10.1145\/1109557.1109620"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1016\/0167-2789(90)90195-U"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80025-X"},{"key":"R28","first-page":"121","volume":"3","author":"K\u00f6nig D.","year":"1927","journal-title":"Acta Litt. Sci. Szeged"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"M. Lagoudakis and T. LaBean,\n                      2D DNA self-assembly for satisfiability\n                      , in DNA Based Computers V, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 54, E. Winfree and D. Gifford, eds., AMS, Providence, RI, 2000, pp. 141\u2013154.","DOI":"10.1090\/dimacs\/054\/12"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1021\/nl051180j"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1038\/35017519"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1038\/35035038"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1021\/nl0619406"},{"key":"R34","unstructured":"D. Myers,\n                      Decidability of the tiling connectivity problem\n                      , abstract 79T-E42, Notices Amer. Math. Soc., 195 (1979), A-441."},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1038\/35091143"},{"key":"R36","doi-asserted-by":"crossref","unstructured":"J. Reif,\n                      Local parallel biomolecular computation\n                      , in DNA Based Computers III, DIMACS Ser. Discrete. Math. Theoret. Comput. Sci. 48, H. Rubin and D. Wood, eds., AMS, Providence, RI, 1999, pp. 217\u2013254.","DOI":"10.1090\/dimacs\/048\/17"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1007\/BF01418780"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.97.3.984"},{"key":"R39","unstructured":"P. Rothemund,\n                      Theory and Experiments in Algorithmic Self-Assembly\n                      , Ph.D. thesis, University of Southern California, Los Angeles, CA, 2001."},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1038\/nature04586"},{"key":"R41","doi-asserted-by":"crossref","unstructured":"P. Rothemund, N. Papadakis, and E. Winfree,\n                      Algorithmic self-assembly of DNA Sierpinski triangles\n                      , PLoS Biol., 2 (2004), e424.","DOI":"10.1371\/journal.pbio.0020424"},{"key":"R42","doi-asserted-by":"crossref","unstructured":"P. Rothemund and E. Winfree,\n                      The program-size complexity of self-assembled squares\n                      , in Proceedings of the ACM Symposium on Theory of Computing (STOC), 2001, pp. 459\u2013468.","DOI":"10.1145\/335305.335358"},{"key":"R43","doi-asserted-by":"publisher","DOI":"10.1038\/35099520"},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.1021\/nl049527q"},{"key":"R45","doi-asserted-by":"publisher","DOI":"10.1038\/nature02307"},{"key":"R46","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446712"},{"key":"R47","doi-asserted-by":"publisher","DOI":"10.1002\/anie.200500703"},{"key":"R48","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1961.tb03975.x"},{"key":"R49","doi-asserted-by":"publisher","DOI":"10.1126\/science.1962191"},{"key":"R50","unstructured":"E. Winfree,\n                      Algorithmic Self-Assembly of DNA\n                      , Ph.D. thesis, California Institute of Technology, Pasadena, CA, 1998."},{"key":"R51","doi-asserted-by":"publisher","DOI":"10.1038\/28998"},{"key":"R52","doi-asserted-by":"crossref","unstructured":"E. Winfree, X. Yang, and N. Seeman,\n                      Universal computation via self-assembly of DNA: Some theory and experiments\n                      , in DNA Based Computers II, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 44, L. Landweber and E. Baum, eds., AMS, Providence, RI, 1999, pp. 191\u2013213.","DOI":"10.1090\/dimacs\/044\/16"},{"key":"R53","doi-asserted-by":"publisher","DOI":"10.1038\/35020524"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/080723971","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:19:13Z","timestamp":1787336353000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/080723971"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1]]},"references-count":53,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["10.1137\/080723971"],"URL":"https:\/\/doi.org\/10.1137\/080723971","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1]]}}}