Intrinsic Universality in Seeded Active Tile Self-Assembly
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916326191136768 |
|---|---|
| author | Gomez, Tim Grizzell, Elise Haun, Asher Knobel, Ryan Peters, Tom Schweller, Robert Wylie, Tim |
| author_facet | Gomez, Tim Grizzell, Elise Haun, Asher Knobel, Ryan Peters, Tom Schweller, Robert Wylie, Tim |
| contents | The Tile Automata (TA) model describes self-assembly systems in which monomers can build structures and transition with an adjacent monomer to change their states. This paper shows that seeded TA is a non-committal intrinsically universal model of self-assembly. We present a single universal Tile Automata system containing approximately 4600 states that can simulate (a) the output assemblies created by any other Tile Automata system G, (b) the dynamics involved in building G's assemblies, and (c) G's internal state transitions. It does so in a non-committal way: it preserves the full non-deterministic dynamics of a tile's potential attachment or transition by selecting its state in a single step, considering all possible outcomes until the moment of selection.
The system uses supertiles, each encoding the complete system being simulated. The universal system builds supertiles from its seed, each representing a single tile in G, transferring the information to simulate G to each new tile. Supertiles may also asynchronously transition states according to the rules of G. This result directly transfers to a restricted version of asynchronous Cellular Automata: pairwise Cellular Automata. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_11545 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Intrinsic Universality in Seeded Active Tile Self-Assembly Gomez, Tim Grizzell, Elise Haun, Asher Knobel, Ryan Peters, Tom Schweller, Robert Wylie, Tim Cellular Automata and Lattice Gases Computational Complexity The Tile Automata (TA) model describes self-assembly systems in which monomers can build structures and transition with an adjacent monomer to change their states. This paper shows that seeded TA is a non-committal intrinsically universal model of self-assembly. We present a single universal Tile Automata system containing approximately 4600 states that can simulate (a) the output assemblies created by any other Tile Automata system G, (b) the dynamics involved in building G's assemblies, and (c) G's internal state transitions. It does so in a non-committal way: it preserves the full non-deterministic dynamics of a tile's potential attachment or transition by selecting its state in a single step, considering all possible outcomes until the moment of selection. The system uses supertiles, each encoding the complete system being simulated. The universal system builds supertiles from its seed, each representing a single tile in G, transferring the information to simulate G to each new tile. Supertiles may also asynchronously transition states according to the rules of G. This result directly transfers to a restricted version of asynchronous Cellular Automata: pairwise Cellular Automata. |
| title | Intrinsic Universality in Seeded Active Tile Self-Assembly |
| topic | Cellular Automata and Lattice Gases Computational Complexity |
| url | https://arxiv.org/abs/2407.11545 |