## Abstract

Molecular self-assembly, the formation of large structures by small pieces of matter sticking together according to simple local interactions, is a ubiquitous phenomenon. A challenging engineering goal is to design a few molecules so that large numbers of them can self-assemble into desired complicated target objects. Indeed, we would like to understand the ultimate capabilities and limitations of this bottom-up fabrication process. We look to theoretical models of algorithmic self-assembly, where small square tiles stick together according to simple local rules in order to carry out a crystal growth process. In this survey, we focus on the use of simulation between such models to classify and separate their computational and expressive powers. Roughly speaking, one model simulates another if they grow the same structures, via the same dynamical growth processes. Our journey begins with the result that there is a single intrinsically universal tile set that, with appropriate initialization and spatial scaling, simulates any instance of Winfree's abstract Tile Assembly Model. This universal tile set exhibits something stronger than Turing universality: it captures the geometry and dynamics of any simulated system in a very direct way. From there we find that there is no such tile set in the more restrictive non-cooperative model, proving it weaker than the full Tile Assembly Model. In the two-handed model, where large structures can bind together in one step, we encounter an infinite set of infinite hierarchies of 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 simulates any tile assembly system. We find another tile that aperiodically tiles the plane (but with small gaps). These and other recent results show that simulation is giving rise to a kind of computational complexity theory for self-assembly. It seems this could be the beginning of a much longer journey, so directions for future work are suggested.

## 1. Introduction

Molecular self-assembly, the formation of large structures by small pieces of matter sticking together according to simple local interactions, is a ubiquitous phenomenon in nature. It is also a phenomenon that we are beginning to learn how to control, or program, by designing molecules and their local interaction rules. Since Seeman's pioneering work on assembling two-dimensional (2D) [1,2] lattices from small artificially synthesized DNA molecules, we have learned how to self-assemble various kinds of shapes and patterns, such as Rothemund's nanoscale squares, tiny maps and smiley faces [3], as well as three-dimensional (3D) lattices [4] and shapes [5] including spheres and vases [6], and Latin, Arabic and Chinese characters [7]. These structures are hardcoded in the sense that for each position a unique DNA molecule is synthesized; the larger the structure the more unique the molecular components we need to design. Thinking of Seeman's periodic 2D DNA structures as lattices of tiles, Winfree [8] asked if one could use smarter molecules that exploit computation to come together in such a way that individual tile types end up appearing in many different locations in the target shape or pattern. Since then a number of examples of such algorithmic tile-based structures have been self-assembled, including regular arrays of tiles [9], fractal structures [10,11], bit-copying systems [12–14] and binary counters [12,15]. Given these experimental successes, it is imperative to have a theory of self-assembly to guide this rapidly developing field of nanoscale engineering. Models of algorithmic self-assembly are capable of Turing universality, and so of an infinite variety of computational behaviours, but yet distinct enough from existing computational models to present interesting theoretical challenges.

The abstract Tile Assembly Model, put forward by Winfree [8], is a kind of asynchronous non-deterministic cellular automaton that models crystal growth processes. Put another way, the abstract Tile Assembly Model restricts classical square Wang tiling [16] to use a mechanism for crystal-like growth of a tiling, one tile at a time, starting from a special seed tile. Formally, an instance of the abstract Tile Assembly Model [8] is called a tile assembly system and is a triple consisting of a finite set *T* of square tiles, a seed assembly *σ* (one or more tiles stuck together), and a temperature *τ*∈{1,2,3,…}, as shown in figure 1*a*. Each side of a square tile has a glue (or colour) *g* which in turn has a strength *s*∈{0,1,2,…}. Growth occurs on the integer plane and begins from a seed assembly (or a seed tile) placed at the origin, as shown in figure 1*b*. A tile sticks to a partially formed assembly if it can be placed next to the assembly in such a way that enough of its glues match the glues of the adjacent tiles on the assembly and the sum of the matching glue strengths is at least the temperature. Intuitively, the tile sticks if its binding is sticky enough to overcome thermal fluctuations in the environment. Growth proceeds one tile at a time, asynchronously and non-deterministically. In this model, tiles may not overlap nor rotate, and unlike Wang tiling, adjacent glues (colours) may mismatch in an assembly. The model is capable of Turing machine simulation [8], and indeed computation via Turing machine simulation can be used to guide the process of self-assembly [17].

Of course individual tiles need not be square: models with triangles [18,19], hexagons [18–21] and arbitrary polyominos and polygons [19,21–23] have been considered. Yet other models of self-assembly allow for non-local rules and large-scale interactions. One such model is the two-handed (or hierarchical) model [24–27] which allows large structures to stick together if enough of their tiles' edge colours match. Another is the Nubot model [20] of molecular robotics where large assemblies of molecules can grow and then move relative to each other in a rigid-body fashion. Although some self-assembly models can be thought of as generalizations of cellular automata, or effectivizations of Wang tiling, these models are all quite distinct from each other in terms of both questions that can be sensibly asked and results that can be obtained.

### (a) Introduction to the use of simulation in self-assembly

In this survey, we discuss the relative computational and expressive power of self-assembly models using *simulation* as a method to compare these models. Our notion of simulation is specifically designed to capture, in a formal and natural sense, both production (assemblies) and dynamics (how those assemblies are built) of self-assembly systems. In the past few years quite a number of results have come to fruition showing that simulation and the related notion of intrinsic universality can be used to classify the power of self-assembly systems. Simulation provides one clean theory to unify a wide range of self-assembly models including models that use different modes of assembly (single-tile versus multi-tile assembly, with or without rotations and/or flips) and various geometries (square tiles versus polyomino or polygonal tiles with information-encoding geometries). Some of these results formally show that intrinsic universality is a distinct notion from computational (Turing) universality while others show infinite hierarchies of tile assembly systems with increasing simulation power as we move up the hierarchies. Some of the results mentioned in this survey are summarized in figure 2 which the reader should refer to throughout the text.

Tile assemblers have borrowed and generalized the powerful idea of intrinsic universality from the cellular automata community where it has given rise to a rich theory [28–33].^{1} This short survey attempts to show that we are beginning to see this in self-assembly too. Tile self-assembly systems are distributed, asynchronous and non-deterministic. Hence it should not be surprising that our definition of simulation, and even some techniques used in proofs, use concepts similar to those seen in concurrency control, database theory and the theory of asynchronous state transition systems. For example, the definition of simulation is related, although with essential differences, to some notions of weak bisimulation used in the study of asynchronous distributed systems [36,37]. In particular, in the simulator system we interpret certain parts of assemblies as representing empty space in the simulated system, and for a time many tiles can be added to such regions before that region commits to encoding some specific tile in the simulated system. Hence the simulator makes ‘hidden’, or ‘internal’, actions as is seen in weak bisimulation. However, our notion of simulation is not an instance of weak bisimulation.^{2} Also, it should be noted that before the study of intrinsic universality in self-assembly, some previous self-assembly papers [17,38] made use of notions that can be seen as precursors to the definitions and results discussed here which perhaps lends weight to the intuition that spatially scaled dynamics-preserving simulation is a natural way to compare self-assembly systems.

It is important to point out that besides simulation there are a number of other methods to compare self-assembly models that also lead to interesting results and proof techniques. Examples include computational power [8,39], efficiency in terms of the number of tile types needed to build shapes or patterns [40,41] and computational complexity of verification of properties of tile assembly systems [42]. See other surveys for more details [43,44].

In this informal survey, we forgo formal definitions and proofs, which can be found in the cited literature.

## 2. Simulation and a result: the abstract Tile Assembly Model is intrinsically universal

Intuitively, one self-assembly model simulates another if they grow the same structures, via the same dynamical growth processes, possibly with some spatial scaling. In order to be a little more precise, let and be tile assembly systems of the abstract Tile Assembly Model described above. is said to *simulate* if the following conditions hold: (i) each tile of is represented by one or more *m*×*m* blocks of tiles in called *supertiles*, (ii) the seed assembly of is represented by the *seed assembly* of (one or more connected *m*×*m* supertiles), and (iii) via supertile representation every sequence of tile placements in the simulated system has a corresponding sequence of supertile placements in the simulator system and vice versa. It is worth pointing out that although the intuitive idea of one assembly system simulating another is fairly simple, the formal definition gets a little technical as the filling out of supertiles in the simulator is an asynchronous and non-deterministic distributed process with many supertiles growing independently and in parallel in the simulator system. See, for example, [45] for a formal definition.

With our notion of simulation in hand we are ready to describe intrinsic universality. Figure 1*d* illustrates the concept. A class of tile assembly systems *C* is said to be *intrinsically universal* if there exists a single set of tiles *U* that simulates any instance of *C*. For each such simulation, *U* should be appropriately initialized as an instance (i.e. a tile assembly system) of *C* itself. For example, the abstract Tile Assembly Model has been shown to be intrinsically universal [46]. Specifically, this means that there is a single set of tiles *U* that, when appropriately initialized, is capable of simulating an arbitrary tile assembly system . To program such a simulation, tiles from are represented as *m*×*m* supertiles (built from tiles in *U*) and the seed assembly of is represented as a connected assembly of such supertiles. Furthermore, the entire tile assembly system (a finite object) is itself encoded in the supertiles of of . Then if we observe all possible growth dynamics in both and we get that both systems produce the same set of assemblies via the same dynamics where we use a supertile representation function to map from supertiles over *U* to tiles from *T*. It is worth pointing out that in this particular construction [46] the simulating system is always (merely) at temperature *τ*=2 no matter how large the temperature (*τ*≥1) of the simulated system is.

This intrinsically universal tile set has the ability to simulate both the geometry and growth order of any tile assembly system. Modulo spatial rescaling, this universal tile set *U* represents the full power and expressivity of the entire abstract Tile Assembly Model.

## 3. A complexity theory for self-assembly: the abstract Tile Assembly Model

We have seen that the abstract Tile Assembly Model is intrinsically universal: a kind of completeness for the model with respect to our notion of simulation. The class of all Turing machines also exhibits a kind of completeness shown via the existence of a universal Turing machine, although typically using a much weaker notion of simulation than ours that cares less about capturing the dynamics of the simulated machine.^{3} Now that we know the abstract Tile Assembly Model is intrinsically universal, and that this holds with a fairly strict notion of simulation, we can attempt to use simulation to tease apart the power of different tile assembly models. Specifically we ask if natural subclasses of the model can achieve the full expressive power of the model via spatially scaled dynamics-preserving simulation and/or if such subclasses can even simulate each other.

### (a) Separating the power of cooperative and non-cooperative tile assembly systems

It has been known for some time that the abstract Tile Assembly Model at temperature 2, where at least some of the tiles are required to match on two or more sides for correct binding, i.e. *cooperative binding*, is capable of highly non-trivial behaviour. Turing machine simulation [40], efficient production of *n*×*n* squares and other simple size-*n* shapes using tile types [48], efficient production of arbitrary finite connected shapes using a number of tile types within a logarithmic factor of the Kolmogorov complexity of the shape [17] and even intrinsic universality [46] (as already discussed) can all be achieved with cooperative, or temperature 2, growth.

The fact that the (full) abstract Tile Assembly Model is intrinsically universal means that there is a subclass of the model, namely the class of systems that use the intrinsically universal tile set *U*, that is capable of simulating the full model. This suggests an obvious question: can we show that some subclasses of the model are provably weaker than the full model, by showing that systems from these subclasses cannot simulate the full model?

The most notorious such subclass is called temperature 1. Despite its esoteric name, it models a fundamental and ubiquitous form of growth: asynchronous growing and branching tips in Euclidian space where each new tile is added if it matches on at *least one side*. Since temperature 1 binding does *not* require matching glues on multiple sides, it is called non-cooperative binding. A reasonable analogy is to think of cooperative binding as context sensitive, and non-cooperative binding as context free. In 2D, it's like snakes on a plane.

Recently, it has been shown that that the temperature 1 abstract Tile Assembly Model (i.e. non-cooperative binding) is provably weaker than the full model [45]: in particular, temperature 1 tile assembly is not capable of *simulating* arbitrary tile assembly systems. In fact, there is a very simple cooperative tile assembly system, that uses cooperative binding on two sides in merely one location, that cannot be simulated by any non-cooperative tile assembly system. This is the first fully general negative result about temperature 1 that does not assume restrictions on the model nor unproven hypotheses. The proof uses a simple pumping lemma (called the window movie lemma) for self-assembly that gives a sufficient condition to modify assembly sequences and swap parts of assemblies. It is used to fool any claimed non-cooperative simulation of cooperative binding. This lemma has since found use elsewhere and indeed has been generalized in various ways [49–53]. An interesting aspect of the negative result is that it holds for 3D non-cooperative systems; they too cannot simulate arbitrary tile assembly systems. This seems quite shocking, given that 3D non-cooperative systems are Turing-universal [39]! So in particular, 3D non-cooperative systems can simulate 2D (or 3D) cooperative systems by simulating a Turing machine that in turn simulates the cooperative system, but this loose style of simulation ends up destroying the geometry and dynamics of tile assembly by encoding everything as ‘geometry-less’ strings.^{4} Hence, the negative result in [45] can be interpreted to mean that Turing-universal algorithmic behaviour in self-assembly does not imply the ability to simulate, in a direct geometric fashion, arbitrary algorithmic self-assembly processes. Despite this negative result, and a recent positive result, showing that non-cooperative systems can be programmed to grow assemblies of size larger than the number of tile types [54], it remains open whether 2D non-cooperative systems are intrinsically universal for themselves, or capable of Turing machine simulation in an error-free way.

It was also shown that in 3D there is a (cube) tile set that non-cooperatively simulates all 2D non-cooperative systems [45].

### (b) Separating the power of cooperative tile assembly systems

Besides the abstract Tile Assembly Model being intrinsically universal, it is also known that a restricted sub-model, called the locally consistent Tile Assembly Model, is intrinsically universal [55]. A locally consistent tile assembly system is one where tiles bind without mismatches, and with binding strength of exactly 2. This sub-model is quite expressive: the standard methods to simulate Turing machines with tile assembly systems are locally consistent, as are many systems that have been implemented in the laboratory to date with DNA [10–15]. This begs the question: are locally consistent systems capable of simulating the full model? Recent work by Becker & Meunier [49] shows that the answer is ‘no’. In particular, their results show that any class of tile assembly systems that has no mismatches, or disallows excess binding strength, cannot simulate the abstract Tile Assembly Model.^{5}

The result tells us that at least some of the tricky aspects of the intrinsic universality simulation in [46] are required. In particular, in that simulation binding mismatches occur in numerous places (often as a mechanism to decide which of the competing parts of an *m*×*m* simulator supertile will ‘win’ a competition to decide which simulated tile the supertile encodes). The fact that systems without mismatches cannot simulate those with mismatches [49] tells us that this aspect of the simulation is required. One of the key innovations in [49] is to generalize the window movie lemma (a pumping lemma) from [45] so that it can be applied in significantly more complicated settings. It will be interesting to see if this generalized ‘bisimulation lemma’ finds use elsewhere. Finally, Becker & Meunier [49] show that 3D mismatch-free tile assembly systems are intrinsically universal and leaves open the question for 2D mismatch-free systems.

It remains as future work to further characterize the power of interesting subclasses of the abstract Tile Assembly Model, and in particular, to separate such subclasses. Work in this direction will enable us to understand exactly which of the model's features are required for specific kinds of global behaviour.

## 4. A complexity theory for self-assembly: comparing models of self-assembly

What about other models of self-assembly besides the abstract Tile Assembly Model?

### (a) Two-hands

It has been shown that the two-handed, or hierarchical, model of self-assembly (where large assemblies of tiles may come together in a single step) is not intrinsically universal [27]. Specifically there is no tile set that, in the two-handed model, can simulate all two-handed systems for all temperatures. However, the same paper shows that for each temperature *τ*∈{2,3,4,…} there is a tile set *U*_{τ} that is intrinsically universal for the class of two-handed systems that work at temperature *τ*. Also, there is an infinite hierarchy of classes of such systems with each level strictly more powerful (can assemble more complicated shapes) than the one below. In fact there are an infinite set of such hierarchies, as described in the caption of figure 2. These results give a formalization of the intuition that multiple long range interactions are more powerful than fewer long range interactions in the two-handed model.

By combining results from [25,46], we get that there is a tile set for the two-handed model that (at temperature 2) simulates any tile assembly system of the abstract Tile Assembly Model. Specifically, is simulated using the intrinsically universal tile set *U* from [46] (which runs at temperature 2) which in turn is simulated at temperature 2 using the two-handed construction in [25].

### (b) The one polygon

Demaine *et al.* [21] take the existence of an intrinsically universal tile set for the abstract Tile Assembly Model [46] as merely the first in a sequence of simulations that routes from square tiles, to the intrinsically universal tile set, to hexagons (with strength <*τ*, or weak, glues) to a *single* polygon that is translatable, rotatable and flipable. Their fixed-sized polygon, when appropriately seeded, simulates any tile assembly system from the abstract Tile Assembly Model. This polygon, the one, captures the power of the entire abstract Tile Assembly Model: to simulate a tile assembly system one simply puts together a seed assembly of polygons that encodes and just lets it go! Likewise, Turing machines can be simulated with this single tile. It is also shown [21] that with translation only (i.e. no rotation), such results are not possible with a small (size ≤3) seed (although with larger seeds a single translation-only polyomino simulates the space–time diagram of a one-dimensional (1D) cellular automaton). In the simpler setting of Wang plane tiling it is shown [21] how to take any tile set *T* (on the square or hexagonal lattice) and ‘compile’ it using a very simple procedure to get a single regular polygon that simulates exactly the tilings of *T*, except with tiny gaps between the polygons. In particular, if one starts with any aperiodic square or hexagon tile set, that tile set can be complied to a single regular polygonal tile, all of who's tilings are aperiodic, with tiny gaps between the polygons.

### (c) Signal tiles, negative glues, polyominos

Of course, one can imagine reasonable self-assembly models that are quite different from those already discussed. For a number of such models simulation has been used as a method to compare their power. These include the experimentally motivated [56] Signal-Passing [57], and Active [58], Tile Assembly Models with tiles that have molecular (DNA) wires on their surface. Essentially there is a use-once circuit sitting on the assembly itself! The circuit's wires make use of Yurke *et al.*'s [59] beautiful toehold-mediated DNA strand displacement mechanism. Recently, Hendricks *et al.* [60] have shown that in the two-handed Tile Assembly Model there is a single 3D tile set that can simulate any 2D signal-passing tile assembly system (that does not have tile detachment). Their result shows that a constant number of planes (in the third dimension) is sufficient to handle wire crossings and asynchronous signal passing. A number of results on simulation using the (closely related) Active Tile Assembly Model can be found in Karpenko [58], including simulation of the temperature 2 abstract Tile Assembly Model with a spatial scale factor of 2, and simulation of cellular automata.

Recent work [50] shows that the abstract Tile Assembly Model and a non-cooperative version of it with both square or domino (or duple) tiles have incomparable power with respect to simulation. Both models exhibit systems that cannot be simulated by the other! Another paper [61] shows that negative glues (glues that repel each other) on square and domino tiles can be used, at temperature 1, to simulate the temperature 2 abstract Tile Assembly Model, and that the former model is actually more powerful than the latter. The same paper points out that the landscape of self-assembly simulation power versus computational simulation power is rather subtle in the sense that there are a number of classes of computationally universal systems that are unable to simulate the (algorithmic and geometric) process of self-assembly.

Fekete *et al.* [22] define scale-free (or scale factor 1) simulation and show that polyominoes which are ‘3-position limited’, meaning they have only three perimeter locations where glues can be placed, can be simulated by the temperature 1 abstract Tile Assembly Model. (Same for 4-position limited polyominoes where those positions have a restriction called ‘uniquely paired’.) Appropriate future negative results on the temperature 1 abstract Tile Assembly Model will apply to these models. This result can be thought of as a self-assembly analogue to the computational complexity notion that a problem is likely to have an efficient algorithm if we can place it in a class of problems that are all strongly conjectured to have efficient algorithms, but for which we cannot prove it.

As mentioned above, the abstract Tile Assembly Model can be thought of as an asynchronous and non-deterministic cellular automaton (CA) that has the notion of a crystal growth frontier. Hendricks & Patitz [62] formally relate the abstract Tile Assembly Model and CA: they give a single CA that simulates any tile assembly system, as well as a single-tile set that simulates any non-deterministic CA with a finite initial configuration. The methods of updating configurations in both models are quite different (CA are infinite, synchronous and deterministic, while tile assembly is finite, asynchronous and non-deterministic) and so their constructions need to handle this. Jonoska & Karpenko [63] show that 1D CA can be simulated by the Active abstract Tile Assembly Model (mentioned above) at temperature 1 by storing the time–space history in a large assembly. Further work shows that 1D and 2D CA are simulated in this active model, but where (by using the feature of tile detachment) the entire space–time history does not need to be stored [58,64]. Together these pieces of work open the possibility of further comparing and contrasting the CA and tile assembly models.

## 5. Conclusion and future work

The results cited in this survey show that simulation between self-assembly models can be used as a method to classify their relative power. It is worth pointing out that our notion of simulation seems to strike a nice balance between being loose enough so that we can find intrinsically universal systems of various kinds but restricted enough that negative results separating the power of various systems can actually be shown. As figure 2 shows, we are beginning to see a kind of complexity theory for self-assembly. Indeed gaps in the figure (i.e. missing solid arrows and missing models) suggest a variety of open questions.

It is an open question whether or not the hexagonal Tile Assembly Model [21], various polygonal tile assembly models [19,21], the Nubot model [20] and Signal-Passing Tile Assembly Model [60,63] are intrinsically universal. And independent of whether or not these models turn out to be intrinsically universal, we suggest that simulation can be used to tease apart their computational and expressive power, as well as the power of subclasses of these models. For example, Gilbert *et al.* [19] investigate the computational power of various kinds of polygonal tile assembly systems, showing that regular polygon tiles with more than six sides simulate Turing machines. What is the relationship between tile geometry and simulation power? Do more sides give strictly more simulation power?

A desirable feature of a simulator is not only that it simulates all possible dynamics of some simulated system, but that this is done in a probabilistically fair manner. Probabilities come into play when we think about the assembly process as a continuous time Markov process where tile placement is a random event (chosen uniformly from the set of possible placements) that occurs after an amount of time that is also a random variable, and in particular when we consider the number of tiles and order of their placement to assemble a given structure. Is there an intrinsically universal tile set that simulates a wide class of systems in a probabilistically fair manner? Here, the probability of seeing a given dynamics or assembly in a simulator should be close to that of the simulated system, where ‘close’ means, say, within a factor proportional to the spatial scaling. In particular, can the intrinsically universal simulations in [46,55] be improved to have this property?

Does there exist a tile set *U* for the abstract Tile Assembly Model, such that for any (adversarially chosen) seed assembly *σ*, at temperature 2, this tile assembly system simulates some tile assembly system ? Moreover, *U* should be able to simulate all such members of some non-trivial class *S*. *U* is a tile set that can do one thing and nothing else: simulate tile assembly systems from the class *S*. This question about *U* is inspired by the factor simulation question in CA [29], although it differs in the details.

Many algorithmic tile assembly systems use cooperative self-assembly to simulate Turing machines in a ‘zig-zag’ fashion, as do a number of experimentally implemented systems [12–14,65]. Can the negative result of [45] be extended to show 2D temperature 1 abstract Tile Assembly Model systems do not simulate zig-zag tile assembly systems? This would be a non-trivial extension as the negative result in [45] holds for the 3D temperature 1 model, which can indeed simulate zig-zag systems, and would show that no deterministic 2D temperature 1 system can simulate Turing machines in the ‘usual way’. Furthermore, Fekete *et al.* [22] show that a certain, rather general, class of ‘geometric bit-reading gadgets’ cannot be built in the 2D temperature 1 model, which gives some evidence that the standard method of simulating Turing machines in the abstract Tile Assembly Model is impossible in 2D at temperature 1.

There are a number of future research directions for the two-handed model. One open question [27] asks whether or not temperature *τ* two-handed systems can simulate temperature *τ*−1 two-handed systems. (We know that in this model temperature *τ* systems cannot simulate temperature *τ*+1 systems and that temperature *τ* systems can simulate temperature *τ*′ systems where [27]. Also, it is conjectured that temperature *τ* systems cannot simulate all temperature *τ*−1 systems [27], even though they seem, at least naively, to have sufficient cooperative capabilities. Hendricks *et al.* [66] show progress on this question by proving that for certain simulators the answer depends on the exact notion of simulation used.) Another direction involves finding which aspects of the model (e.g. mismatches, excess binding strength, geometric blocking) are required for intrinsic universality at a given temperature, in order to tease apart and better understand the intricacies of this very powerful, but natural, model.

Of course, there are many other ways to compare the power of self-assembly models; for details see for example two other surveys on the theory of algorithmic tile assembly [43,44]. Researchers have looked at shape and pattern building, tile complexity, time complexity, determinism versus non-determinism and randomized (coin-flipping) algorithms in self-assembly. It remains as important future work to find relationships between these notions on the one hand, and intrinsic universality and simulation on the other hand. Can ideas from intrinsic universality be used to answer questions about these notions?

## Acknowledgements

I thank *all* my co-authors on the topic of intrinsic universality in tile assembly, I have enjoyed working with you all immensely. It has been a fun ride so far, yet it seems there is much to learn. I thank Matt Patitz, Pierre-Étienne Meunier, Trent Rogers and Florent Becker for insights related to this article and Erik Winfree and Paul W. K. Rothemund for discussions on intrinsic universality over the years. Many thanks to Viv Kendon, Susan Stepney and Angelika Sebald for the invitation to present this work.

## Footnotes

One contribution of 13 to a Theo Murphy meeting issue ‘Heterotic computing: exploiting hybrid computational devices’.

↵1 This notion has also been studied in the context of Wang tiling [34,35].

↵2 In particular, our definition allows for simulator assemblies

*α*′, which represent*α*in the simulated system, to represent merely a*proper subset*of the dynamics of*α*; as long as*α*′ can be reached by an assembly from which the full set of dynamics is indeed possible. Weak bisimulation forbids this as there is no way to consistently label the states, or assemblies, of such a simulator by states in the simulated system.↵3 It turns out that one can have a much tighter notion of simulation for Turing machines inspired by the constant spatial scale factor simulations discussed in this survey, and furthermore it turns out that Turing machines are intrinsically universal under this notion. As described in [47], it is possible to have a universal Turing machine that simulates any Turing machine

*M*with only a constant factor time overhead and a constant factor ‘spatial rescaling’ of tape contents. This universal machine stores the entire simulated program*M*(which is of constant size: i.e. independent of the input length) at the simulated tape head position. Simulating a transition rule involves reading and copying information from the simulated program, and simulating a move left or right involves moving the entire simulated program one step to the left or right. Each step is simulated in time independent of the time and space of the simulated machine, and quadratic in the constant-length simulated program. Intuition compels belief in this being the morally correct notion of intrinsic universality for Turing machines. The construction is particularly straightforward as the Turing machine model is both sequential and local.↵4 Or as Paul W.K. Rothemund has put it, 3D non-cooperative systems can dream about tile assembly, but cannot actually

*do*tile assembly.↵5 Moreover, Becker & Meunier [49] show that mismatch-free systems and systems without excess binding strength cannot simulate each other.

- Accepted April 28, 2015.

- © 2015 The Author(s) Published by the Royal Society. All rights reserved.