{'fraction_non_alphanumeric': 0.03553853110951507, 'fraction_numerical': 0.008831431383502248, 'mean_word_length': 4.2300361713967725, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Intrinsic universality in tile self-assembly requires cooperation

We prove a negative result on the power of a model of algorithmic self-assembly for which it has been notoriously difficult to find general techniques and results. Specifically, we prove that Winfree's abstract Tile Assembly Model, when restricted to use noncooperative tile binding, is not intrinsically universal. This stands in stark contrast to the recent result that, via cooperative binding, the abstract Tile Assembly Model is indeed intrinsically universal. Noncooperative self-assembly, also known as"temperature 1", is where tiles bind to each other if they match on one or more sides, whereas cooperative binding requires binding on multiple sides. Our result shows that the change from single- to multi-sided binding qualitatively improves the kinds of dynamics and behavior that these models of nanoscale self-assembly are capable of. Our lower bound on simulation power holds in both two and three dimensions; the latter being quite surprising given that three-dimensional noncooperative tile assembly systems simulate Turing machines. On the positive side, we exhibit a three-dimensional noncooperative self-assembly tile set capable of simulating any two-dimensional noncooperative self-assembly system. Our negative result can be interpreted to mean that Turing universal algorithmic behavior in self-assembly does not imply the ability to simulate arbitrary algorithmic self-assembly processes.


Introduction
Self-assembly is the process through which unorganized, simple, components automatically coalesce according to simple local rules to form some kind of target structure. It sounds simple, but the end result can be extraordinary. For example, researchers have been able to self-assemble a wide variety of structures experimentally at the nanoscale, such as regular arrays [47], fractal structures [21,39], smiling faces [38,44], DNA tweezers [48], logic circuits [34,40], neural networks [35], and molecular robots [27]. These examples are fundamental because they demonstrate that self-assembly can, in principle, be used to manufacture specialized geometrical, mechanical and computational objects at the nanoscale. Potential future applications of nanoscale self-assembly include the production of smaller, more efficient microprocessors and medical technologies that are capable of diagnosing and even treating disease at the cellular level.
Controlling nanoscale self-assembly for the purposes of manufacturing atomically precise components will require a bottom-up, hands-off strategy. In other words, the self-assembling units themselves will have to be "programmed" to direct themselves to do the right thing-efficiently and correctly. Molecular self-assembly is rapidly becoming a ubiquitous engineering paradigm, and we need to develop a theory to inform us of its algorithmic capabilities and ultimate limitations.
In 1998, Erik Winfree [45] introduced the abstract Tile Assembly Model (aTAM), an over-simplified discrete mathematical model of algorithmic DNA nanoscale self-assembly pioneered by Seeman [41]. The aTAM is an asynchronous nondeterministic cellular automaton, that models crystal growth processes. Put another way, the aTAM essentially augments classical Wang tiling [43] with a mechanism for sequential "growth" of a tiling (in Wang tiling, only the existence of a valid, mismatch-free tiling is considered and not the order of tile placement). In the aTAM, the fundamental components are un-rotatable, but translatable square or cube "tile types" whose sides are labeled with "glue" colors and integer "strengths". Two tiles that are placed next to each other interact if the glue colors on their abutting sides match, and they bind if the strengths on their abutting sides match and sum to at least a certain (integer) "temperature". Self-assembly starts from a "seed" tile type and proceeds nondeterministically and asynchronously as tiles bind to the seed-containing-assembly. Despite its deliberate over-simplification, the aTAM is a computationally expressive model. For example, by using cooperative binding (that is, binding of tiles on two or more sides), Winfree [45] proved that it is Turing universal, which implies that self-assembly can be directed by a computer program. Here, we study noncooperative binding.
Tile self-assembly in which tiles may be placed in a noncooperative fashion is colloquially referred to as "temperature-1 self-assembly". Despite the esoteric name, this is a fundamental and ubiquitous form of growth: it refers to growth from growing and branching tips in Euclidian space where each new tile is added if it can match on at least one side. It has been known for some time that a more general form of growth where some of the tiles must match on two or more sides, i.e. cooperative growth, leads to highly non-trivial behavior: arbitrary Turing machine simulation [25,37], efficient production of n × n squares and other simple shapes using Θ(log n/ log log n) tile types [1], efficient production of arbitrary finite connected shapes using a number of tile types that is within a log factor of the Kolmogorov complexity of the shape [42], and even intrinsic universality: the existence of a single tile set that simulates arbitrary tile assembly systems [17]. Until now, it was not known whether or not two-dimensional noncooperative binding has these capabilities without possibility of error, although in all cases the answer has been conjectured to be negative [11,12,20,28,32,37]. Our main result is such a negative result. Simply put, there is no noncooperative tile set that simulates all other tile assembly systems.
The topic of intrinsic universality, with its tight notion of simulation, has given rise to a rich theory in the field of cellular automata [5,13,14,30], and indeed has also been studied in Wang tiling [22][23][24] and tile self-assembly [16][17][18]. Recently, the aTAM has been shown to be intrinsically universal [17], meaning that there is a single set of tiles U that works at temperature 2, and when appropriately initialized, is capable of simulating the behavior of an arbitrary aTAM tile assembly system. Modulo rescaling, this single tile set U represents the full power and expressivity of the entire aTAM model, at any temperature. Indeed, Demaine et al [15] apply this to show that there is a single (rotatable, translatable) polygonal tile that can simulate any tile assembly system or Wang plane tiling system. The restricted "locally consistent" aTAM also exhibits intrinsic universality [18]. More recently, it has been shown that the two-handed model of self-assembly (where large assemblies of tiles may come together in a single step) is not intrinsically universal [16]. However, the same paper shows that for each "temperature" τ ∈ {2, 3, 4, . . .} there is a tileset that is intrinsically universal for the class of two-handed systems that work at temperature τ [16], and that there is an infinite hierarchy of classes of systems with each level strictly more powerful than the one below. As has been done for cellular automata, intrinsic universality in self-assembly, with its well-defined and powerful notion of simulation, is becoming a new tool by which we can tease apart the computational power of self-assembly systems.

Results
We give an overview of our results, although a number of terms have not yet been formally defined. For definitions, see Section 2. Our main result states that in the standard noncooperative model (i.e. temperature-1 aTAM in 2D) there is no intrinsically universal tile set. The proof is contained in Section 3. Theorem 1.1. There is no tile set U such that U is intrinsically universal at temperature 1 for the class of all aTAM tile assembly systems.
Our main result stands in stark contrast to the fact that if we permit cooperative binding (that is, temperature 2) then there is a universal tile set for the aTAM: Theorem (Doty, Lutz, Patitz, Schweller, Summers, Woods [17]). There is a tile set U such that U is intrinsically universal at temperature 2 for the class of all aTAM tile assembly systems.
This proves that noncooperative systems can not simulate cooperative systems, and shows that temperature 1 systems are provably weaker than temperature 2 systems in terms of their ability to simulate structure and dynamics. The same proof from Section 3 also works in 3D: There is no 3D tile set U such that U is intrinsically universal at temperature 1 for the class of all aTAM tile assembly systems.
The latter negative result is interesting in how it stands in contrast to the known result that 3D temperature 1 can indeed simulate arbitrary algorithms: Theorem (Cook, Fu, Schweller [12]). For each Turing machine M and input x there exists a 3D temperature 1 tile assembly system T M,x that simulates the computation of M on x.
So, the process of tile assembly can be simulated by a (Turing machine) algorithm, and 3D temperature-1 can simulate arbitrary algorithms, yet 3D temperature-1 can not simulate self-assembly in a way that preserves structure and dynamics. This result essentially says that in a noncooperative growthbased setting, the ability to simulate arbitrary algorithms does not confer the ability to simulate arbitrary algorithmic tile-based growth dynamics.

Positive results
Our negative results should be contrasted with our positive result, which is proved in Section 4. We find that 3D noncooperative tile assembly can in fact simulate 2D noncooperative tile assembly, in other words, 3D temperature-1 simulates 2D temperature-1.
There is a 3D tile set U such that U is intrinsically universal at temperature 1 for the class of all 2D aTAM tile assembly systems.
Finally, we conjecture the following: There is no 2D tile set U such that U is intrinsically universal at temperature 1 for the class of all 2D aTAM temperature 1 tile assembly systems.

Other results
The proof of Theorems 1.1 and 1.2, also holds for the restricted class of "locally consistent" aTAM systems [18]. In [18] it was shown that there is a locally consistent tile set that is intrinsically universal at temperature 2 for all locally constant systems. Here we show that temperature 1 can not even simulate this restricted class of systems (proof: the TAS T shown to be un-simulatable at temperature 1 in the proof of Theorem 1.1 is locally consistent): There is no tile set U such that U is intrinsically universal at temperature 1 for the class of all locally consistent aTAM tile assembly systems.
Intrinisic universality uses a strong notion of simulation where the simulator is a single tile set that simulates all tile assembly systems from some class. A weaker form of simulation is where for each tile assembly system T from some class, there exists a simulator tile assembly system T (from another class), that simulates T (see, e.g., [2,8,15]). Our proof shows that even this weaker form of simulation of temperature-2 is impossible at temperature 1: There is a 2D temperature-2 tile assembly system T that can not be simulated by any 2D, nor any 3D, temperature 1 tile assembly system.
The proof of this is the same as the proofs of Theorem 1.2, and given in Section 3. 1

Key technical ideas and methods
One of the main challenges with proving negative results about 2D temperature 1 self-assembly comes from the intuition that, although the assemblies produced at temperature-1 often look "obviously simple" (they are a collection of simple paths, possibly with repeating tile types), it seems extremely difficult to prove this. This is because it is easy to overlook geometry and quickly become seduced into believing that, as a result of the noncooperative nature of temperature-1 self-assembly, it must always be possible to indefinitely repeat (or "pump") sub-paths of tiles that begin and end with the same tile type. However, it is easy to construct an example of a 2D temperature-1 selfassembly system that uniquely produces a final structure, which contains at least one sub-path that begins and ends with the same tile type but the subpath can not be pumped indefinitely because it gets "blocked" by previous portions of the path. Could a long growth path that blocks itself, but branches just before doing so, simulate meaningful computation? Surprisingly, both the the 2D low-error, and 3D no-error, temperature-1 Turing machine simulations in [12] iterate exactly this idea, over and over, along with some clever geometric tricks. Our result here shows that neither this, nor any trick, will suffice to show that 2D nor 3D temperature-1 simulates aTAM tile self-assembly.
To show this limitation on temperature-1, we first prove Lemma 3.3 that gives a sufficient condition for taking any two assemblies, at any temperature ≥ 1, and "splicing" them together to create a new valid assembly. This gives a kind of strong pumping lemma for self-assembly. This lemma generalizes Theorem 3.1 of [3], which was (a) proven for a more restrictive scenario where the assemblies are contained in long and thin rectangles, and (b) works only for pumping a positive number of times-ours works for negative pumping (i.e. shrinking/splicing out) also.
Armed with this lemma, we then give an example, very simple, temperature 2 tile assembly system T that uses cooperative binding (binding on 2 sides) in exactly one tile position, with all other bonds being noncooperative. We show that any claimed temperature-1 simulation of this system must fail, and the place it fails is at the location where it should simulate cooperative binding. Any claimed simulator tile set is free to choose to use arbitrary scaling and a complicated-looking seed assembly, and may have a large (but constant) number of tile types; nevertheless we can use our pumping lemma to splice out parts of the simulation and trick it into exposing its inability to simulate cooperation. The proof is given in Section 3: it works in both 2D and 3D which gives Theorems 1.1 and 1.2. In the proof, since T is locally consistent, we get also Theorem 1.5, and since we exhibited a specific T that can not be simulated we get Theorem 1.6.
In Section 4 we show that the 3D temperature-1 aTAM can indeed simulate the 2D temperature-1 aTAM. The construction makes extensive use of the fact that in 3D, a closed curve does not necessarily partition the space into two parts. It repeatedly uses the third dimension as a means of sidestepping the limitations of planarity, and for "stepping up and over" locations reserved for future growth, then "stepping down" to place blocking tiles which will later block specific paths, and then returning to continue growth along a path which will eventually read this geometric blocking information. Similar blocking was used by Cook, Fu, and Schweller [12]. However, their construction consists of one single non-blocked path, with many tiny blocked branches. Our construction simulates the multiple, often independent, paths of the simulated system by using many paths, each of which has many tiny branches that all get blocked, except for one. This forces the construction to correctly handle a variety of timing issues related to the growth of the assembly, always ensuring that any needed blocking tiles must be placed before the path which will "read" them cane form, and also to correctly deal with all possible situations where divergent paths (i.e. those simulating the independent additions of separate tiles) may later converge on a location. This is dealt with using a "competition" scheme similar to that in [18] and [17].

Prior work on noncooperative binding
Many examples (referenced above) testify that cooperative binding in tile selfassembly is sufficient for the self-assembly of computationally and geometrically interesting shapes and patterns. But is it necessary? In other words, is cooperative binding more powerful than noncooperative binding?
Unfortunately and frustratingly, few general techniques exist for proving lower bounds in 2D temperature-1 self-assembly. However, there are some nice examples that begin to expose its the limitations. For instance, Rothemund and Winfree [37] proved that the number of unique tile types required to uniquely self-assemble a fully-connected n × n square in 2D at temperature-1 is ≥ n 2 and conjectured that, in general, 2n − 1 unique tile types are necessary to uniquely self-assemble n × n squares at temperature-1. Manuch et al. [28] proved that the minimum number of unique tile types required to uniquely selfassemble an n × n square in 2D, at temperature-1, with no glue mismatches, is 2n − 1. Note that the latter result does not assume a fully-connected terminal structure, whereas the former does. Doty, Patitz and Summers [20] formalized a notion of "pumpability" in temperature-1 self-assembly: a 2D temperature-1 self-assembly system that uniquely produces an infinite structure is "pumpable", if for every sufficiently long path of tiles, it is always possible to find at least one infinitely repeatable sub-path of tiles along this path (although not every sub-path that begins and ends with the same tile type may be infinitely repeatable). They conjecture that all 2D temperature-1 tile systems that uniquely produce some final structure are pumpable, and under the assumption of pumpbility they prove that the shape or pattern it produced is necessarily "simple" in the sense of Presburger arithmetic [33]. However, their conjecture remains unproven.

Prior work on intrinsic universality
Intrinsic universality uses a strict notion of simulation, where the simulator preserves the dynamics of the simulated system, modulo a constant-sized (block) rescaling. In particular, an intrinsically universal cellular automata is one where its space-time diagrams contain (via a representation function) those of any simulated cellular automaton: where (in 1D) a single cell in the simulated automaton is represented by an m × t block in the simulator. Despite this strong requirement, intrinsically universal cellular automata were shown to be very common in some natural classes of rules [6] and there are examples with very small programs (rules) [31]. The idea that intrinsic universality could facilitate the finding of lower bounds and negative results was conjectured, for example in [31], and a general method was proposed in [9]. Since then, intrinsic universality, and in particular communication complexity theory, have been used as general tools to show negative results on cellular automata [7,9,10,29].
The notion of simulation we use can be thought of as a reduction between systems, however it is stronger than usual reductions defined via algorithmic resource constraints (time, space, even constant circuit depth, etc.). For computational models it is often difficult to prove negative results separating computational power, however, our strict notion of simulation shifts the difficulty from proving hardness results to proving simulation (or completeness) results. However, now that we have examples of intrinsically universal tile sets U [16][17][18] we know that arbitrary "tile programs" can be written, analyzed and compiled into such U ; it captures everything (modulo rescaling). Not only that, we claim that our notion of simulation is a powerful tool because we have gained the ability to prove lower bounds and impossibility results, as this paper shows 2 Preliminaries

Informal description of the abstract Tile Assembly Model
This section gives a brief informal sketch of the abstract Tile Assembly Model (aTAM). See Section 2.2 for a formal definition of the aTAM. In this section, we define the 2D aTAM, whereas in Section 2.2 we formulate the d-dimensional aTAM. For purposes of notational convenience, throughout this paper we will use the term "aTAM" will refer to the 2D aTAM.
A tile type is a unit square with four sides, each consisting of a glue label, often represented as a finite string, and a nonnegative integer strength. A glue g that appears on multiple tiles (or sides) always has the same strength s g . There are a finite set T of tile types, but an infinite number of copies of each tile type, with each copy being referred to as a tile. An assembly is a positioning of tiles on the integer lattice Z 2 , described formally as a partial function α : Z 2 T . Let A T denote the set of all assemblies of tiles from T , and let A T <∞ denote the set of finite assemblies of tiles from T . We write α β to denote that α is a subassembly of β, which means that dom α ⊆ dom β and α(p) = β(p) for all points p ∈ dom α. Two adjacent tiles in an assembly interact, or are attached, if the glue labels on their abutting sides are equal and have positive strength. Each assembly induces a binding graph, a grid graph whose vertices are tiles, with an edge between two tiles if they interact. The assembly is τ -stable if every cut of its binding graph has strength at least τ , where the strength of a cut is the sum of all of the individual glue strengths in the cut. A tile assembly system (TAS) is a triple T = (T, σ, τ ), where T is a finite set of tile types, σ : Z 2 T is a finite, τ -stable seed assembly, and τ is the temperature. An assembly α is producible if either α = σ or if β is a producible assembly and α can be obtained from β by the stable binding of a single tile. In this case we write β → T 1 α (to mean α is producible from β by the attachment of one tile), and we write β → T α if β → T * 1 α (to mean α is producible from β by the attachment of zero or more tiles). When T is clear from context, we may write → 1 and → instead. We let A[T ] denote the set of producible assemblies of T . An assembly is terminal if no tile can be τ -stably attached to it. We let A 2 [T ] ⊆ A[T ] denote the set of producible, terminal assemblies of T . A TAS T is directed if |A 2 [T ]| = 1. Hence, although a directed system may be nondeterministic in terms of the order of tile placements, it is deterministic in the sense that exactly one terminal assembly is producible (this is analogous to the notion of confluence in rewriting systems).
Since the behavior of a TAS T = (T, σ, τ ) is unchanged if every glue with strength greater than τ is changed to have strength exactly τ , we assume that all glue strengths are in the set {0, 1, . . . , τ }.

Formal description of the abstract Tile Assembly Model
This section gives a formal definition of the abstract Tile Assembly Model (aTAM) [46]. For readers unfamiliar with the aTAM, Section 2.1 contains a less formal overview and [37] gives an excellent introduction to the model.
Fix an alphabet Σ. Σ * is the set of finite strings over Σ. Z, Z + , and N denote the set of integers, positive integers, and nonnegative integers, respec- i.e., if and only if x and y are adjacent on the d-dimensional integer Cartesian space.
A d-dimensional tile type is a tuple t ∈ (Σ * × N) 2d ; e.g., a unit square (or cube) with four (or six) sides listed in some standardized order, each side having a glue g ∈ Σ * × N consisting of a finite string label and nonnegative integer strength. From this point on, a tile will refer to either a 2D square or 3D cube tile type. We assume a finite set of tile types, but an infinite number of copies of each tile type, each copy referred to as a tile. A d-dimensional tile set is a set of d-dimensional tile types and is written as d-T . A tile set T is a set of d-dimensional tile types for some d ∈ {2, 3}. A d-configuration is a (possibly empty) arrangement of tiles on the integer lattice Z d , i.e., a partial function Let A T denote the set of all assemblies of tiles from T , and let A T <∞ denote the set of finite assemblies of tiles from T . The shape S α ⊆ Z d of α is dom α. Two adjacent tiles in an assembly interact, or are attached, if the glues on their abutting sides are equal (in both label and strength) and have positive strength. Each assembly α induces a binding graph G b α , a grid graph whose vertices are positions occupied by tiles, with an edge between two vertices if the tiles at those vertices interact. Given τ ∈ Z + , α is τ -stable if every cut of G b α has weight at least τ , where the weight of an edge is the strength of the glue it represents. When τ is clear from context, we say α is stable. Given two assemblies α, β, we say α is a subassembly of β, and we write α β, if S α ⊆ S β and, for all points p ∈ S α , α(p) = β(p). A The result of an assembly sequence is the unique limiting assembly (for a finite sequence, this is the final assembly in the sequence).
We write α → T β, and we say α T -produces β (in 0 or more steps) if there is a T -assembly sequence α 0 , α 1 , . . . of length k = |S β \ S α | + 1 such that If k is finite then it is routine to verify that β = α k−1 . We say α is T -producible if σ → T α, and we write A[T ] to denote the set of T -producible assemblies. The relation → T is a partial order on A[T ] [26,36].
An assembly α is T -terminal if α is τ -stable and ∂ T α = ∅. We write When T is clear from context, we may omit T from the notation above and instead write → 1 , →, ∂α, assembly sequence, produces, producible, and terminal.

Simulation definition
To state our main result, we must formally define what it means for one TAS to "simulate" another. The following definitions improve the presentation of those in [17], and correct a subtle error there. 2 From this point on, let T be a d-dimensional tile set, and let m ∈ Z + . An m-block supertile over T is a partial function α : Note that the dimension of the m-block is implicitly defined by the dimension of T . Let B T m be the set of all m-block supertiles over T . The m-block with no domain is said to be empty. For a general assembly α : and undefined otherwise. For a given valid m-block supertile representation function R from tile set S to tile set T , define the assembly representation func- In other words, α may have tiles on supertile blocks representing empty space in α, but only if that position is adjacent to a tile in α. We call such growth "around the edges" of α fuzz and thus restrict it to be adjacent to only valid supertiles, but not diagonally adjacent (i.e. we do not permit diagonal fuzz ).
In the following definitions, let T = (T, σ T , τ T ) be a d-TAS for d ∈ {2, 3}, let S = (S, σ S , τ S ) be a d -TAS for d ≥ d, and let R be an m-block representation function R : B S m → T .
Definition 2.1. We say that S and T have equivalent productions (under R), and we write S ⇔ T if the following conditions hold:
The previous definition essentially specifies that every time S simulates an assembly α ∈ A[T ], there must be at least one valid growth path in S for each of the possible next steps that T could make from α which results in an assembly in S that maps to that next step.
Let REPR denote the set of all supertile representation functions (i.e., m-block supertile representation functions for some m ∈ Z + ). For some d ∈ {2, 3}, let C be a class of d-dimensional tile assembly systems, and let U be a ddimensional tile set for d ≥ d. Note that every element of C, REPR, and A U <∞ is a finite object, hence can be represented in a suitable format for computation in some formal system such as Turing machines. We say U is intrinsically universal for C at temperature τ ∈ Z + if there are computable functions R : C → REPR and S : , U T simulates T at scale m and using supertile representation function R. That is, R(T ) outputs a representation function that interprets assemblies of U T as assemblies of T , and S(T ) outputs the seed assembly used to program tiles from U to represent the seed assembly of T . We say that U is intrinsically universal for C if it is intrinsically universal for C at some temperature τ ∈ Z + .
3 Temperature 1 self-assembly is not intrinsically universal for the aTAM In this section we prove Theorem 1.2 which is restated below. The proof is for 3D systems, and so as an immediate corollary we get our main theorem, which is for standard 2D systems: Theorem 1.1. In the proof, our chosen temperature 2 tile assembly system T (that "breaks" any claimed simulator) is locally consistent, so we also get Theorem 1.5. Finally, since in the proof we exhibit a specific T that can not be simulated, we also get Theorem 1.6.
Theorem 1.2 There is no 3D tile set U such that U is intrinsically universal at temperature 1 for the class of all aTAM tile assembly systems.

Proof overview of Theorem 1.2
We prove Theorem 1.2 by contradiction. We suppose that there exists a universal tile set U at temperature 1. We then choose a particular temperature 2 tile assembly system T and show that any simulation of T by U must build erroneous assemblies, failing to simulate both dynamics and production in Definition 2.4. The tile assembly system T is illustrated in Figure 4. A seed tile grows two "arms", each of arbitrary length, these arms each grow a "finger" and then try to cooperatively touch their fingers: if they happened to choose arms of equal length the fingers can cooperatively place a keystone tile which leads to flagpole and flag tiles, if not growth stops. Clearly, T is a very simple temperature 2 tile assembly system. 4 Recall that given T , the simulator then gets to choose an arbitrary scale factor m ∈ N and seed assembly σ T for the simulation. Growing from the seed, the universal tile set U simulates a tile assembly system T if and only if it simulates every possible sequence of tile additions producing a terminal assembly of T (at some m-scale blowup). This includes all non-deterministic branches of assembly, such as the various lengths of the arms of T . Our approach is to take a valid simulation that simulates the placing of the keystone, and use it to show that the simulator must also produce another assembly that is invalid, i.e. it is not a simulation of T as defined in Definition 2.2. In particular, when simulating the placing of the keystone, both arms should be the same length, however we show that U must also construct keystone-placing assemblies that have arms of unequal lengths and so are not valid simulations.
In order to construct the invalid assembly, we prove a lemma (called the window movie lemma, Lemma 3.3) that describes an operation for taking two producible assemblies, and combining them to create two new producible assemblies. The lemma is rather general, and it applies to TASs of any temperature producing arbitrary (possibly infinite) assemblies. The window movie lemma can be used as a pumping lemma (generalizing the technique used in the proof of Theorem 3.1 of [3,4]), or used to splice arbitrary assemblies together.
The proof finishes by invoking the fact that U is a temperature 1 system at one key step: the placement of a specific tile by the simulator in (or near) the simulated keystone region. At this point we apply the window movie lemma to the assembly sequence and splice together pieces of the valid assembly to produce a second, invalid assembly, essentially exposing the temperature 1 simulator as a charlatan that is (poorly) faking cooperation. Our proof avoids the use of overly complicated case analyses that often arise when working with temperature 1 systems.

Windows
In order to prove U produces invalid assemblies when simulating the aforementioned system, we develop a technique called window movies for constructing additional producible assemblies of a tile set (U ) and seed σ, given a some initial producible assembly. Window movies share some similarities with the proof of Theorem 3.1 in [3], which shows that thin rectangular assemblies can be "pumped" to create new producible assemblies of arbitrary length. We strengthen the technique in [3] so that assemblies can also be "pumped down", generating producible assemblies smaller than the original assembly. Besides being useful for Theorem 1.1, this lemma gives a general method to combine assemblies together which might be useful elsewhere.
Definition 3.1. A window w is a set of edges forming a cut-set in the infinite grid graph.
Given a window w and an assembly α, a window that intersects α is a partioning of α into two configurations (i.e. after being split into two parts, each part may or may not be disconnected). In this case we say that the window w cuts the assembly α into two configurations α L and α R , where α = α L ∪ α R . Given a window w, its translation by a vector c, written w + c is simply the translation of each of w's elements (edges) by c. Examples of windows are shown in Figure 1. For a window w and an assembly sequence α, we define a window movie M to be the order of placement, position and glue type for each glue that appears along the window w in an assembly sequence α.
Definition 3.2. Given an assembly sequence α and a window w, the associated window movie is the maximal sequence M α,w = (v 0 , g 0 ), (v 1 , g 1 ), (v 2 , g 2 ), . . . of pairs of grid graph vertices v i and glues g i , given by the order of the appearance of the glues along window w in the assembly sequence α. Furthermore, if k glues appear along w at the same instant (this happens upon placement of a tile which has multiple sides touching w) then these k glues appear contiguously and are listed in lexicographical order of the unit vectors describing their orientation in M α,w .
An example of a window movie is shown in Figure 2. Figure 2: Top: A window (thick line) and an assembly sequence along the window. Bottom: The unique induced window movie.
, with l, m ∈ Z + ∪ {∞}, be assembly sequences in T with results α and β, respectively. Let w be a window that partitions α into two configurations α L and α R , and w = w + c be a translation of w that partitions β into two configurations β L and β R . Furthermore, define M α,w , M β,w to be the respective window movies for α, w and β, w , and define α L , β L to be the subconfigurations of α and β containing the seed tiles of α and β, respectively. Then if M α,w = M β,w , it is the case that the following two assemblies are also producible: (1) the assembly α L β R = α L ∪ β R and (2) the assembly Before proceeding, we first define some notation that will be useful for this section of the paper.
For an assembly sequence α = (α i | 0 ≤ i < l), we write | α| = l (note that if α is infinite, then l = ∞). We write α[i] to denote x → t, where x and t are such that α i+1 = α i + ( x → t), i.e., α[i] is the placement of tile type t at position x, assuming that x ∈ ∂ t α i . We define α = α + ( t α i and undefined otherwise, assuming | α| > 0. Otherwise, if | α| = 0, then α = α + ( x → t) = (α 0 ), where α 0 is the assembly such that α 0 ( x) = t and is undefined at all other positions. This is our notation for appending steps to the assembly sequence α: to do so, we must specify a tile type t to be placed at a given location x ∈ ∂ t α i−1 . Proof. We give a constructive proof by giving an algorithm for constructing an assembly sequence yielding α L β R . Let α and β be the assembly sequences of α and β, respectively. Intuitively, the algorithm performs a lossy merge of α and β, ignoring assembly sequence steps of α (respectively, β) that place tiles in α R (β L ). Without loss of generality, and for notational simplicity, let w be a window such that M α,w = M β,w . In other words, the common Initialize i, j, k = 0 and γ to be empty Figure 3: The algorithm to produce a valid assembly sequence γ.
window movie of α and β occur at the same location in the plane, and thus since c = 0, β L = β L and β R = β R . Let M be the sequence of steps in the window movie M α,w . The algorithm in Figure 3 describes how to produce a new valid assembly sequence γ.
If we assume that the assembly sequence γ ultimately produced by the algorithm is valid, then the result of γ is indeed α L β R , since for every tile in α L and β R , the algorithm adds a step to the sequence γ involving the addition of this tile to the assembly. However, we need to prove that the assembly sequence γ is valid, it may be the case that either: 1. there is insufficient bond strength between the tile to be placed and the existing neighboring tiles, or 2. a tile is already present at this location. Case 2 is a non-issue, as locations in α L and β L only have tiles from α L placed in them, and locations in α R and β R only have tiles from β R placed in them. Case 1 is more difficult, and is where the remainder of the proof is spent.
Formally, we claim the following: at each step of the algorithm, the current version of γ at this step is a valid assembly sequence whose result is a producible subassembly of α L β R . Note that the outer loop of the algorithm iterates through all steps of α and β, such that at any point of adding α[i] (or β[j]) to γ, all steps of the window movie occurring before α[i] ( β[j]) in α ( β) have occurred. Similarly, all tiles in α L (or β R ) added to α (β) before step i (j) in the assembly sequence have occurred.
So if the T ile ( α[i]) that is added to the subassembly of α produced after i − 1 steps, can bond at a location in α L to form a τ -stable assembly, the same tile added to the producible assembly of γ must also bond to the same location in γ, as the neighboring glues consist of (i) an identical set of glues from tiles in the subassembly of α L and (ii) glues on the side of the window movie containing α R . Similarly, the tiles of β R must also be able to bind.
So the assembly sequence of γ is valid, i.e. every addition to γ adds a tile to the assembly to form a new producible assembly. Since we have a valid assembly sequence, as argued above, the finished producible assembly is α L β R .
In the proof, we used the two identical window movies to ensure each step in the constructed assembly sequence was valid, i.e. the proposed tile could attach at the specified location. However, if a pair of incident glues in the window movie are not identical, then they are never used to ensure a proposed tile can attach. Using this observation, we define a restricted form of window movie, called a bond-forming submovie, which consists of only those steps of the window movie that place glues that eventually form positivestrength bonds in the assembly. Every window movie M has a unique bondforming submovie B(M ), and Lemma 3.3 can be strengthened by relaxing the requirement that the window movies M α,w = M β,w match:

The simulated tile set
Here we describe the tile assembly system T = (T, σ, 2) to be simulated by the claimed simulator tile set U . The tile set T consists of a small constant number of tile types as seen in Figure 4: the seed σ, eight arm tiles, six finger tiles, a keystone tile, a flagpole tile, and a flag tile. Of the infinite set of terminal assemblies formed, each assembly either contains both the keystone and flag tile types or does not (see Figure 4). The glues in the various tiles are all unique with the exception of the common east-west glue type used within each arm to induce non-deterministic and independent arm lengths. Glues are shown in part (b) of Figure 4. Note that cooperative binding happens at most once during growth, when attaching the keystone tile to two arms of identical length. All other binding events are noncooperative and all glues are strength-2 except for g 11 , g 14 which are strength-1.
Recall that a universal tile set U simulating T carries out the simulation by creating m × m supertiles that represent the tiles of T , and that are placed with the same dynamics (i.e. tile placement ordering, modulo rescaling) as T .
In particular, U must simulate the creation of a terminal assembly with a flag by placing all of the supertiles in both arms first, then the keystone supertile, flagpole supertile, and finally flag supertile. Though U is permitted to place tiles in fuzz supertile regions (i.e. adjacent to supertile regions with a nonempty represented tile type), U cannot put tiles in the flag supertile region before placing tiles that represent the flagpole tile. That is, any assembly sequence of U placing a tile in the flag supertile region must have already simulated an assembly sequence placing the flagpole tile, which in turn must have already simulated an assembly sequence placing the keystone tile, and so on.

Invalid simulation of T
In this section we give the main proof argument for Theorem 1.2 by showing that the tile set U does not simulate T . Let g be the number of glues in the tile set U and let m be the scale factor chosen for T . For the remainder of the proof, we only consider the simulation by U of T in the case that T grows an assembly γ with a pair of arms of identical horizontal length ((g + 1) 6m · (6m)! + 1) · 3 + 6. This length is justified as follows.
By Definition 2.3, there exists γ ∈ A[U] such that R * (γ ) = γ, where U = (U, σ T , 1) is the simulator tile assembly system using tile set U , seed assembly σ T , and temperature 1. The simulator uses scale m, therefore because the definition of cleanly maps to (see Section 2.3) permit one-supertile wide "fuzz" (i.e. the placement of tiles in locations adjacent to supertiles but which don't map to a tile in T ), the vertical height of an arm is at most 3m. Any window that cuts the bottom arm of the simulation α vertically, has one of (g + 1) 6m sets of glues corresponding to 6m locations that glues can appear at and the g + 1 distinct choices for each glue (including the null glue). So any window movie that vertically cuts the bottom arm of the assembly has such a glue set, and one of at most (6m)! possible orderings for these glues to appear in the movie. Then by the pigeonhole principle, examining ((g+1) 6m ·(6m)!+1) such vertical cuts ensures some set of 6m glues and their ordering occurs twice. If the arm has length ((g + 1) 6m · (6m)! + 1) · 3 + 6, examining one vertical cut of the bottom arm in every third supertile of the simulation, ignoring the first and last three supertiles in the arm, also finds a set of 6m glues and their ordering that occurs twice.
We now show how to combine this fact with Corollary 3.4 to construct an assembly, producible by the simulator, but that is not a simulation of any assembly produced by T . Let γ = (γ i | 0 ≤ i < k) be such that the result of γ = γ . Consider the first step i of the assembly sequence γ that places a tile t at some location x, i.e., γ i = γ i−1 + ( x → t), satisfying one of the w γ i−1 (1) the placement of tile t completes a path between the top finger and bottom finger through the keystone supertile, and possibly also through the m × m region of fuzz immediately to the west of the keystone supertile; (2) the placement of tile t is in the flagpole supertile. Now, step backwards in the assembly process by one step and consider γ i−1 , i.e., the assembly at step i − 1 of γ . Since condition (1) has not occurred, there exists a path p along the edges of the grid graph starting from the m×m region that is distance 2m west from the keystone supertile, which travels eastward, threading through the m × m region west of the keystone supertile, then continues threading through the keystone supertile, and then past the east extent of γ i−1 , such that no edge of p crosses an edge shared by matching ⇒ ⇒ Figure 6: Splicing two identical window movies together to produce another valid assembly sequence and terminal assembly by invoking Corollary 3.4 with vertical windows. glues in γ i−1 (see Figure 5). So for any vertical cut of the bottom arm of γ i−1 , one can extend the vertical cut into a window such that the bond-forming submovie of the window only has glues in the vertical cut of the bottom arm of γ i−1 (again, see Figure 5).
Then by the previous counting argument, one can find two such windows w, w with identical bond-forming submovies, as these windows only have glues forming bonds in the vertical cut of the bottom arm (see the left part of Figure 6). Moreover, the two windows have vertical cuts separated horizontally by distance d ≥ 3m and not occurring in the first or last three supertiles of the arm.
This last property is key, as it follows w and w can be modified to follow the same path through the keystone supertile or the fuzz immediately west by selecting a path through these supertiles and duplicating this path twice on both w and w . The two occurrences of this subpath should be separated horizontally by distance d. Then w = w + (d, 0).
Finally, we use information about which condition occurs in step i of the simulation to construct an invalid assembly. From conditions (1) and (2) above we know that t binds to one of α L or β R . Letγ = α L β R + (( x − (d, 0)) → t), i.e., the addition of t to α L β R at the relevant location.
If condition (2) holds (flagpole), then t is placed in a region in which no tile should exist in a simulation with arms not aligned (fuzz in this region is not permitted, by the definition of (diagonal) fuzz in Section 2.3). If condition (1)  holds, then t was originally placed to complete a path between the tips of the top and bottom fingers through the keystone region in γ i . So fromγ we continue placing tiles found on the portion of this path from t to the (here, nonexistent) top or bottom finger, so that we are recreating exactly the path between finger tips found in γ i . Note that these new tiles are all placed within the keystone region and the supertile immediately to the west of the keystone, with the exception of exactly one tile placed either in the m × 1 row of tile locations directly above the keystone above the (shorter) bottom arm (if t was bound to β R ), or in the m × 1 row of tile locations directly below the keystone below the (longer) top arm (if t was bound to β R ). In either case, Definition 2.2 says that the placement of this particular tile implies an invalid simulation by a producible assembly.
To conclude the proof of Theorem 1.2, any claimed universal tile set U simulating T (and in particular the assembly processes with very long but equal-length arms) produces assemblies that do not correspond to a simulation of any assembly produced by T . That is, U does not correctly simulate the production of T (Definition 2.1), hence U does not correctly simulate T (Definition 2.4), and since nothing was assumed about U other than its existance, no such universal tile set exists.

3D temperature-1 aTAM simulates 2D temperature-1 aTAM
In this section, we give a proof of Theorem 1.3. Formally, we show that there exists a 3D aTAM tile set U such that, given an arbitrary 2D aTAM tile system T = (T, σ, 1), where |σ| = 1, there exists an appropriately initialized seed assembly σ T , which depends on T , such that U = (U, σ T , 1) simulates T at scale factor c, for some c ∈ N.
Our construction makes use of several of the techniques from [18]. The basic idea is to use the tiles of U to assemble three-dimensional volumes, called supertiles, each of which represent a single tile from T . The dimensions of each supertile are c × c × 6. The initial supertile which represents σ contains an encoding of the entire tile set T . This encoding is "passed" from each supertile to each newly forming supertile and is used by each supertile to determine the tile type of T that the supertile is supposed to simulate. The encoding of T is also used by each supertile to determine any "output" glues, which may contribute to, if not initiate, the growth of neighboring supertiles.
Before presenting our construction, we first define a useful self-assembly gadget for reading geometrically-specified input.

Read-write gadgets
In temperature 2 tile assembly systems, a tile attachment can be the result of the binding of two strength 1 glues on different sides of the tile. We call this cooperative binding since the two tiles to which the new tile is binding are "cooperating" to allow for its attachment by each sharing a glue, and thus the information encoded in that glue. However, in temperature 1 systems such behavior cannot be enforced because either glue of the pair is sufficient to allow a new tile to bind, possibly ignoring the second glue. This means that if, in order for the correct tile to be placed, it must "collect" information from more than one adjacent tile, then this information cannot be transmitted strictly via glues interacting.
One solution to this problem, in 3D, is to grow a path of tiles, which can potentially split into two (or more) branches, and use a previously placed tile to block the growth of one branch but allow further growth of another branch. The path allowed to continue is thus explicitly provided with information from the glues along the path, as well as implicitly from the fact that it gets to continue. This is a method to handle the fact that we can not do cooperative binding at temperature 1: it uses geometry to transmit the "second" piece of information that must be used to make a decision. In order to ensure that such information is deterministically provided to the growing path, the tiles which block one branch from completing must be guaranteed to have been placed prior to the growth of the path. Since it is possible for any branching paths at temperature 1 to grow independently of each other, with either branch  growing arbitrarily far before the other is extended by even a single tile, it is necessary to force the growth of portions of the assembly, which require such behavior, to be restricted to be a single-tile-wide path. Such a path will zig-zag back and forth in order to "read" the information previously encoded in the geometric placement of blocking tiles.
See Figures 8-10 for examples of a path encoding each of two possible values, which are read by a later portion of the same path.
While the examples of Figures 8-10 demonstrate the ability of a short path of tiles to read one of two possible values (a single bit), we can combine these gadgets to read a sequence of values.
For example, suppose we encode an input string w = w 0 · · · w l−1 as a series of geometric "bumps" and "dents" along a path, then the glues (that connect the tiles) of a path that ultimately navigates these geometric obstacles can effectively read each bit w i , such that after the "reader" path finishes scanning all of the bumps and dents, the input w is stored in the most-recently-added tile t in the reader path. Then it is possible to use t to compute some function   Figure 9 for more details on the growth of the path. z = f (w) of those bits. Then the growth of a final "output" path can be initiated which goes go and builds a path representing the correct pattern of bumps and dents corresponding to the value z. These output bumps and dents can then be used as input for a subsequent "reader" path.
In order to modularize such functionality, we now define a read-write gadget, which is a block of depth 2 or 4 that can be used in any of the three layers L 0 , L 1 and L 2 by simply translating it to the planes z = 0, z = 2 or z = 4, respectively. A read-write gadget is a g × g × d region, for some g ∈ N and d ∈ {2, 4}, with (1) an entrance location, (2) a reading region, (3) at least one output region and (4) zero or more exit locations. In the reading region, a path implicitly reads the geometry of a previously-assembled path of tiles via a series of branching points at which the path may branch one of two possible ways depending on a bit value specified geometrically. An output region is where the path travels after it has finished collecting the input bits specified by the geometry of the reading region, and a single read-write gadget may have output regions on up to 2 different planes (i.e. 0 and 2, or 2 and 4), which is the reason that they may be of depth either 2 or 4, and this is the way that we will transfer information among different levels of the construction. An output region of one read-write gadget may overlap with neighboring read-write gadgets to so that the output of one read-write gadget can serve as the input for the reading section of another read-write gadget. An exit location is where the a path exits the gadget. Note that, after read-write gadget completes its reading phase, its reading path may branch into multiple output paths, whence a read-write gadget may have more than one exit location. See Figure 11 for an example of a read-write gadget, which reads a series of bits A, B, and C (specifically, A = 0, B = 1, and C = 0), and then outputs the bits (A = 1, B = 0, C = 0) before exiting. Note that the input and output are both located on plane z = 0, while both require the placement of some tiles into plane z = 1. Given a constant sized tile set, the number of input values which can be read within a read-write gadget is bounded by a constant, since we propagate information about each branch solely by the glues along the path. In other words, after a reading path navigates each geometrically-specified bit, that bit is concatenated to each of the subsequent glues along the path. Interestingly, this idea can be carried out in very much the same spirit at temperature 1 in 2D if one negative-strength glue is allowed (i.e., a glue that potentially subtracts from-instead of adds to-the total strength with which a tile may bind) [32].
In our construction, we will make the following simplifying assumptions: 1) all read-write gadgets have input on no more than two sides (with respect to the x and y-axes) and located in a single plane, 2) all reading and output regions are on planes z = 0, 2, or 4, with planes z = 1, 3, and 5 reserved for the paths needed to "reach over" and construct output regions, 3. entrance and exit regions are never on the same side and plane, and 4) reading and output regions are never on the same side and plane.

Construction details
First, we divide the 3D space into layers, each of which consist of two consecutive planes. We define layer L 0 as planes z = 0, 1, L 1 as planes z = 2, 3, and L 2 as planes z = 4, 5. We call L 0 the competition layer, and it is used to "decide" which input superside is responsible for choosing the tile from T to be represented and for creating the output supersides. We call L 1 the informa- tion layer, and it is used to help propagate the information to and from input and output supersides. L 2 is the output layer and it selects and distributes the necessary output information for each superside, in effect arranging the "output" glues for each simulated tile (as well as the full definition of T ) into the proper locations to serve as inputs for subsequent supertile formation.
Note that 6 planes in z are not strictly necessary for this construction, and although it can be made to work in 3 (or perhaps even a minimum of 2), modifying the construction to use fewer than 6 planes makes it more complicated and more difficult than it already is to present: therefore, we choose 6 for clarity of presentation. In an effort to simplify the construction for presentation, we describe it in such a way that we subdivide each supertile into a grid of read-write gadgets (all of the same dimensions and with read and output locations for the same set of variables) rather than individual tiles. This will come at the cost of a larger overall scale factor for the simulation, but only by a constant independent of the tile set being simulated.
To help describe our construction, we make use of an example throughout. The tile set used for the example can be seen in Figure 12. The first aspect of the construction which we will explain is the encoding of T by the tiles of U.

Encoding T
To encode T , we make use of the fact that, at temperature 1, the glue on the edge of a tile characterizes the set of all tiles capable of binding to that edge of the tile in any producible assembly (this stands in contrast to temperature 2 systems in which a single strength 1 glue only specifies half of the information for a potential binding event). Therefore, rather than encode any information about the specific glues in T , we simply keep track of all tiles with the ability to bind to each side of each given tile. To do so, let t 0 , t 1 , . . . , t |T |−1 be an enumeration of the tile types in T . We then place read-write gadgets composed of tiles in U in a line so that the edges on a given side output the pattern defined by the algorithm in Figure 13.
This encoding is simply a listing of each tile type t ∈ T which includes, for each tile and each direction, a full list including the number of each tile type t ∈ T and a 'y' if t and t bind along that edge of t (i.e. their glues match) and a 'n' if they don't bind. Further, if t is the last tile type in the list which does bind, instead of a 'y', it is prefaced with an 'f '. (Note that the 'y', 'f ', or 'n' come before the number of the tile type in the enumeration of T .) Thus, the encoding (with numbers written in decimal rather than binary and spaces added to make it easier to read) of the example T from Figure 12 is as follows:

Supersides
We define a superside to be the outermost row of read-write gadgets along the perimeter of one side of a c × c supertile in the construction. Every supertile, other than the seed (see Section 4.2.6 for the structure of the seed) grows from an input superside, which grows from the adjacent output superside of a neighboring supertile. An input superside for a supertile consists of the following components: 1. A binary string h, which encodes the height of the probe (to be defined later), 2. A list S containing the number of each tile type that could bind to the output superside, which placed this input superside (i.e. adjacent to this superside), and 3. The encoding of T (previously discussed).
The list S is simply the list of tile types with each preceded by a 'y', 'f ', or 'n', corresponding to whether or not the supertile could grow to represent a tile of that type. (Yes for those preceded with 'y' or 'f ', no otherwise, with 'f ' marking the last one.) See Section 4.2.1 for more detail. For example, an input superside for a supertile north of a supertile representing tile type 1 would have S encoded as follows (with the numbers represented in binary): "Nn0y1y2n3f4", thus denoting that a tile of type 1, 2, or 4 could bind to the north of a 1 tile.
See Figure 14 for an example of a supertile with all 4 input supersides represented (along with the probes reaching toward the center of the supertile to be described in Section 4.2.3).

The competition layer
The competition layer, L 0 , is the arena in which a battle ensues (between competing probes) to determine the type of tile to be simulated by the newlyforming supertile. Assume that one or more input supersides for a supertile have formed (the seed supertile will have at least one output superside to be used as an input superside for supertile that represents a tile capable of binding to the seed in the simulated system). Each such superside will begin the growth of a log-width binary counter that counts down, beginning from the value h, encoded in the region dednoted by h to 0. This pattern of growth is called a probe, and grows to the location immediately adjacent to the center location of the supertile (the reader should consult the references [17,18] for 2D simulation constructions implementing probes as decreasing binary counters). The center location of a supertile is not formed as a read-write gadget, but instead each probe attempts to grow a single-tile-wide path of tiles from the adjacent read-write gadget to place a tile in the center of the supertile. Exactly one probe will win the competition to reach that center location first and be able to place a tile in that center position, thus "winning the competition" to determine what type the supertile will be. Note that this "competition" does not determine which tile type is to be simulated by this supertile. At this The white squares logically represent tiles as read-write gadgets (rather than individual tiles), and the black squares are used to show the path of glue connectivity between consecutive gadgets and thus the zig-zag growth pattern. Note that, although there is no glue binding between most gadgets in adjacent rows, the information is passed from a previous row to a subsequent row of read-write gadgets via the geometry of the output regions from the read-write gadgets in the previous row. point, we only know the new supertile will grow from the winning superside. After its victory, the supertile will then be able to form the output supersides. Growth of all other (losing) probes is halted by them being blocked from the winning (center) position. Thus, losing probes never leave the competition layer.
Note that as a probe grows, all of the read-write gadgets along its counterclockwise-most side, other than at the very base of the probe, present a special marker value. The read-write gadget closest to the input superside presents another special marker value denoting the end of the probe. The latter marker will be used by the path growing back along the counterclockwise-most side of the winning probe from the (winning) center to the superside from which the winning probe originated as a halting signal. See Figure 15 for an example of a probe winning the competition and then growing a path back down to the superside from which it originated.

The information layer
The main purpose of the information layer, L 1 , is to facilitate the transfer of information between the two other layers of the construction. Figures 16-19 show in yellow the portions of a supertile that grow in into this layer. Other than essentially "bridging the gap" between layers L 0 and L 2 , growth in L 1 is required at the tip of the victorious probe in order to climb over the winning probe in case there are other, losing, probes surrounding the tile placed in the center position of the supertile.

The output layer
After a superside has won the competition via its probe, a path grows back down along the probe until reaching the base, at which point it begins growth in the clockwise direction. It grows in a zig-zag path which rotates the encodings of T , h, and the appropriate new value for the set S on that side, into position to create an output superside (see Figure 21 for an extremely high-level sketch of the process, and see Figure 20 for a basic example of how the zig-zag pattern of growth of read-write gadgets can be used to perform operations such as rotation and splitting of information into two directions). The first step is to select a tile type (by its number) from the set S, which is represented in the input superside. This is done by the first row to grow across the superside.
After reaching the beginning of S, at every position where a character y is encountered, the tile-selection row can nondeterministically choose to select the tile number t immediately following the y. If it chooses t, then the bits of t are marked as selected and the selection is complete. Otherwise, the same choice is possible for each y encountered. If (the number of) no tile has been selected when the f symbol is encountered (there is guaranteed to be 0! (b) After a probe wins, it grows a path back down, along its counterclockwisemost (here, rightmost) side using the information on its east to find the bottom position. It then grows up into layer L1 and over to the original row of the input superside and reads the information from that side (which was output to both L0 and L1) to begin forming the output layer. Figure 15: Example of a probe which begins with h = 10. Each white and grey square represents a read-write gadget, and all of which output to the north of L 0 , while those in the least significant bit position (with labels including 'L') also output to the east of L 0 . exactly one f , otherwise an input superside would not have been created), then this last tile type immediately following the f marker is forced to be selected since it is the last valid choice and a choice must be made. Note that there could be multiple tiles to choose during this process. All entries marked with y, in the case that the system being simulated is nondeterministic, could be selected to attach at this step. Note that this type of nondeterministic selection of tile types does not fairly choose between all choices with equal probability (for the sake of discussion, assigning equal probability 1/k for each of k nondeterministic tile choices for a given binding event). This method is used for simplicity of discussion, but more complex selection methods, which choose options with closer to uniform probability, could be utilized. The reader is encouraged to consult [19] for a discussion of such "random number selection" techniques. These techniques can be implemented using zig-zag growth patterns of read-write gadgets.
Before selecting the bits of the tile type to be simulated, the supertile represents the empty space, i.e., a point in the simulated system that has yet to receive a tile type. However, once the tile-selection row has selected all the bits, we know what tile type it simulates. For a complete description of the representation function, see section 4.2.8. For the selected bits of t, since the encoding of T gets rotated and continues to move upward, the encoding of T is available to have the bits of t pass through it. The bits identifying the number for each tile type encoded in T are marked if they match the bits of t, and after all of the bits of t have passed through the uniquely matching tile type number is identified. This provides subsequent rows of growth the ability to select the encoding of the appropriate side (for the about-to-be-formed superside) for tile type t, so that they can then be rotated into position to become the set S for the output superside.
Since only one input superside can possibly win the competition, and all growth initiated from a side which lost the competition remains in the competition and information layers (L 0 and L 1 ), it is guaranteed that the output layer is completely available for use by the winning superside to grow clockwise around the supertile and create the necessary output supersides. It is important to note that one zig-zagging, one-tile-wide path of tiles is responsible for the growth originating from an input superside, growing the probe, claiming the center position of the supertile, growing back down to the input superside, selecting which tile to represent, moving and rotating the information for new output supersides around the supertile. We must use a single path in order to ensure that any information, which is implicitly represented by the geometry of the read-write gadgets, is in place before needing to be read said information.
At the point when the information necessary to form a new output superside is fully rotated and in position, which may then grow into an input superside for an adjacent supertile, then the single path splits into two paths.
The original path continues to transfer the information around the supertile for all other output supersides (terminating after placing the information for the third output superside), while the new branch is free to potentially begin the growth of and win the competition for the new supertile. However, the new path first grows along the gadgets representing the information for the new superside and checks the values of the new set S. If the location for every tile in S is marked with an n, then there is no tile in T that can attach to this side of the tile being represented by the current supertile and the path building this output superside terminates before it starts to build a corresponding input superside. Otherwise, in the case where there is a tile that could attach to the newly formed output side, the new path continues by growing another row which copies the information for the output superside down to level L 0 . If it is able to complete the growth of the new output superside, then an input superside in the region for an adjacent supertile assembles and begins the growth of the probe for that new supertile. However, if a supertile already exists in that neighboring position and had already placed an input superside into this side of the current supertile (which must have lost the competition for this supertile, else it would be the one creating the output supersides), then the path creating the new output superside will be blocked and will terminate. This is because the slight overlap of the regions representing h (the positions for the least significant bits of each copy of h are in the same location, which puts them in the correct alignment to grow probes directly toward the center of each supertile; see the west side of Figure 17 for a depiction of how the locations for the two encodings of h, north (input) and south (output), overlap). This correctly models simulation since a supertile must already exist in the adjacent position to have placed an input superside here, and therefore it is unnecessary to attempt to grow into that location. Furthermore, if a supertile already exists in the adjacent location but has yet to place an input superside that will prevent the growth of this new superside, that will cause no problem either because the completion of the new superside will only result in a probe which grows toward the center of the adjacent supertile but fails to win the competition. The resulting assembly will not break the simulation of the adjacent supertile (of course, if no probe has yet claimed the center position to win the competition, this superside has a valid chance at doing so).
As the information in the output layer grows clockwise around the supertile, the spacing is designed so that each completed rotation of the information for a superside provides an implicit "counter" that provides the output layer with the information necessary to know when to stop and deposit an output side. Thus, no other counter values need to be encoded and the rotations of the information can provide all of the necessary spacing information for correct growth.
See Figures 16-19 for an example of how an output layer grows. The grey regions represent tiles in the competition layer, L 0 , the yellow those in the information layer, L 1 , and the blue those in the output layer, L 2 . In this series of figures, a scenario is shown where there are four input supersides, all vying for the center position of the supertile, with the southern probe winning that competition. For the sake of depicting the full flow of information and location of information in all input and output supersides, the overlapping positions of encodings of h, which would prevent output supersides from forming where completed input supersides already exist, are ignored. However, the fact that encodings from h's of input supersides use space needed by the encodings of h for the output supersides would actually prevent them from completing since they are unnecessary.

Seed structure
The seed structure σ T is a single supertile which maps to the seed tile s ∈ T . It is the only supertile which has no input supersides. Instead, it has one output superside corresponding to each side of s which has a glue, with the structure of the output superside being identical to the structure of all other output supersides. Specifically, the output superside consists of the outermost read-write gadgets along the perimeter of a given side, which would normally grow from an output layer. In order to provide a connected seed structure, each output superside is connected to the center position of σ T by a singletile-wide path of tiles, and the center position has a tile type unique to the central position of the seed tile. See Figure 22 for an example.       Figure 22: The structure of the seed assembly σ T . Note that there would only be an output superside for each side of the seed tile which has a nonzero strength glue. The other sides would have no tiles present in the seed structure.

Scale factor of the simulation
Here we present the scale factor for the simulation of T . Note that when we discuss the amount of space required for the various encodings, each bit or character, rather than being represented by a single tile, is represented by a read-write gadget. The read-write gadgets used by this construction are constant size, regardless of T , with widths and heights equivalent to the total number of different symbols used in the construction, and the total depth of the simulation is always 6. Since the increase in the scale caused by the use of read-write gadgets is constant, we ignore it for the rest of this discussion.
First, we discuss the length of the encoding of T . For each t ∈ T , we encode the number assigned to t, which is of length O(log |T |). Then, for each of the 4 sides of t we encode a single character (N ,E,S,or W ) and a list which contains the number assigned to each tile type and a single character (y, f , or n), for a length of 4(1 + |T |(O(log |T |) + 1)) = O(|T | log |T |). Finally, for each tile there is a single character, D, at the end. This results in a total encoding of size O(|T | log |T |) for each tile type. Given the encoding of |T | tile types and two more characters (B and F ), the full encoding of T requires space O(|T | 2 log |T |).
The scale factor of the simulation is determined by the length of the sides of the supertiles. Each side must be sized that that it can contain 1. a constant sized gap at each corner (size O(1)), 2. two copies of the encoding of T (size O(|T | 2 log |T |)), 3. two encodings of S, each of which are the encoding of a single side of one tile type (size O(|T | log |T |)), and 4. two copies of h, which is the log of the probe height. To determine the height to which a probe must grow, we first assume that the sides of each supertile contain only the copies of T and S, which makes each side of width 2O(|T | 2 log |T |) + 2O(|T | log |T |) = O(|T | 2 log |T |). If all sides were of that length, to get to the center, a probe would need to grow to height h = O(|T | 2 log |T |)/2 = O(|T | 2 log |T |), which can be encoded in log h = O(log(|T | 2 log |T |)) space. We then let h = h + (2 log h )/2 to account for the additional distance a probe must grow to account for the two copies of h encoded in each side and note that log h = O(log(|T | 2 log |T |)). (Note that to get side lengths and a value for h which cause the probes to all grow to within exactly one distance of a read-write gadget from the exact center of the supertile, some "padding" of up to width log h may be added between the encodings of S and h). Thus the size of each side, and therefore the scale factor for the simulation, is O(|T | 2 log |T |).

Representation function
The representation function R for the simulation of a tile set T maps supertiles over U to tiles of T as follows. For a supertile s, if there is no tile in the center location, it maps to an empty location. If there is a tile in the center, if it is the special center tile for the seed, s maps to the seed σ, otherwise R follows the path back down the probe and to the point that a tile number is selected from the set S. The tile number uniquely identifies the tile t ∈ T that s represents.