Intrinsic universality and the computational power of self-assembly
This short survey of recent work in tile self-assembly discusses the use of simulation to classify and separate the computational and expressive power of self-assembly models. The journey begins with the result that there is a single universal tile set that, with proper initialization and scaling, s...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Open Publishing Association
2013-09-01
|
| Series: | Electronic Proceedings in Theoretical Computer Science |
| Online Access: | http://arxiv.org/pdf/1309.1265v1 |
| _version_ | 1819243584201687040 |
|---|---|
| author | Damien Woods |
| author_facet | Damien Woods |
| author_sort | Damien Woods |
| collection | DOAJ |
| description | This short survey of recent work in tile self-assembly discusses the use of simulation to classify and separate the computational and expressive power of self-assembly models. The journey begins with the result that there is a single universal tile set that, with proper initialization and scaling, simulates any tile assembly system. This universal tile set exhibits something stronger than Turing universality: it captures the geometry and dynamics of any simulated system. From there we find that there is no such tile set in the noncooperative, or temperature 1, model, proving it weaker than the full tile assembly model. In the two-handed or hierarchal model, where large assemblies can bind together on one step, we encounter an infinite set, of infinite hierarchies, each with strictly increasing simulation power. Towards the end of our trip, we find one tile to rule them all: a single rotatable flipable polygonal tile that can simulate any tile assembly system. It seems this could be the beginning of a much longer journey, so directions for future work are suggested. |
| first_indexed | 2024-12-23T14:58:01Z |
| format | Article |
| id | doaj.art-beda5d79122a41a4a9722e63b35ac893 |
| institution | Directory Open Access Journal |
| issn | 2075-2180 |
| language | English |
| last_indexed | 2024-12-23T14:58:01Z |
| publishDate | 2013-09-01 |
| publisher | Open Publishing Association |
| record_format | Article |
| series | Electronic Proceedings in Theoretical Computer Science |
| spelling | doaj.art-beda5d79122a41a4a9722e63b35ac8932022-12-21T17:42:43ZengOpen Publishing AssociationElectronic Proceedings in Theoretical Computer Science2075-21802013-09-01128Proc. MCU 2013162210.4204/EPTCS.128.5Intrinsic universality and the computational power of self-assemblyDamien WoodsThis short survey of recent work in tile self-assembly discusses the use of simulation to classify and separate the computational and expressive power of self-assembly models. The journey begins with the result that there is a single universal tile set that, with proper initialization and scaling, simulates any tile assembly system. This universal tile set exhibits something stronger than Turing universality: it captures the geometry and dynamics of any simulated system. From there we find that there is no such tile set in the noncooperative, or temperature 1, model, proving it weaker than the full tile assembly model. In the two-handed or hierarchal model, where large assemblies can bind together on one step, we encounter an infinite set, of infinite hierarchies, each with strictly increasing simulation power. Towards the end of our trip, we find one tile to rule them all: a single rotatable flipable polygonal tile that can simulate any tile assembly system. It seems this could be the beginning of a much longer journey, so directions for future work are suggested.http://arxiv.org/pdf/1309.1265v1 |
| spellingShingle | Damien Woods Intrinsic universality and the computational power of self-assembly Electronic Proceedings in Theoretical Computer Science |
| title | Intrinsic universality and the computational power of self-assembly |
| title_full | Intrinsic universality and the computational power of self-assembly |
| title_fullStr | Intrinsic universality and the computational power of self-assembly |
| title_full_unstemmed | Intrinsic universality and the computational power of self-assembly |
| title_short | Intrinsic universality and the computational power of self-assembly |
| title_sort | intrinsic universality and the computational power of self assembly |
| url | http://arxiv.org/pdf/1309.1265v1 |
| work_keys_str_mv | AT damienwoods intrinsicuniversalityandthecomputationalpowerofselfassembly |