The Two-Handed Tile Assembly Model is not Intrinsically Universal
© 2015, Springer Science+Business Media New York. The Two-Handed Tile Assembly Model (2HAM) is a model of algorithmic self-assembly in which large structures, or assemblies of tiles, are grown by the binding of smaller assemblies. In order to bind, two assemblies must have matching glues that can si...
| Main Authors: | , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Nature America, Inc
2021
|
| Online Access: | https://hdl.handle.net/1721.1/135769 |
| _version_ | 1826188804449370112 |
|---|---|
| author | Demaine, Erik D Patitz, Matthew J Rogers, Trent A Schweller, Robert T Summers, Scott M Woods, Damien |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Demaine, Erik D Patitz, Matthew J Rogers, Trent A Schweller, Robert T Summers, Scott M Woods, Damien |
| author_sort | Demaine, Erik D |
| collection | MIT |
| description | © 2015, Springer Science+Business Media New York. The Two-Handed Tile Assembly Model (2HAM) is a model of algorithmic self-assembly in which large structures, or assemblies of tiles, are grown by the binding of smaller assemblies. In order to bind, two assemblies must have matching glues that can simultaneously touch each other, and stick together with strength that is at least the temperature τ, where τ is some fixed positive integer. We ask whether the 2HAM is intrinsically universal. In other words, we ask: is there a single 2HAM tile set U which can be used to simulate any instance of the model? Our main result is a negative answer to this question. We show that for all τ′ < τ, each temperature-τ′ 2HAM tile system does not simulate at least one temperature-τ 2HAM tile system. This impossibility result proves that the 2HAM is not intrinsically universal and stands in contrast to the fact that the (single-tile addition) abstract Tile Assembly Model is intrinsically universal. On the positive side, we prove that, for every fixed temperature τ ≥ 2, temperature-τ 2HAM tile systems are indeed intrinsically universal. In other words, for each τ there is a single intrinsically universal 2HAM tile set Uτ that, when appropriately initialized, is capable of simulating the behavior of any temperature-τ 2HAM tile system. As a corollary, we find an infinite set of infinite hierarchies of 2HAM systems with strictly increasing simulation power within each hierarchy. Finally, we show that for each τ, there is a temperature-τ 2HAM system that simultaneously simulates all temperature-τ 2HAM systems. |
| first_indexed | 2024-09-23T08:05:18Z |
| format | Article |
| id | mit-1721.1/135769 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T08:05:18Z |
| publishDate | 2021 |
| publisher | Springer Nature America, Inc |
| record_format | dspace |
| spelling | mit-1721.1/1357692023-12-08T21:12:28Z The Two-Handed Tile Assembly Model is not Intrinsically Universal Demaine, Erik D Patitz, Matthew J Rogers, Trent A Schweller, Robert T Summers, Scott M Woods, Damien Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory © 2015, Springer Science+Business Media New York. The Two-Handed Tile Assembly Model (2HAM) is a model of algorithmic self-assembly in which large structures, or assemblies of tiles, are grown by the binding of smaller assemblies. In order to bind, two assemblies must have matching glues that can simultaneously touch each other, and stick together with strength that is at least the temperature τ, where τ is some fixed positive integer. We ask whether the 2HAM is intrinsically universal. In other words, we ask: is there a single 2HAM tile set U which can be used to simulate any instance of the model? Our main result is a negative answer to this question. We show that for all τ′ < τ, each temperature-τ′ 2HAM tile system does not simulate at least one temperature-τ 2HAM tile system. This impossibility result proves that the 2HAM is not intrinsically universal and stands in contrast to the fact that the (single-tile addition) abstract Tile Assembly Model is intrinsically universal. On the positive side, we prove that, for every fixed temperature τ ≥ 2, temperature-τ 2HAM tile systems are indeed intrinsically universal. In other words, for each τ there is a single intrinsically universal 2HAM tile set Uτ that, when appropriately initialized, is capable of simulating the behavior of any temperature-τ 2HAM tile system. As a corollary, we find an infinite set of infinite hierarchies of 2HAM systems with strictly increasing simulation power within each hierarchy. Finally, we show that for each τ, there is a temperature-τ 2HAM system that simultaneously simulates all temperature-τ 2HAM systems. 2021-10-27T20:29:12Z 2021-10-27T20:29:12Z 2016 2019-06-18T11:45:23Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/135769 en 10.1007/S00453-015-9976-Y Algorithmica Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer Nature America, Inc arXiv |
| spellingShingle | Demaine, Erik D Patitz, Matthew J Rogers, Trent A Schweller, Robert T Summers, Scott M Woods, Damien The Two-Handed Tile Assembly Model is not Intrinsically Universal |
| title | The Two-Handed Tile Assembly Model is not Intrinsically Universal |
| title_full | The Two-Handed Tile Assembly Model is not Intrinsically Universal |
| title_fullStr | The Two-Handed Tile Assembly Model is not Intrinsically Universal |
| title_full_unstemmed | The Two-Handed Tile Assembly Model is not Intrinsically Universal |
| title_short | The Two-Handed Tile Assembly Model is not Intrinsically Universal |
| title_sort | two handed tile assembly model is not intrinsically universal |
| url | https://hdl.handle.net/1721.1/135769 |
| work_keys_str_mv | AT demaineerikd thetwohandedtileassemblymodelisnotintrinsicallyuniversal AT patitzmatthewj thetwohandedtileassemblymodelisnotintrinsicallyuniversal AT rogerstrenta thetwohandedtileassemblymodelisnotintrinsicallyuniversal AT schwellerrobertt thetwohandedtileassemblymodelisnotintrinsicallyuniversal AT summersscottm thetwohandedtileassemblymodelisnotintrinsicallyuniversal AT woodsdamien thetwohandedtileassemblymodelisnotintrinsicallyuniversal AT demaineerikd twohandedtileassemblymodelisnotintrinsicallyuniversal AT patitzmatthewj twohandedtileassemblymodelisnotintrinsicallyuniversal AT rogerstrenta twohandedtileassemblymodelisnotintrinsicallyuniversal AT schwellerrobertt twohandedtileassemblymodelisnotintrinsicallyuniversal AT summersscottm twohandedtileassemblymodelisnotintrinsicallyuniversal AT woodsdamien twohandedtileassemblymodelisnotintrinsicallyuniversal |