Brief Announcement: Intrinsic Universality in Seeded Active Tile Self-Assembly

Gomez, Tim; Grizzell, Elise; Haun, Asher; Knobel, Ryan; Peters, Tom; Schweller, Robert; Wylie, Tim

doi:10.4230/LIPIcs.SAND.2025.24

Brief Announcement: Intrinsic Universality in Seeded Active Tile Self-Assembly

Tim Gomez CSAIL, MIT, Cambridge, MA, USA Elise Grizzell

University of Texas Rio Grande Valley, Edinburg, TX, USA Asher Haun

University of Texas Rio Grande Valley, Edinburg, TX, USA Ryan Knobel University of Texas Rio Grande Valley, Edinburg, TX, USA Tom Peters

TU Eindhoven, The Netherlands Robert Schweller University of Texas Rio Grande Valley, Edinburg, TX, USA Tim Wylie University of Texas Rio Grande Valley, Edinburg, TX, USA

Abstract

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 $\Gamma$ , (b) the dynamics involved in building $\Gamma$ ’s assemblies, and (c) $\Gamma$ ’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 $\Gamma$ , transferring the information to simulate $\Gamma$ to each new tile. Supertiles may also asynchronously transition states according to the rules of $\Gamma$ . This result also implies IU for pairwise asynchronous Cellular Automata.

Keywords and phrases:

Intrinsic Universality, Tile Automata, Cellular Automata, Self-assembly

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Models of computation

Related Version:

Full Version: https://arxiv.org/abs/2407.11545 [7]

Funding:

This research was supported in part by National Science Foundation Grant CCF-2329918.

DOI:

10.4230/LIPIcs.SAND.2025.24

Event:

4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)

Editors:

Kitty Meeks and Christian Scheideler

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Tile self-assembly is a model that attempts to exploit the computational capabilities of simple mechanisms, such as nucleic acids, being used in simple monomers, such as DNA molecules, to combine to form complex structures, and in controlling the growth of those structures, to utilize their powers to perform computations. In recent years, a diverse set of new abstractions and models have been conceived and studied, the most prominent of which is likely the (two-dimensional) abstract Tile Assembly Model (aTAM) [11]. In this model, a tile is a non-rotatable unit square with specified glues on each side, modeling a single monomer. Two tiles can attach if their glues match. A tile assembly system is a set of these tile types and a temperature $\tau$ . Research into these models usually revolves around the types of assemblies that can be created with specific sets of tile types. These are studies in passive self-assembly since the monomers themselves can only attach, but not change.

Cellular Automata is a tangentially related area that can be viewed as having active “tiles” (in an infinitely tiled plane) where the state of each tile/cell can change based on its neighbors. In this paper, we work in a related model, derived by combining elements of tile self-assembly and the local state changes of asynchronous Cellular Automata: seeded Tile Automata (TA) [2] (see Figure 1(a)). A Tile Automata system $\Gamma$ has a set of states $\Sigma$ . Tiles with an initial state $\sigma\in\Lambda$ ( $\Lambda\subseteq\Sigma$ ) can attach to the seed $s$ if the system contains an affinity rule for their respective tile types that has an equal or higher strength than the system temperature $\tau$ . Should a single pair of tiles lack sufficient strength to bind to the assembly, they may bind cooperatively by adding the strengths of affinities of neighboring tiles to reach $\tau$ . Contrary to the passive aTAM, tiles in the active TA system can change their state based off transition rules, which allow only two adjacent tiles to interact.

Here, we study the creation of an intrinsically universal (IU) Tile Automata system $\Gamma_{U}$ , a system with a finite state set capable of creating not only the final assemblies of any other arbitrary Tile Automata system $\Gamma$ , but also replicating the exact assembly process and any additional computations achieved via transitions.

IU in Cellular Automata.

The study of self-simulation and universality is as old as the field of Cellular Automata itself, with von Neumann introducing the model to build a self-replicating machine [10]. Although Banks coined the term intrinsic universality [1] in 1970, von Neumann’s initial construction was also proven to be IU. Conway’s famous Game of Life is also intrinsically universal [6]. Intrinsic universality in CA has been studied extensively, but we highlight the related asynchronous results, such as [12]. These updating schemes restrict which cells can be updated at each time step. The closest related updating scheme to Tile Assembly is “fully asynchronous” where only one cell may update at a time.¹¹1For the case of Tile Automata and Surface Chemical Reaction Networks, it is better stated as “one rule” can be applied at a time because two cells can be updated in one update.

IU in Passive Self-Assembly.

In [5], a universal tile set was introduced for systems with tiles that bond with exactly strength 2. The first properly intrinsically universal tile set, one that can simulate the full aTAM at any temperature, was presented in [4]. These papers both used constructions for intrinsic universality that we call committal [9]. It was also shown that a single polygon tile type with the ability to flip, translate, and rotate can simulate any aTAM system through several intermediate simulations [3]. The aTAM was found not to be committal intrinsically universal at Temperature-1 [9], and in directed and non-directed planar systems [8]. Directed 3D and Spatial aTAM were proven to be IU [8].

Our Contributions.

Table 1 outlines the main contributions in context with other known IU results. We list impossibility proofs for non-committal IU for any passive or state-bounded system in Section 2. Section 3 covers the results related to IU for seeded TA, and Section 4 covers its implications with Cellular Automata.

Table 1: An overview of known and new simulation results for types of asynchronous cellular automata including tile assembly models. D is the dimension,

N

is neighborhood size of the input system,

|T|

and

|\Sigma|

are, respectively, the number of tile or state types in the universal system,

S

is the scale factor,

n

is the number of states in the input system, and

\tau

is the system’s temperature.

Intrinsic Universality Across Models
Model	D	$N$	$\|T\|$ / $\|\Sigma\|$	Scale ( $S$ )	Reference
aTAM	2D	5	$>$ 10M	$O(n^{4}\log(n))$	[4]
aTAM	3D	7	152 000	$O(n^{2}\log(n\tau))$	[8]
Seeded TA Temp- $1$	2D	5	4600	$O(n^{3})$	Theorem 3
Seeded TA	2D	5	4600	$O(\min((\tau n)^{3},n^{9}))$	Theorem 6
Async. Cellular Automata	1D	3	$O(1)$	unknown	[12]
Block-Pairwise ACA	2D	2	2600	$O(n^{3})$	Theorem 7
Pairwise ACA	2D	2	$O(1)$	$O(n^{3})$	Theorem 8

2 Strict IU

We show that any passive self-assembly model and variants of active self-assembly with bounded state changes cannot adhere to the stronger non-committal definition of intrinsic universality for self-assembly initially presented in [4]. Instead, a more permissive definition for dynamics simulation in IU systems (committal) has been used within self-assembly [9].

Theorem 1.

The Abstract Tile Assembly Model (aTAM) is not intrinsically universal under non-committal simulation.

Theorem 2.

The Freezing Seeded Tile Automata model is not intrinsically universal under non-committal simulation.

3 Seeded TA is Intrinsically Universal

Our main result is to show that the 2D seeded Tile Automata model with unbounded state changes adheres to the stronger non-committal definition of intrinsic universality, which is done in 3 steps:

1.

We show that temperature-1 seeded TA is IU, at scale $O(|\Sigma|^{3})$ , for all seeded temperature-1 systems with constant (approximately 4600) states.
2.

We show that any temperature- $\tau$ seeded TA system can be simulated by a temperature-1 seeded TA system by scaling based on $\tau$ or on the number of states and interactions, which requires $O(\min(|\Sigma|^{3},\tau|\Sigma|))$ states.
3.

These combine to create a general IU result for any seeded TA system by showing that the effect of temperature simulation on the scale of the system’s supertiles is bounded.

3.1 Seeded Temperature-1 TA

The simulation framework is intricate and substantial with many gadget and smaller constructions working together. Here, we merely show the basic blueprint of the scaled supertile. For full details and definitions, please see [7].

Supertiles.

Supertiles are $m\times m$ blocks that map to a specific tile in some state from the original system that is being simulated. Each supertile contains all information necessary for the simulation. Figure 1(b) shows a simplified diagram of a single supertile. Every supertile has binding sites on each of the four sides, and wires on each side that lead to a central lookup table corresponding to valid affinities and transitions for the system being simulated. Within the table each column represents a state in the system being simulated and each row a state and direction of a neighboring supertile. There are datacells at each intersection. The supertile makes use of several small gadgets for effective and correct communication and information transmission, as well as ensuring non-committal simulation. The most important gadgets are the Lookup Table, Transition Storage Area, Datacells, and the Transition Selection.

(a) Example seeded TA system.

(b) Supertile high-level overview.

Figure 1: (a) Example Tile Automata system with 6 states, a temperature of 4, affinities of different strengths, vertical and horizontal transitions, and a seed assembly. The assembly sequence to a terminal assembly is shown with the changes highlighted. Due to the affinity strengthening restriction, there is no detachment. (b) An overview of a supertile. 1) An agent inside of the supertile. 2) Wires connecting supertiles from each edge to the lookup table. West wires are drawn individually. 3) The lookup table storing the information about the system being simulated. 4) A row containing the information about the state of the east neighbor of the supertile. 5) The active column, representing the current state of the supertile. 6) A group of datacells storing all information for the north side. 7) A single datacell, in this case, storing the affinities and transitions for when both this supertile and the East supertile are in state 1. 8) The table control edge, with an agent waiting to enter. 9) Transition selection gadget at each edge, dictating the transition of this supertile with its east neighbor. This gadget is the key to non-committal IU with a tile and its neighbor committing to a state change simultaneously.

Theorem 3.

There exists a tile set $(\Sigma_{U},\Lambda_{U},\Pi_{U},\Delta_{U})$ such that, for all systems $\Gamma=(\Sigma,\Lambda,\Pi,\Delta,s,1)$ , there exists a $\Gamma^{\prime}=(\Sigma_{U},\Lambda_{U},\Pi_{U},\Delta_{U},s_{U},1)$ that simulates $\Gamma$ at scale $O(|\Sigma|^{3})$ .

3.2 Temperature Simulation

We show that at scale-1, we can simulate a seeded TA system at any temperature if we scale the number of states in the system based on the number of interactions. We can also scale based directly on the temperature. Together, this provides two bounds on the scale factor, which makes the optimal: $O(\min(\tau|\Sigma|,|\Sigma|^{3})$ .

Lemma 4.

For all Tile Automata systems $\Gamma_{\tau}=(\Sigma,\Lambda,\Pi,\Delta,s,\tau)$ there exists a system $\Gamma_{1}=(\Sigma_{1},\Lambda_{1},\Pi_{1},\Delta_{1},s_{1},1)$ that simulates it with 1-fuzz at scale-1 such that $|\Sigma_{1}|=O(\tau|\Sigma|)$ .

Lemma 5.

For all Tile Automata systems $\Gamma_{\tau}=(\Sigma,\Lambda,\Pi,\Delta,s,\tau)$ there exists a system $\Gamma_{1}=(\Sigma_{1},\Lambda_{1},\Pi_{1},\Delta_{1},s_{1},1)$ that simulates it with 1-fuzz at scale-1 such that $|\Sigma_{1}|=O(|\Sigma|^{3})$ .

3.3 Seeded TA is IU

By taking Theorem 3 in conjunction with Lemmas 4 and 5, we achieve the desired result that seeded Tile Automata is non-committal intrinsically universal. This follows by directly plugging in the state-scaling into the temperature-1 construction.

Theorem 6.

There exists a tile set $(\Sigma_{U},\Pi_{U},\Delta_{U},1)$ such that, for all systems $\Gamma=(\Sigma,\Lambda,\Pi,\Delta,s,\tau)$ , there exists a $\Gamma^{\prime}=(\Sigma_{U},\Lambda_{U},\Pi_{U},\Delta_{U},s^{\prime},1)$ that simulates $\Gamma$ with 1-fuzz at scale factor $O(\min((\tau|\Sigma|)^{3},|\Sigma|^{9})$ .

4 Asynchronous Cellular Automata

Due to the mechanics of TA, our construction can be adapted to prove that 2D Asynchronous Cellular Automata, with a cardinal radius of 1 and neighborhood size of 2, is also IU in approximately 2600 states, which although inefficient, is the first 2D ACA IU result.

Lemma 7.

Block-pairwise ACA is strongly intrinsically universal.

Theorem 8.

The Asynchronous Cellular Automata model with a cardinal-direction neighborhood of size-2 and radius-1 (pairwise ACA) is strongly intrinsically universal.

References

[1] Edwin Roger Banks. Universality in cellular automata. In 11th Annual Symposium on Switching and Automata Theory (swat), pages 194–215, 1970. doi:10.1109/SWAT.1970.27.
[2] Cameron Chalk, Austin Luchsinger, Eric Martinez, Robert Schweller, Andrew Winslow, and Tim Wylie. Freezing Simulates Non-freezing Tile Automata. In DNA Computing and Molecular Programming, pages 155–172, 2018. doi:10.1007/978-3-030-00030-1.
[3] Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Matthew J. Patitz, Robert T. Schweller, Andrew Winslow, and Damien Woods. One Tile to Rule Them All: Simulating Any Turing Machine, Tile Assembly System, or Tiling System with a Single Puzzle Piece. ArXiv e-Prints, 2012. doi:10.48550/arXiv.1212.4756.
[4] David Doty, Jack H. Lutz, Matthew J. Patitz, Robert T. Schweller, Scott M. Summers, and Damien Woods. The Tile Assembly Model is Intrinsically Universal. In 53rd Annual Symposium on Foundations of Computer Science, pages 302–310, 2012. doi:10.1109/FOCS.2012.76.
[5] David Doty, Jack H Lutz, Matthew J Patitz, Scott M Summers, and Damien Woods. Intrinsic Universality in Self-Assembly. In 27th International Symposium on Theoretical Aspects of Computer Science (2010), 2010. doi:10.4230/LIPIcs.STACS.2010.2461.
[6] Bruno Durand and Zsuzsanna Róka. The game of life: universality revisited. In Cellular Automata: a Parallel Model, pages 51–74, 1999. doi:10.1007/978-94-015-9153-9_2.
[7] Tim Gomez, Elise Grizzell, Asher Haun, Ryan Knobel, Tom Peters, Robert Schweller, and Tim Wylie. Intrinsic universality in seeded active tile self-assembly, 2024. arXiv:2407.11545.
[8] Daniel Hader, Aaron Koch, Matthew J. Patitz, and Michael Sharp. The Impacts of Dimensionality, Diffusion, and Directedness on Intrinsic Universality in the abstract Tile Assembly Model. In Symposium on Discrete Algorithms (SODA), pages 2607–2624, 2019.
[9] Pierre-Étienne Meunier, Matthew J. Patitz, Scott M. Summers, Guillaume Theyssier, Andrew Winslow, and Damien Woods. Intrinsic universality in tile self-assembly requires cooperation. In 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 752–771, 2014. doi:10.1137/1.9781611973402.56.
[10] J. von Neumann. Theory of self-reproducing automata. Urbana, U. of Illinois Press, 1966.
[11] Erik Winfree. Algorithmic self-assembly of DNA. California Institute of Technology, 1998.
[12] Thomas Worsch. Towards intrinsically universal asynchronous CA. Natural Computing, 12:539–550, 2013. doi:10.1007/s11047-013-9388-3.

[bib.bib1] [1] Edwin Roger Banks. Universality in cellular automata. In 11th Annual Symposium on Switching and Automata Theory (swat), pages 194–215, 1970. doi:10.1109/SWAT.1970.27.

[bib.bib2] [2] Cameron Chalk, Austin Luchsinger, Eric Martinez, Robert Schweller, Andrew Winslow, and Tim Wylie. Freezing Simulates Non-freezing Tile Automata. In DNA Computing and Molecular Programming, pages 155–172, 2018. doi:10.1007/978-3-030-00030-1.

[bib.bib3] [3] Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Matthew J. Patitz, Robert T. Schweller, Andrew Winslow, and Damien Woods. One Tile to Rule Them All: Simulating Any Turing Machine, Tile Assembly System, or Tiling System with a Single Puzzle Piece. ArXiv e-Prints, 2012. doi:10.48550/arXiv.1212.4756.

[bib.bib4] [4] David Doty, Jack H. Lutz, Matthew J. Patitz, Robert T. Schweller, Scott M. Summers, and Damien Woods. The Tile Assembly Model is Intrinsically Universal. In 53rd Annual Symposium on Foundations of Computer Science, pages 302–310, 2012. doi:10.1109/FOCS.2012.76.

[bib.bib5] [5] David Doty, Jack H Lutz, Matthew J Patitz, Scott M Summers, and Damien Woods. Intrinsic Universality in Self-Assembly. In 27th International Symposium on Theoretical Aspects of Computer Science (2010), 2010. doi:10.4230/LIPIcs.STACS.2010.2461.

[bib.bib6] [6] Bruno Durand and Zsuzsanna Róka. The game of life: universality revisited. In Cellular Automata: a Parallel Model, pages 51–74, 1999. doi:10.1007/978-94-015-9153-9_2.

[bib.bib7] [7] Tim Gomez, Elise Grizzell, Asher Haun, Ryan Knobel, Tom Peters, Robert Schweller, and Tim Wylie. Intrinsic universality in seeded active tile self-assembly, 2024. arXiv:2407.11545.

[bib.bib8] [8] Daniel Hader, Aaron Koch, Matthew J. Patitz, and Michael Sharp. The Impacts of Dimensionality, Diffusion, and Directedness on Intrinsic Universality in the abstract Tile Assembly Model. In Symposium on Discrete Algorithms (SODA), pages 2607–2624, 2019.

[bib.bib9] [9] Pierre-Étienne Meunier, Matthew J. Patitz, Scott M. Summers, Guillaume Theyssier, Andrew Winslow, and Damien Woods. Intrinsic universality in tile self-assembly requires cooperation. In 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 752–771, 2014. doi:10.1137/1.9781611973402.56.

[bib.bib10] [10] J. von Neumann. Theory of self-reproducing automata. Urbana, U. of Illinois Press, 1966.

[bib.bib11] [11] Erik Winfree. Algorithmic self-assembly of DNA. California Institute of Technology, 1998.

[bib.bib12] [12] Thomas Worsch. Towards intrinsically universal asynchronous CA. Natural Computing, 12:539–550, 2013. doi:10.1007/s11047-013-9388-3.