# Strict Self-Assembly of Discrete Self-Similar Fractal Shapes

Florent Becker

► To cite this version:

Florent Becker. Strict Self-Assembly of Discrete Self-Similar Fractal Shapes. 2024. hal-04571345v3

HAL Id: hal-04571345

https://hal.science/hal-04571345v3

Preprint submitted on 30 May 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution - ShareAlike 4.0 International License
# Strict Self-Assembly of Discrete Self-Similar Fractal Shapes

Florent Becker

<figure><img src="image_1.png" /></figure>

LIFO — Université d'Orléans, rue Léonard de Vinci
45000 Orléans, France

## Abstract

This paper gives a (polynomial time) algorithm to decide whether a given Discrete Self-Similar Fractal Shape can be assembled in the aTAM model.

In the positive case, the construction relies on a Self-Assembling System in the aTAM which strictly assembles a particular self-similar fractal shape, namely a variant $K^\infty$ of the Sierpinski Carpet. We prove that the aTAM we propose is correct through a novel device, *self-describing circuits* which are generally useful for rigorous yet readable proofs of the behaviour of aTAMs.

We then discuss which self-similar fractals can or cannot be strictly self-assembled in the aTAM. It turns out that the ability of iterates of the generator to pass information is crucial: either this *bandwidth* is eventually sufficient in both cardinal directions and $K^\infty$ appears within the fractal pattern after some finite number of iterations, or that bandwidth remains ever insufficient in one direction and any aTAM trying to self-assemble the shape will end up with an ultimately periodic pattern.

**2012 ACM Subject Classification** Theory of computation → Abstract machines; Theory of computation → Timed and hybrid models; Theory of computation → Computational geometry

**Keywords and phrases** Molecular Self-assembly, Discrete Fractals, Substitutions

## 1 Introduction

There is an area of particular interest at the intersection between dynamical systems, models of computation and automata, and discrete geometry. There, researchers try to determine the limits of various models of computation when faced with geometrical constraints, and to relate them with the dynamic properties of the models. This paper deals with Self-Assembling Tilings in the Abstract Tile Assembly Model (aTAM), as introduced by Winfree [21]. In addition to its *raison d'être* as an abstract model of DNA computing, this model enjoys an interest as an intermediary between one-dimensional and two-dimensional Cellular Automata (CAs), as well as a kind of asynchronous version of CAs and tilings.

Two features distinguish this model from more classical models such as Cellular Automata: the fact that it consumes the space it computes in, forcing a steady growth of its output; as well as its asynchronicity. The aTAM is able to simulate classical models such as Turing Machines and Cellular Automata [21] by covering large rectangles in a synchronized manner. The synchronization can be wrought from the jaws of the environment's asynchronicity using so called "Temperature 2" systems where the local attachement of a tile to a site can depend from the concomitant presence of two tiles on neighboring sites. This synchronization can also be substituted for by a richer local geometry, such as 3D space [2], or the presence of a variety of tiles shapes [12].

This hints that much of the subtelty of the asynchronous and write-only nature of the aTAM reflects in its ability to assemble fine geometrical features. Since 2010 [20], a particular focus has been set on so-called Discrete Self-Similar Fractal Shapes (DSSFS) as candidates for being tough to assemble in the aTAM and allowing to pinpoint the subtelty of its variants. In order to meaningfully constrain the aTAM using the geometry of the shape that is being assembled, this line of research investigates its *strict* self-assembly. That is, the authors
# Strict Self-Assembly of Discrete Self-Similar Fractal Shapes

Florent Becker

<figure><img src="image_2.png" /></figure>

LIFO — Université d'Orléans, rue Léonard de Vinci
45000 Orléans, France

## Abstract

This paper gives a (polynomial time) algorithm to decide whether a given Discrete Self-Similar Fractal Shape can be assembled in the aTAM model.

In the positive case, the construction relies on a Self-Assembling System in the aTAM which strictly assembles a particular self-similar fractal shape, namely a variant $K^\infty$ of the Sierpinski Carpet. We prove that the aTAM we propose is correct through a novel device, *self-describing circuits* which are generally useful for rigorous yet readable proofs of the behaviour of aTAMs.

We then discuss which self-similar fractals can or cannot be strictly self-assembled in the aTAM. It turns out that the ability of iterates of the generator to pass information is crucial: either this *bandwidth* is eventually sufficient in both cardinal directions and $K^\infty$ appears within the fractal pattern after some finite number of iterations, or that bandwidth remains ever insufficient in one direction and any aTAM trying to self-assemble the shape will end up with an ultimately periodic pattern.

**2012 ACM Subject Classification** Theory of computation → Abstract machines; Theory of computation → Timed and hybrid models; Theory of computation → Computational geometry

**Keywords and phrases** Molecular Self-assembly, Discrete Fractals, Substitutions

## 1 Introduction

There is an area of particular interest at the intersection between dynamical systems, models of computation and automata, and discrete geometry. There, researchers try to determine the limits of various models of computation when faced with geometrical constraints, and to relate them with the dynamic properties of the models. This paper deals with Self-Assembling Tilings in the Abstract Tile Assembly Model (aTAM), as introduced by Winfree [21]. In addition to its *raison d'être* as an abstract model of DNA computing, this model enjoys an interest as an intermediary between one-dimensional and two-dimensional Cellular Automata (CAs), as well as a kind of asynchronous version of CAs and tilings.

Two features distinguish this model from more classical models such as Cellular Automata: the fact that it consumes the space it computes in, forcing a steady growth of its output; as well as its asynchronicity. The aTAM is able to simulate classical models such as Turing Machines and Cellular Automata [21] by covering large rectangles in a synchronized manner. The synchronization can be wrought from the jaws of the environment's asynchronicity using so called "Temperature 2" systems where the local attachement of a tile to a site can depend from the concomitant presence of two tiles on neighboring sites. This synchronization can also be substituted for by a richer local geometry, such as 3D space [2], or the presence of a variety of tiles shapes [12].

This hints that much of the subtelty of the asynchronous and write-only nature of the aTAM reflects in its ability to assemble fine geometrical features. Since 2010 [20], a particular focus has been set on so-called Discrete Self-Similar Fractal Shapes (DSSFS) as candidates for being tough to assemble in the aTAM and allowing to pinpoint the subtelty of its variants. In order to meaningfully constrain the aTAM using the geometry of the shape that is being assembled, this line of research investigates its *strict* self-assembly. That is, the authors
demand that in order to assemble a shape $S$, no tile is ever put outside of $S$.

This program has seen some progress, with two lines of results. The first line of results [6, 1, 15, 20, 13] looks at close variants of DSSFS, either slightly laxer and showing that they can be obtained by aTAM system, or restricted sets of DSSFS and showing that they cannot be obtained. The second line of results [11, 10] looks at variants of the aTAM, generally more powerful ones, showing that they can assemble (some) DSSFS.

The big question since [20] has been whether the *plain* model (aTAM) can self-assemble some *unadultered* DSSFS. The conjecture has generally been that their geometry is too complicated for the aTAM, that is that *there was no aTAM system able to uniquely and strictly self-assemble a DSSFS*. In order to characterize these geometrical constraints, several notions have been proposed, such as $\zeta$-dimension and sparsity [8, 9], and ease of disconnecting [11, 6, 1]. This paper answers the question differently: not only there *is* a DSFSS which can be strictly self-assembled, in fact most DSSFS can indeed be self-assembled, as long as a periodic tiling by their generator is well connected.

The positive construction of this paper relies on a family of ideas from the theory of Tilings. The hierarchical structure of discrete fractals is a lot alike that of many aperiodic tilings. In trying to assemble such a hierarchical shape, one can take inspiration from authors such as Mozes or Goodman-Strauss [7, 18] who use a system with several layers of information checking each other's work in order to impose from local rules the desired global hierarchy. Like theirs, the construction uses several layers carrying the same information at different scales. This part of the construction is somewhat simpler than in tilings thanks to the *seeded* nature of the assembly. In tilings again, Durand, Romashchenko and Shen show in [4] another way to impose such a structure, by obtaining their tiling through a Fixed-Point Theorem. The approach here through *self-describing circuits* is a bastardization of these two, with some tricks of its own to deal with the lack of global synchronisation in the assembly. The way it is presented, through a circuit, is a necessity to deal with the proof of a big aTAM system acting in an environment with non-trivial geometric constraints, but it can certainly be useful as a tool to express and study many constructions in the aTAM model.

The characterization of the fractal shapes which *cannot* be assembled in the aTAM relies on a Pumping Lemma in the tradition of [17]. This Pumping Lemma limits the amount of computation that can be done in the assembly by looking at its *treewidth*, or equivalently, the size of the largest square it encircles. This is a formalization of a new limit to computing power in the aTAM, and it should apply in a variety of settings, with a *je-ne-sais-quoi* of Complexity Theory.

The presentation will start in Section 2 with the definitions of the abstract Tile Assembly Model, as well as the statement of the Tree Pump Lemma (Lemma 8) and the difference between *weak* and *strict* assembly of shapes. The paper then covers the basics about discrete self-similar fractal shapes, and states the main positive result, Theorem 15. Then, Section 3 presents Self-Describing Embedded Circuits which form the main proof device for Theorem 15; they are put to use in Section 4, concluding the proof of the positive construction. Finally, Section 5 delimitates the fractal shapes which can be constructed through the aTAM. The dichotomy there is quite sharp: for a given shape $S$, either the technique of Theorem 15 can be straightforwardly adapted to $S$ or there is no way at all to obtain it in the aTAM. Lemma 53 concludes the paper with a polynomial-time algorithm to distinguish between the two situations.
2 Strict Self-Assembly of Fractals

demand that in order to assemble a shape $S$, no tile is ever put outside of $S$.

This program has seen some progress, with two lines of results. The first line of results [6, 1, 15, 20, 13] looks at close variants of DSSFS, either slightly laxer and showing that they can be obtained by aTAM system, or restricted sets of DSSFS and showing that they cannot be obtained. The second line of results [11, 10] looks at variants of the aTAM, generally more powerful ones, showing that they can assemble (some) DSSFS.

The big question since [20] has been whether the *plain* model (aTAM) can self-assemble some *unadultered* DSSFS. The conjecture has generally been that their geometry is too complicated for the aTAM, that is that *there was no aTAM system able to uniquely and strictly self-assemble a DSSFS*. In order to characterize these geometrical constraints, several notions have been proposed, such as $\zeta$-dimension and sparsity [8, 9], and ease of disconnecting [11, 6, 1]. This paper answers the question differently: not only there *is* a DSFSS which can be strictly self-assembled, in fact most DSSFS can indeed be self-assembled, as long as a periodic tiling by their generator is well connected.

The positive construction of this paper relies on a family of ideas from the theory of Tilings. The hierarchical structure of discrete fractals is a lot alike that of many aperiodic tilings. In trying to assemble such a hierarchical shape, one can take inspiration from authors such as Mozes or Goodman-Strauss [7, 18] who use a system with several layers of information checking each other's work in order to impose from local rules the desired global hierarchy. Like theirs, the construction uses several layers carrying the same information at different scales. This part of the construction is somewhat simpler than in tilings thanks to the *seeded* nature of the assembly. In tilings again, Durand, Romashchenko and Shen show in [4] another way to impose such a structure, by obtaining their tiling through a Fixed-Point Theorem. The approach here through *self-describing circuits* is a bastardization of these two, with some tricks of its own to deal with the lack of global synchronisation in the assembly. The way it is presented, through a circuit, is a necessity to deal with the proof of a big aTAM system acting in an environment with non-trivial geometric constraints, but it can certainly be useful as a tool to express and study many constructions in the aTAM model.

The characterization of the fractal shapes which *cannot* be assembled in the aTAM relies on a Pumping Lemma in the tradition of [17]. This Pumping Lemma limits the amount of computation that can be done in the assembly by looking at its *treewidth*, or equivalently, the size of the largest square it encircles. This is a formalization of a new limit to computing power in the aTAM, and it should apply in a variety of settings, with a *je-ne-sais-quoi* of Complexity Theory.

The presentation will start in Section 2 with the definitions of the abstract Tile Assembly Model, as well as the statement of the Tree Pump Lemma (Lemma 8) and the difference between *weak* and *strict* assembly of shapes. The paper then covers the basics about discrete self-similar fractal shapes, and states the main positive result, Theorem 15. Then, Section 3 presents Self-Describing Embedded Circuits which form the main proof device for Theorem 15; they are put to use in Section 4, concluding the proof of the positive construction. Finally, Section 5 delimitates the fractal shapes which can be constructed through the aTAM. The dichotomy there is quite sharp: for a given shape $S$, either the technique of Theorem 15 can be straightforwardly adapted to $S$ or there is no way at all to obtain it in the aTAM. Lemma 53 concludes the paper with a polynomial-time algorithm to distinguish between the two situations.
# 2 Definitions and statement of the main results

## 2.1 Notations

A variable with an arrow such as $\vec{a}$ denotes a vector of values indexed by some set $S$. Given $s \in S$, $a_s$ is the element of $\vec{a}$ associated with $s$.

For any sets $A, B$ and $S$, given $\vec{a} \in A^S$ and $\vec{b} \in B^S$, the standard notation $\vec{a} \otimes \vec{b}$ is the vector $\vec{v} \in (A \times B)^S$ defined by $\forall s \in S, v_s = (a_s, b_s)$. Likewise, given $f : A^I \to A^O$ and $g : B^I \to B^O$, the function $f \otimes g : (A \times B)^I \to (A \times B)^O$ is defined by $(f \otimes g)(\vec{a} \otimes \vec{b}) = f(\vec{a}) \otimes g(\vec{b})$.

The unit vectors $(0, 1)$, $(1, 0)$, $(0, -1)$, $(-1, 0)$ of $\mathbb{Z}^2$ are noted $N, E, S, W$ respectively. An oriented edge of $\mathbb{Z}^2$ is an arc, noted $(a \to b)$; its direction is the unit vector $b-a \in \{N, E, S, W\}$. Given an arc $e = (a \to b)$ and a vector $v \in \mathbb{Z}^2$, $e + v = (a + v \to b + v)$. The arc out of $a \in \mathbb{Z}^2$ in direction $d \in \{N, E, S, W\}$ is $(a \to a + d)$.

Let $P$ be a finite subset of $\mathbb{N}^2$, with $w = \max(x|(x, y) \in P)$ and $h = \max(y|(x, y) \in P)$. Then for $z = (x, y) \in \mathbb{Z}^2$, $\lfloor z/P \rfloor$ is the pair $(\lfloor x/w \rfloor, \lfloor y/h \rfloor)$ and $z \bmod P$ is the pair $(x \bmod w, y \bmod h)$.

The constructions in Section 3 and 4 make heavy use of sets built as cartesian products. In an attempt to make their exposition more readable and distinguish the function of each component of the product, they are given in a “record” or “object” like syntax using `$\{\}\{\}$` for record construction and “$x \cdot$ field” for field access. That is, given a base set $X$ and a finite set of $k$ labels such as $L = \{\text{zeroth, first, second, \dots, not-quite-k-th}\}$, the element $x = (x_0, x_1, x_2, \dots, x_{k-1})$ is written $x = \{\text{zeroth} = x_0, \text{first} = x_1, \dots, \text{not-quite-k-th} = x_{k-1}\}$. Symetrically, $x_0$ can be extracted from $x$ by writing $x \cdot$ zeroth. A judicious set of labels can make this notation actually useful.

## 2.2 Self-assembly and the Abstract Tile-Assembly Model

### 2.2.1 Definitions

There follows a brief exposition of the basic definition of the aTAM. The survey by Patitz [19] as well as the classical article by Winfree [21] give a far less telegraphic exposition.

**Definition 1 (Wang Tile).** Given an alphabet $\Sigma$, a Wang Tile is an element of $\Sigma^{\{N,E,S,W\}}$, i.e. a unit square with an element of $\Sigma$ on each of its sides. Given $w \in \Sigma^{\{N,E,S,W\}}$ and $d \in \{N, E, S, W\}$, $w(d)$ is referred to as the color of the $d$ side of $w$.

**Definition 2 (Assembly).** Given a set $W$ of Wang Tiles, an assembly of $W$ is a partial function $A : \mathbb{Z}^2 \to W$. It is finite if its domain is. The notation $z \in A$ should be read as $z \in \text{dom}(A)$, or equivalently “$A(z)$ is defined”.

The set of assemblies on $W$ is noted $W^{\subset \mathbb{Z}^2}$.

**Definition 3 (aTAM).** Let $\Sigma$ be an alphabet, an unseeded Tile Assembly System $T$ is a triplet

$$ \left\{ \begin{array}{ll} \text{tileset} & \in \Sigma^{\{N,E,S,W\}} \\ \text{strength-function} & : \quad \Sigma \to \mathbb{Z} \\ \text{temperature} & \in \mathbb{N} \end{array} \right\}. $$

A seeded Tile Assembly System $T'$ is a quadruplet

$$ \left\{ \begin{array}{ll} \text{tileset} & \in \Sigma^{\{N,E,S,W\}} \\ \text{strength-function} & : \quad \Sigma \to \mathbb{Z} \\ \text{temperature} & \in \mathbb{N} \\ \text{seed} & \in (T' \cdot \text{tileset})^{\subset \mathbb{Z}^2} \end{array} \right\}. $$
# 2 Definitions and statement of the main results

## 2.1 Notations

A variable with an arrow such as $\vec{a}$ denotes a vector of values indexed by some set $S$. Given $s \in S$, $a_s$ is the element of $\vec{a}$ associated with $s$.

For any sets $A, B$ and $S$, given $\vec{a} \in A^S$ and $\vec{b} \in B^S$, the standard notation $\vec{a} \otimes \vec{b}$ is the vector $\vec{v} \in (A \times B)^S$ defined by $\forall s \in S, v_s = (a_s, b_s)$. Likewise, given $f : A^I \to A^O$ and $g : B^I \to B^O$, the function $f \otimes g : (A \times B)^I \to (A \times B)^O$ is defined by $(f \otimes g)(\vec{a} \otimes \vec{b}) = f(\vec{a}) \otimes g(\vec{b})$.

The unit vectors $(0, 1)$, $(1, 0)$, $(0, -1)$, $(-1, 0)$ of $\mathbb{Z}^2$ are noted $N, E, S, W$ respectively. An oriented edge of $\mathbb{Z}^2$ is an arc, noted $(a \to b)$; its direction is the unit vector $b-a \in \{N, E, S, W\}$. Given an arc $e = (a \to b)$ and a vector $v \in \mathbb{Z}^2$, $e + v = (a + v \to b + v)$. The arc out of $a \in \mathbb{Z}^2$ in direction $d \in \{N, E, S, W\}$ is $(a \to a + d)$.

Let $P$ be a finite subset of $\mathbb{N}^2$, with $w = \max(x|(x, y) \in P)$ and $h = \max(y|(x, y) \in P)$. Then for $z = (x, y) \in \mathbb{Z}^2$, $\lfloor z/P \rfloor$ is the pair $(\lfloor x/w \rfloor, \lfloor y/h \rfloor)$ and $z \bmod P$ is the pair $(x \bmod w, y \bmod h)$.

The constructions in Section 3 and 4 make heavy use of sets built as cartesian products. In an attempt to make their exposition more readable and distinguish the function of each component of the product, they are given in a “record” or “object” like syntax using `$\{\}\{\}$` for record construction and “$x \cdot$ field” for field access. That is, given a base set $X$ and a finite set of $k$ labels such as $L = \{\text{zeroth, first, second, \dots, not-quite-k-th}\}$, the element $x = (x_0, x_1, x_2, \dots, x_{k-1})$ is written $x = \{\text{zeroth} = x_0, \text{first} = x_1, \dots, \text{not-quite-k-th} = x_{k-1}\}$. Symetrically, $x_0$ can be extracted from $x$ by writing $x \cdot$ zeroth. A judicious set of labels can make this notation actually useful.

## 2.2 Self-assembly and the Abstract Tile-Assembly Model

### 2.2.1 Definitions

There follows a brief exposition of the basic definition of the aTAM. The survey by Patitz [19] as well as the classical article by Winfree [21] give a far less telegraphic exposition.

**Definition 1 (Wang Tile).** Given an alphabet $\Sigma$, a Wang Tile is an element of $\Sigma^{\{N,E,S,W\}}$, i.e. a unit square with an element of $\Sigma$ on each of its sides. Given $w \in \Sigma^{\{N,E,S,W\}}$ and $d \in \{N, E, S, W\}$, $w(d)$ is referred to as the color of the $d$ side of $w$.

**Definition 2 (Assembly).** Given a set $W$ of Wang Tiles, an assembly of $W$ is a partial function $A : \mathbb{Z}^2 \to W$. It is finite if its domain is. The notation $z \in A$ should be read as $z \in \text{dom}(A)$, or equivalently “$A(z)$ is defined”.

The set of assemblies on $W$ is noted $W^{\subset \mathbb{Z}^2}$.

**Definition 3 (aTAM).** Let $\Sigma$ be an alphabet, an unseeded Tile Assembly System $T$ is a triplet

$$ \left\{ \begin{array}{ll} \text{tileset} & \in \Sigma^{\{N,E,S,W\}} \\ \text{strength-function} & : \quad \Sigma \to \mathbb{Z} \\ \text{temperature} & \in \mathbb{N} \end{array} \right\}. $$

A seeded Tile Assembly System $T'$ is a quadruplet

$$ \left\{ \begin{array}{ll} \text{tileset} & \in \Sigma^{\{N,E,S,W\}} \\ \text{strength-function} & : \quad \Sigma \to \mathbb{Z} \\ \text{temperature} & \in \mathbb{N} \\ \text{seed} & \in (T' \cdot \text{tileset})^{\subset \mathbb{Z}^2} \end{array} \right\}. $$
4 Strict Self-Assembly of Fractals

In both cases, the notation $T^{\subset \mathbb{Z}^2}$ refers to the set of assemblies $(T \cdot \text{tileset})^{\subset \mathbb{Z}^2}$.

The crucial differences between a Tile Assembly System and a mere set of Wang Tiles are its strength function and its temperature. The strength function defines the *binding strength* of an edge of an assembly.

**Definition 4 (Binding).** Let $S$ be a Tile Assembly System, and $A \in S^{\subset \mathbb{Z}^2}$. Let $e$ be an edge between two positions $z, z' = z + d$ in $A$. The binding $b(e)$ of $e$ in $A$ is

- $0$ if $A(z)(d) \neq A(z')(\bar{-}d)$, and

- $S$-strength($g$) if $A(z)(d) = A(z')(\bar{-}d) = g$.

Given a set $E$ of edges of $A$, the binding strength of $E$ is $b(E) = \sum_{e \in E} b(e)$.

This binding strength corresponds to forces tying the assembly together in the face of thermal agitation. This thermal agitation is modeled by $S$-temperature. Whenever an assembly has a cut with a binding strength less than the temperature, it will tend to be torn along this cut by thermal agitation. Assemblies which do not have such cuts are *stable*.

**Definition 5 (Stable assembly).** Given a Tile Assembly System $S$, an assembly $A \in S^{\subset \mathbb{Z}^2}$ is stable if for any cut $C$ of $A$, $b(C) \geq S$-temperature

Stability begets a definition for the dynamics of the process of self-assembly: tiles are added to an assembly as long as the resulting new assembly is stable.

**Definition 6 (Attachment, Assembly Sequence).** Given a Tile Assembly System $S$ and an assembly $A \in S^{\subset \mathbb{Z}^2}$, an attachment candidate is a pair $t@z$, with $t \in S$-tileset and $z \in \mathbb{Z}^2$. It is valid if $z \notin \text{dom } A$ and stable if $A' = A \cup \{z \mapsto t\}$ is stable. If it is both valid and stable, it is an attachment, noted $A \xrightarrow{t@z} A'$

An assembly $A'$ follows from an assembly $A$ if there is a sequence of attachments $A_0 = A \xrightarrow{t_1@z_1} A_1 \xrightarrow{t_2@z_2} \dots \xrightarrow{t_k@z_k} A_k = A'$. Such a sequence is an assembly sequence from $A$ to $A'$. It is noted $\alpha = A \to_S A'$, and $A'$ is noted $\lim \alpha$. If $\alpha$ is infinite, then $\lim \alpha = \bigcup_i A_i$.

The set of assembly sequences following from a given assembly $A$ is noted $\mathcal{H}[S, A]$, and $A[S, A] = \{\lim \alpha | \alpha \in \mathcal{H}[S, A]\}$.

An assembly is terminal if $A[S, A] = \{A\}$. The set of terminal assemblies following from $A$ is $A^{\square}[S, A]$.

Given a seeded Tile Assembly System, its productions are the assemblies following from its seed.

**Definition 7 (Production, Terminal Production).** Given a seeded Tile Assembly System $S$, a production is an assembly which follows from $S$-seed.

The set of productions of $S$ is noted $A[S]$, and the set of terminal productions is noted $A^{\square}[S]$. Likewise, $\mathcal{H}[S] = \mathcal{H}[S, S \cdot \text{seed}]$.

Note that a production may be infinite but not terminal.

Given a subset $X \subset \mathbb{Z}^2$, the restriction of an assembly sequence $\alpha$ to $X$, noted $\alpha|_X$, is the sequence of attachments of $\alpha$ taking place within $X$. Likewise, for an assembly $A$, $A|_X$ is the restriction of $A$ to the positions within $X$.
4 Strict Self-Assembly of Fractals

In both cases, the notation $T^{\subset \mathbb{Z}^2}$ refers to the set of assemblies $(T \cdot \text{tileset})^{\subset \mathbb{Z}^2}$.

The crucial differences between a Tile Assembly System and a mere set of Wang Tiles are its strength function and its temperature. The strength function defines the *binding strength* of an edge of an assembly.

**Definition 4 (Binding).** Let $S$ be a Tile Assembly System, and $A \in S^{\subset \mathbb{Z}^2}$. Let $e$ be an edge between two positions $z, z' = z + d$ in $A$. The binding $b(e)$ of $e$ in $A$ is

$$ \text{0 if } A(z)(d) \neq A(z')(\bar{d}) \text{, and} $$

$$ \text{S strength}(g) \text{ if } A(z)(d) = A(z')(\bar{d}) = g. $$

Given a set $E$ of edges of $A$, the binding strength of $E$ is $b(E) = \sum_{e \in E} b(e)$.

This binding strength corresponds to forces tying the assembly together in the face of thermal agitation. This thermal agitation is modeled by $S$-temperature. Whenever an assembly has a cut with a binding strength less than the temperature, it will tend to be torn along this cut by thermal agitation. Assemblies which do not have such cuts are *stable*.

**Definition 5 (Stable assembly).** Given a Tile Assembly System $S$, an assembly $A \in S^{\subset \mathbb{Z}^2}$ is stable if for any cut $C$ of $A$, $b(C) \geq S$-temperature

Stability begets a definition for the dynamics of the process of self-assembly: tiles are added to an assembly as long as the resulting new assembly is stable.

**Definition 6 (Attachment, Assembly Sequence).** Given a Tile Assembly System $S$ and an assembly $A \in S^{\subset \mathbb{Z}^2}$, an attachment candidate is a pair $t@z$, with $t \in S$-tileset and $z \in \mathbb{Z}^2$. It is valid if $z \notin \text{dom } A$ and stable if $A' = A \cup \{z \mapsto t\}$ is stable. If it is both valid and stable, it is an attachment, noted $A \xrightarrow{t@z} A'$

An assembly $A'$ follows from an assembly $A$ if there is a sequence of attachments $A_0 = A \xrightarrow{t_1@z_1} A_1 \xrightarrow{t_2@z_2} \dots \xrightarrow{t_k@z_k} A_k = A'$. Such a sequence is an assembly sequence from $A$ to $A'$. It is noted $\alpha = A \to_S A'$, and $A'$ is noted $\lim \alpha$. If $\alpha$ is infinite, then $\lim \alpha = \bigcup_i A_i$.

The set of assembly sequences following from a given assembly $A$ is noted $\mathcal{H}[S, A]$, and $A[S, A] = \{\lim \alpha | \alpha \in \mathcal{H}[S, A]\}$.

An assembly is terminal if $A[S, A] = \{A\}$. The set of terminal assemblies following from $A$ is $A^{\square}[S, A]$.

Given a seeded Tile Assembly System, its productions are the assemblies following from its seed.

**Definition 7 (Production, Terminal Production).** Given a seeded Tile Assembly System $S$, a production is an assembly which follows from $S$-seed.

The set of productions of $S$ is noted $A[S]$, and the set of terminal productions is noted $A^{\square}[S]$. Likewise, $\mathcal{H}[S] = \mathcal{H}[S, S \cdot \text{seed}]$.

Note that a production may be infinite but not terminal.

Given a subset $X \subset \mathbb{Z}^2$, the restriction of an assembly sequence $\alpha$ to $X$, noted $\alpha|_X$ is the sequence of attachments of $\alpha$ taking place within $X$. Likewise, for an assembly $A$, $A|_X$ is the restriction of $A$ to the positions within $X$.
### 2.2.2 The Tree Pump Lemma

No paper about self-assembly would be complete without a “pump or die” lemma in the style of [17]. This one examines the case of skinny productions, that is those who do not encircle any square larger than $N$ for some fixed $N$. The crucial property which makes them simple(-ish) is their bounded treewidth. The interest of this lemma —especially for eight year olds— is that it lets the user direct the flow of the firehose.

**► Lemma 8 (Tree Pump).** For any aTAM system $S$ with $S$-seed finite and connected, define the following sets of assemblies:

- for any integer $m$, $C_m[S]$ is the set of assemblies of $S$ which encircle an $m \times m$ square;

- for any real $k$ and vector $\vec{d}$, $B_{k,\vec{d}}[S]$ is the set of assemblies of $S$ which do not cover any position $\vec{p}$ such that $\vec{p} \cdot \vec{d} > k + |S$-seed|

- for any vector $\vec{d}$, $P_{\vec{d}}[S]$ is the set of ultimately periodic assemblies of $S$ such that there is a vector $\vec{p}$ with $|\vec{p} \cdot \vec{d}| > 0$ and a non-empty sub-assembly $a \subseteq A$ such that $a + \vec{p} \subseteq a$.

Then, there is a function $F: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$ such that for aTAM system $S$ with $n$ tiles and a 1-tile seed, integer $m$ and unit vector $\vec{d}$ of $\mathbb{R}^2$,

$$A \Box [S] \cap (C_m[S] \cup B_{F(n,m),\vec{d}}[S] \cup P_{\vec{d}}[S]) \neq \emptyset.$$

<figure><img src="image_2.png" /><figcaption>■ **Figure 1** The three sets defined by Lemma 8: $C_m[S]$ is the assemblies which encircle an $m \times m$ square, $B_{F(n,m),\vec{d}}[S]$ is the set of assemblies which do not reach further than $F(n,m)$ in direction $\vec{d}$, and $P_{\vec{d}}[S]$ is the assemblies which contain a periodic path with period $\vec{p}$ such that $\vec{p} \cdot \vec{d} > 0$.</figcaption></figure>

The Tree Pump Lemma states that in order to do a meaningful amount of computation, a self-assembling system with $n$ tiles needs to encircle large squares —say, of size $m$, thus hitting $C_m[S]$. If it does not, then its productions look very much like trees drawn on $\mathbb{Z}^2$
### 2.2.2 The Tree Pump Lemma

No paper about self-assembly would be complete without a “pump or die” lemma in the style of [17]. This one examines the case of skinny productions, that is those who do not encircle any square larger than $N$ for some fixed $N$. The crucial property which makes them simple(-ish) is their bounded treewidth. The interest of this lemma —especially for eight year olds— is that it lets the user direct the flow of the firehose.

**► Lemma 8 (Tree Pump).** For any aTAM system $S$ with $S$-seed finite and connected, define the following sets of assemblies:

- for any integer $m$, $C_m[S]$ is the set of assemblies of $S$ which encircle an $m \times m$ square;

- for any real $k$ and vector $\vec{d}$, $B_{k,\vec{d}}[S]$ is the set of assemblies of $S$ which do not cover any position $\vec{p}$ such that $\vec{p} \cdot \vec{d} > k + |S$-seed|

- for any vector $\vec{d}$, $P_{\vec{d}}[S]$ is the set of ultimately periodic assemblies of $S$ such that there is a vector $\vec{p}$ with $|\vec{p} \cdot \vec{d}| > 0$ and a non-empty sub-assembly $a \subseteq A$ such that $a + \vec{p} \subseteq a$.

Then, there is a function $F: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$ such that for aTAM system $S$ with $n$ tiles and a 1-tile seed, integer $m$ and unit vector $\vec{d}$ of $\mathbb{R}^2$,

$$A \Box [S] \cap (C_m[S] \cup B_{F(n,m),\vec{d}}[S] \cup P_{\vec{d}}[S]) \neq \emptyset.$$

<figure><img src="image_3.png" /><figcaption>■ **Figure 1** The three sets defined by Lemma 8: $C_m[S]$ is the assemblies which encircle an $m \times m$ square, $B_{F(n,m),\vec{d}}[S]$ is the set of assemblies which do not reach further than $F(n,m)$ in direction $\vec{d}$, and $P_{\vec{d}}[S]$ is the assemblies which contain a periodic path with period $\vec{p}$ such that $\vec{p} \cdot \vec{d} > 0$.</figcaption></figure>

The Tree Pump Lemma states that in order to do a meaningful amount of computation, a self-assembling system with $n$ tiles needs to encircle large squares —say, of size $m$, thus hitting $C_m[S]$. If it does not, then its productions look very much like trees drawn on $\mathbb{Z}^2$
# 6 Strict Self-Assembly of Fractals

with a $m$-cell wide brush. A branch of that tree then behaves like a finite automaton. If that automaton stops, the assembly goes no further than $F(n, m)$ in any given direction $\vec{d}$, which gives a final production in $B_{F(n,m),\vec{d}}[S]$. If not, these long branches must have an ultimately periodic behavior which gives a final production in $P_{\vec{d}}[S]$.

The full proof is given in Appendix A, as it involves a fair few ancillary definitions.

## 2.3 Strict versus Weak Assembly of shapes

**Definition 9 (Strict Assembly).** An aTAM system $\mathcal{S}$ strictly self-assembles a set $X \subset \mathbb{Z}^2$ if for all terminal production $\mathcal{P} \in \mathcal{A} \square[S]$, the domain of $\mathcal{P}$ is $X$.

**Definition 10 (Weak Assembly).** An aTAM system $\mathcal{S}$ weakly self-assembles a set $X \subset \mathbb{Z}^2$ if there is $Y \subset \mathcal{S}$ tileset such that for all terminal production $\mathcal{P} \in \mathcal{A} \square[S]$ and any position $z \in \mathbb{Z}^2$, $P(z) \in Y \Leftrightarrow z \in X$.

Weak and strict assembly are called thus because it is generally easier to weakly assemble a given shape than to strictly assemble it. Indeed, when weakly self-assembling a given shape $\mathcal{S}$, it is possible to use positions in $\mathbb{Z}^2 \setminus S$ for computation. In strict self-assembly, doing so is impossible.

**Lemma 11 (Folklore).** Any shape that can be strictly assembled can also be weakly assembled.

*Proof.* Set $Y = \mathcal{S}$ tileset in the definition of weak assembly. ▶

## 2.4 Discrete Self-Similar Fractal Shapes

Fractals are usually defined in some continuous space such as $\mathbb{R}^2$ or $\mathbb{C}^2$. In the context of self-assembly, one needs to work with discrete fractals, that is, subsets of $\mathbb{Z}^2$ which are self-similar. In this paper, discrete self-similar fractal shapes are defined as fixed points of some 2 dimensional substitution. In [20], self-similar fractal shapes are defined as the union of an infinite hierarchy of shapes. The following definition is identical, as long as the generator contains $(0,0)$. Explicitly defining a geometrical substitution will help, as that substitution can guide constructions happening on the fractal. If the generator does not contain $(0,0)$, the classical definition can be recovered by iterating the substitution associated with $G \cup (0,0)$ to reach the fix-point, then iterating once the substitution associated with $G$.

The substitution $\sigma_G$ based on a finite pattern $G$ replaces each pixel in a pattern $X$ with a copy of $G$.

**Definition 12 (Rectangular substitution).** Let $G$ be a finite subset of $\mathbb{N}^2$. Let $w = \max(\{x|(x,y) \in G\})$ and $h = \max(\{y|(x,y) \in G\})$. The substitution $\sigma_G : \mathcal{P}(\mathbb{N}^2) \to \mathcal{P}(\mathbb{N}^2)$ associated with $G$ is defined by:

$$ \forall X \subset \mathbb{N}^2, \sigma_G(X) = \{p \in \mathbb{N}^2 | \lfloor p/G \rfloor \in X \wedge p \text{ mod } G \in G\} $$

Using substitution allows manipulating the recursive definition of DSSF with richer data than one bit per position.

**Definition 13 (Colored substitution).** Let $X$ be an alphabet and $G$ a finite subset of $\mathbb{N}^2$; given for each $x \in X$ a coloring $C(x) \in X^G$, the substitution $\sigma_C$ associated with $C$ is defined for each partial coloring $Y : \mathbb{N}^2 \to X$ by:

$$ \begin{cases} \sigma_C(Y) : \mathbb{N}^2 \to X \\ \sigma_C(Y) : \vec{z} \mapsto C(Y(\lfloor z/G \rfloor))(z \text{ mod } G), \end{cases} $$

Where $\sigma_C(Y)(\vec{z})$ is defined whenever $Y(\lfloor z/G \rfloor)$ is defined and $z \text{ mod } G \in G$.
# 6 Strict Self-Assembly of Fractals

with a $m$-cell wide brush. A branch of that tree then behaves like a finite automaton. If that automaton stops, the assembly goes no further than $F(n, m)$ in any given direction $\vec{d}$, which gives a final production in $B_{F(n,m),\vec{d}}[S]$. If not, these long branches must have an ultimately periodic behavior which gives a final production in $P_{\vec{d}}[S]$.

The full proof is given in Appendix A, as it involves a fair few ancillary definitions.

## 2.3 Strict versus Weak Assembly of shapes

**Definition 9 (Strict Assembly).** An aTAM system $\mathcal{S}$ strictly self-assembles a set $X \subset \mathbb{Z}^2$ if for all terminal production $\mathcal{P} \in \mathcal{A} \square[S]$, the domain of $\mathcal{P}$ is $X$.

**Definition 10 (Weak Assembly).** An aTAM system $\mathcal{S}$ weakly self-assembles a set $X \subset \mathbb{Z}^2$ if there is $Y \subset \mathcal{S}$ tileset such that for all terminal production $\mathcal{P} \in \mathcal{A} \square[S]$ and any position $z \in \mathbb{Z}^2$, $\mathcal{P}(z) \in Y \Leftrightarrow z \in X$.

Weak and strict assembly are called thus because it is generally easier to weakly assemble a given shape than to strictly assemble it. Indeed, when weakly self-assembling a given shape $\mathcal{S}$, it is possible to use positions in $\mathbb{Z}^2 \setminus S$ for computation. In strict self-assembly, doing so is impossible.

**Lemma 11 (Folklore).** Any shape that can be strictly assembled can also be weakly assembled.

*Proof.* Set $Y = \mathcal{S}$ tileset in the definition of weak assembly. ▼

## 2.4 Discrete Self-Similar Fractal Shapes

Fractals are usually defined in some continuous space such as $\mathbb{R}^2$ or $\mathbb{C}^2$. In the context of self-assembly, one needs to work with discrete fractals, that is, subsets of $\mathbb{Z}^2$ which are self-similar. In this paper, discrete self-similar fractal shapes are defined as fixed points of some 2 dimensional substitution. In [20], self-similar fractal shapes are defined as the union of an infinite hierarchy of shapes. The following definition is identical, as long as the generator contains $(0,0)$. Explicitly defining a geometrical substitution will help, as that substitution can guide constructions happening on the fractal. If the generator does not contain $(0,0)$, the classical definition can be recovered by iterating the substitution associated with $G \cup (0,0)$ to reach the fix-point, then iterating once the substitution associated with $G$.

The substitution $\sigma_G$ based on a finite pattern $G$ replaces each pixel in a pattern $X$ with a copy of $G$.

**Definition 12 (Rectangular substitution).** Let $G$ be a finite subset of $\mathbb{N}^2$. Let $w = \max(\{x|(x,y) \in G\})$ and $h = \max(\{y|(x,y) \in G\})$. The substitution $\sigma_G : \mathcal{P}(\mathbb{N}^2) \to \mathcal{P}(\mathbb{N}^2)$ associated with $G$ is defined by:

$$ \forall X \subset \mathbb{N}^2, \sigma_G(X) = \{p \in \mathbb{N}^2 | \lfloor p/G \rfloor \in X \wedge p \text{ mod } G \in G\} $$

Using substitution allows manipulating the recursive definition of DSSF with richer data than one bit per position.

**Definition 13 (Colored substitution).** Let $X$ be an alphabet and $G$ a finite subset of $\mathbb{N}^2$; given for each $x \in X$ a coloring $C(x) \in X^G$, the substitution $\sigma_C$ associated with $C$ is defined for each partial coloring $Y : \mathbb{N}^2 \to X$ by:

$$ \begin{cases} \sigma_C(Y) : \mathbb{N}^2 \dashrightarrow X \\ \sigma_C(Y) : \vec{z} \mapsto C(Y(\lfloor z/G \rfloor))(z \text{ mod } G), \end{cases} $$

Where $\sigma_C(Y)(\vec{z})$ is defined whenever $Y(\lfloor z/G \rfloor)$ is defined and $z \text{ mod } G \in G$.
<figure><img src="image_3.png" /><figcaption>■ **Figure 2** A colored substitution on a 3-colored alphabet $\Sigma = \{\bullet, \circled, \circled\}$ is defined from a shape $G = \square$ and a coloring of $G$ for each color of $\Sigma$. It can then be applied to any colored shape (right).</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>■ **Figure 3** The substitution $\kappa$ of the Sierpinski's Cacarpet.</figcaption></figure>

► **Definition 14** (Self-Similar Fractal Shape). Let $G$ be a finite subset of $\mathbb{N}^2$ with $(0,0) \in G$. The discrete self-similar fractal shape with generator $G$ is the following subset of $\mathbb{N}^2$:

$$G^{\infty} = \bigcup_{i \in \mathbb{N}} \sigma_{G}^{i}(\{(0,0)\}).$$

The i-th step of the fractal is $G^i = \sigma_G^i(\{(0,0)\})$.

One self-similar fractal shape will be of particular interest to us in this paper, which we name *Sierpinski's Cacarpet*. It is the self-similar fractal shape $K_{\infty}$ with generator $K = \{0, \dots, 5\}^2 \setminus \{2, 3\}^2$, represented on figure 3. We note $\kappa = \sigma_K$ the associated substitution.

## 2.5 The Sierpinski Cacarpet can be Strictly Self-Assembled

Until this paper, in order to assemble a DSSF $S$ in the aTAM, one would typically embed counters into $S$, or rather some small superset of it [20, 16, 13]. Strict self-assembly of a DSSF can be obtained in another way:

- first, choose a *suitable* DSSF to assemble, namely the Sierpinski Cacarpet $K^{\infty}$

- observe that $K^{\infty}$ is the fixed-point of a discrete substitution $\kappa$,

- in consequence, define a hierarchy of systems: a *self-describing circuit* $C_{\square}$, which entails an *Locally Deterministic Oriented Pattern* $P_{\square}$, whose tiles make a temperature 2 Tile Assembly System $S_{\square}$ in the abstract Tile Assembly Model which uniquely assembles $P_{\square}$.

In fine, the correctness of $S_{\square}$ follows thus:

- $C_{\square}$ is defined as a fixed-point of $\kappa$, and thus has $K^{\infty}$ as its support,
<figure><img src="image_4.png" /><figcaption>■ **Figure 2** A colored substitution on a 3-colored alphabet $\Sigma = \{\bullet, \circled, \circled\}$ is defined from a shape $G = \square$ and a coloring of $G$ for each color of $\Sigma$. It can then be applied to any colored shape (right).</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>■ **Figure 3** The substitution $\kappa$ of the Sierpinski's Cacarpet.</figcaption></figure>

► **Definition 14** (Self-Similar Fractal Shape). Let $G$ be a finite subset of $\mathbb{N}^2$ with $(0,0) \in G$. The discrete self-similar fractal shape with generator $G$ is the following subset of $\mathbb{N}^2$:

$$G^{\infty} = \bigcup_{i \in \mathbb{N}} \sigma_{G}^{i}(\{(0,0)\}).$$

The i-th step of the fractal is $G^i = \sigma_G^i(\{(0,0)\})$.

One self-similar fractal shape will be of particular interest to us in this paper, which we name *Sierpinski's Cacarpet*. It is the self-similar fractal shape $K_{\infty}$ with generator $K = \{0, \dots, 5\}^2 \setminus \{2, 3\}^2$, represented on figure 3. We note $\kappa = \sigma_K$ the associated substitution.

## 2.5 The Sierpinski Cacarpet can be Strictly Self-Assembled

Until this paper, in order to assemble a DSSF $S$ in the aTAM, one would typically embed counters into $S$, or rather some small superset of it [20, 16, 13]. Strict self-assembly of a DSSF can be obtained in another way:

- first, choose a *suitable* DSSF to assemble, namely the Sierpinski Cacarpet $K^{\infty}$

- observe that $K^{\infty}$ is the fixed-point of a discrete substitution $\kappa$,

- in consequence, define a hierarchy of systems: a *self-describing circuit* $C_{\square}$, which entails an *Locally Deterministic Oriented Pattern* $P_{\square}$, whose tiles make a temperature 2 Tile Assembly System $S_{\square}$ in the abstract Tile Assembly Model which uniquely assembles $P_{\square}$.

In fine, the correctness of $S_{\square}$ follows thus:

- $C_{\square}$ is defined as a fixed-point of $\kappa$, and thus has $K^{\infty}$ as its support,
- the structure of $C_{\square}$ allows it to be *evaluated*, which yields a pattern $P_{\square}$, with the same support,

- moreover, $C_{\square}$ is *self-describing* (Definition 21 and Theorem 29), which gives $P_{\square}$ its *local determinism* (Definition 23 and Lemma 24)

- the set of tiles in $P_{\kappa}$ defines an aTAM System $S_{\square}$; since $P_{\square}$ is locally deterministic, the unique final production of $S_{\square}$ is $P_{\square}$ (Lemma 27).

**Theorem 15.** There is an aTAM system at temperature $\kappa$ which self-assembles the DSSF pattern $K^{\infty}$.

The proof of Theorem 15 spans sections 3 and 4. The constructivist reader will find the detailed construction of $C_{\kappa}$ in section 4, this should enlighten them about most of the ideas of the construction. The formalist will find the tower of models and the links between them in section 3.

# 3 Abstract models: Self-Describing Embedded Circuits and Locally Deterministic Patterns

## 3.1 Embedded circuits

A circuit is made of gates. Each of these gates has a *function*, computing the outputs of the gates from the inputs. The gate is embedded on a unit square according to its *wiring*, which states where its inputs come from and where its outputs go to. The wiring and the function must be compatible: the wiring must have as many inputs as the function.

**Definition 16 (Wire).** A wire is a pair of a list of distinct directions $\vec{D} \in \{N, E, S, W\}^*$ and a distinguished element $d \in D$. It is noted as a word on the alphabet $\{n, e, s, w\}$ containing the elements of $D$, with $d$ capitalized. For instance, the wire $((N, E), E)$ is noted $nE$, while $((N, E), N)$ is noted $nE$.

Given a wire $w = (\vec{D}, d)$, its opposite $-w$ is $((-\vec{D}_i), -d)$, i.e. $-N_e = S_w$. The set of wires is noted *Wires*.

**Definition 17 (Wiring).** Given two integers $i, o$ such that $i + o \le 4$, a $(i, o)$-wiring $w$ (i.e. a wiring with in-degree $i$ and out-degree $o$) is given by

- a partition of $\{N, E, S, W\}$ into three sets, $w$. Inputs, $w$. Outputs and $w$. Inert, where $w$. Inputs is ordered

- a map $w$. output-num : $w$. Outputs $\rightarrow \{0, \dots, o-1\}$;

- a map $w$. outwires : $w$. Outputs $\rightarrow$ Wires such that $-d$ is the distinguished element of $w$. outwires($d$).

The set of all wirings is noted $W$.

**Definition 18 (Input / Output / Inert Sides, Degree).** Given a wiring $w \in W$, the elements of $w$. Inputs are the input sides of $w$, the elements of $w$. Outputs are its output sides, and the elements of $w$. Inert are its inert sides. The in-degree of $w$ is the number of its input sides, its out-degree of $w$ is its number of output sides.

Additionally, each output side also determines the *input* sides on the following gate and their ordering. That is, a wiring $w$ with $nE \in w$. outwires can only have a wiring $w'$ with $w'$. Inputs = (S, W) to its right.

The graphical representation of a wiring is given on Figure 4. Each direction in $w$. Inputs has an incoming arrow, and each direction in $w$. Outputs has an outgoing arrow. If $w$. Inputs
- the structure of $C_{\square}$ allows it to be *evaluated*, which yields a pattern $P_{\square}$, with the same support,

- moreover, $C_{\square}$ is *self-describing* (Definition 21 and Theorem 29), which gives $P_{\square}$ its *local determinism* (Definition 23 and Lemma 24)

- the set of tiles in $P_{\kappa}$ defines an aTAM System $S_{\square}$; since $P_{\square}$ is locally deterministic, the unique final production of $S_{\square}$ is $P_{\square}$ (Lemma 27).

**Theorem 15.** *There is an aTAM system at temperature 2 which self-assembles the DSSF pattern $K^{\infty}$.*

The proof of Theorem 15 spans sections 3 and 4. The constructivist reader will find the detailed construction of $C_{\kappa}$ in section 4, this should enlighten them about most of the ideas of the construction. The formalist will find the tower of models and the links between them in section 3.

# 3 Abstract models: Self-Describing Embedded Circuits and Locally Deterministic Patterns

## 3.1 Embedded circuits

A circuit is made of gates. Each of these gates has a *function*, computing the outputs of the gates from the inputs. The gate is embedded on a unit square according to its *wiring*, which states where its inputs come from and where its outputs go to. The wiring and the function must be compatible: the wiring must have as many inputs as the function.

**Definition 16 (Wire).** A wire is a pair of a list of distinct directions $\vec{D} \in \{N, E, S, W\}^*$ and a distinguished element $d \in D$. It is noted as a word on the alphabet $\{n, e, s, w\}$ containing the elements of $D$, with $d$ capitalized. For instance, the wire $((N, E), E)$ is noted $nE$, while $((N, E), N)$ is noted $nE$.

Given a wire $w = (\vec{D}, d)$, its opposite $-w$ is $((-\vec{D}_i), -d)$, i.e. $-N_e = S_w$. The set of wires is noted *Wires*.

**Definition 17 (Wiring).** Given two integers $i, o$ such that $i + o \le 4$, a $(i, o)$-wiring $w$ (i.e. a wiring with in-degree $i$ and out-degree $o$) is given by

- a partition of $\{N, E, S, W\}$ into three sets, $w$. Inputs, $w$. Outputs and $w$. Inert, where $w$. Inputs is ordered

- a map $w$. output-num : $w$. Outputs $\rightarrow \{0, \dots, o-1\}$;

- a map $w$. outwires : $w$. Outputs $\rightarrow$ Wires such that $-d$ is the distinguished element of $w$. outwires($d$).

The set of all wirings is noted $W$.

**Definition 18 (Input / Output / Inert Sides, Degree).** Given a wiring $w \in W$, the elements of $w$. Inputs are the input sides of $w$, the elements of $w$. Outputs are its output sides, and the elements of $w$. Inert are its inert sides. The in-degree of $w$ is the number of its input sides, its out-degree of $w$ is its number of output sides.

Additionally, each output side also determines the *input* sides on the following gate and their ordering. That is, a wiring $w$ with $nE \in w$. outwires can only have a wiring $w'$ with $w' \cdot$ Inputs = $(S, W)$ to its right.

The graphical representation of a wiring is given on Figure 4. Each direction in $w$. Inputs has an incoming arrow, and each direction in $w$. Outputs has an outgoing arrow. If $w$. Inputs
<figure><img src="image_5.png" /><figcaption>■ **Figure 4** The graphical representation of three wirings: $w_1$ = {Inputs = (W), Outputs = {N, S, E}, output-num = {N → 1, E → 0, S → 1}, outwires = {Se, W, wN}}, $w_2$ = {Inputs = (W, S), Outputs = {N}, output-num = {N → 0}, outwires = {Sn}} and $w_3$ = {Inputs = (W, E), Outputs = {S}, output-num = {S → 0}, outwires = {wN}}. Neighboring input wires bend to come together into the wiring. Double arrows indicate a pair of opposite input arrows. The output wire in direction *d* bends to mirror $w \cdot$ outwires(*d*).</figcaption></figure>

has only one element, the corresponding arrow is straight and simple. Likewise for the
outgoing arrow when $w \cdot$ outwires($d$) is a singleton. When $w \cdot$ outwires($d$) is made of two
adjacent directions, the corresponding arrows bend to come near each other; likewise, modulo
rotation, when $w \cdot$ outwires($N$) $\in$ {$Ne, eN$}, the corresponding arrow bends left, and right if
it is $Nw$ or $wN$. For pairs of opposite directions, an arrow with a double tip is used. Triple
and quadruple inputs are not used in this paper. Inputs are numbered according to the order
of $w \cdot$ Inputs and output wires are numbered according to $w \cdot$ output-num.

**Definition 19 (Gate).** *Given an alphabet Σ two integers i, o, a gate g is a pair { func : f, wiring : w}, with f a function f : Σ^i → Σ^o and w an (i, o)-wiring.*

*The set of gates on alphabet Σ is noted Gates(Σ).*

These gates may be placed onto a subset of the grid $\mathbb{Z}^2$ to make *circuits*. An example of a circuit, a multiplier built from a handful of adders and auxiliary gates is given on Figure 5.

**Definition 20 (Circuit).** Let $\Sigma$ be an alphabet. Let $D$ be an oriented subgraph of $\mathbb{Z}^2$, $\vec{I}$ be a sequence of arcs from $\mathbb{Z}^2 \setminus D$ to $D$ and $\vec{O}$ a sequence of arcs from $D$ to $\mathbb{Z}^2 \setminus D$.

A circuit $C$ with dependency graph $D$, input bus $\vec{I}$ and output bus $\vec{O}$ is a map $D \to \text{Gates}(\Sigma)$ such that:

- for any arc *E* in direction *d* ∈ {*N*, *E*, *S*, *W*} between two positions *a*, *b* ∈ *D*, let *w*<sub>*a*</sub> = *C*(*a*)·wiring and *w*<sub>*b*</sub> = *C*(*b*)·wiring; then *d* ∈ *w*<sub>*a*</sub>·Outputs, −*d* ∈ *w*<sub>*b*</sub>·Inputs, and *w*<sub>*a*</sub>·Outputs(*d*) = (−*d*, *w*<sub>*b*</sub>·Inputs),

- for any adjacent positions *a*, *b* in $\mathbb{Z}^2$ with no arc between *a* and *b* in *D*, *d* ∈ $C(a)$·wiring·Inert and −*d* ∈ $C(b)$·wiring·Inert

- and for any arc *e* of $\mathbb{Z}^2$ in direction *d* ∈ {*N*, *E*, *S*, *W*} between two positions *a* ∈ *D* and *b* ∈ $\mathbb{Z}^2 \setminus D$, either:

- *d* ∈ *C(a)*·wiring·Inert *and* *e* is neither an element of *I* nor of *O*,

- *d* ∈ *C(a)*·wiring·Outputs *and* *e* is an element of *O*,

- $-d \in C(a) \cdot \text{wiring} \cdot \text{Inputs}$ and $-e$ is an element of $\vec{I}$.

The support of *C* is the vertex-set of *D*.

Let *C* be a circuit, and *A* the arc-set of its dependency graph *D*. A function *v* : *A* ↦ Σ
conforms to *C* at a position *z̃* in the support of *C*, if for any *d* ∈ *C(z̃)*·wiring·Outputs,
*v(o) = (C(v)·func(v(i₀), ..., v(i_m)))k* with *i₀, ..., i_m* the input arcs of *C(z̃)*, *o* its output arc
in direction *d* and *k* = *C(z̃)·wiring·output-num(d)*.

A circuit is *well-founded* when its dependency graph has no cycle or infinite backwards
paths. For a well-founded circuit, given a vector of inputs $\vec{i}$ indexed by $\vec{I}$, there is a *unique*
<figure><img src="image_6.png" /><figcaption>■ **Figure 4** The graphical representation of three wirings: $w_1$ = {Inputs = (W), Outputs = {N, S, E}, output-num = {N → 1, E → 0, S → 1}, outwires = {Se, W, wN}}, $w_2$ = {Inputs = (W, S), Outputs = {N}, output-num = {N → 0}, outwires = {Sn}} and $w_3$ = {Inputs = (W, E), Outputs = {S}, output-num = {S → 0}, outwires = {wN}}. Neighboring input wires bend to come together into the wiring. Double arrows indicate a pair of opposite input arrows. The output wire in direction *d* bends to mirror *w*·outwires(*d*).</figcaption></figure>

has only one element, the corresponding arrow is straight and simple. Likewise for the
outgoing arrow when w·outwires(d) is a singleton. When w·outwires(d) is made of two
adjacent directions, the corresponding arrows bend to come near each other; likewise, modulo
rotation, when w·outwires(N) ∈ {Ne, eN}, the corresponding arrow bends left, and right if
it is Nw or wN. For pairs of opposite directions, an arrow with a double tip is used. Triple
and quadruple inputs are not used in this paper. Inputs are numbered according to the order
of w·Inputs and output wires are numbered according to w·output-num.

**Definition 19 (Gate).** *Given an alphabet Σ two integers i, o, a gate g is a pair { func : f, wiring : w}, with f a function f : Σ^i → Σ^o and w an (i, o)-wiring.*

*The set of gates on alphabet Σ is noted Gates(Σ).*

These gates may be placed onto a subset of the grid $\mathbb{Z}^2$ to make *circuits*. An example of a circuit, a multiplier built from a handful of adders and auxiliary gates is given on Figure 5.

**Definition 20 (Circuit).** Let $\Sigma$ be an alphabet. Let $D$ be an oriented subgraph of $\mathbb{Z}^2$, $\vec{I}$ be a sequence of arcs from $\mathbb{Z}^2 \setminus D$ to $D$ and $\vec{O}$ a sequence of arcs from $D$ to $\mathbb{Z}^2 \setminus D$.

A circuit $C$ with dependency graph $D$, input bus $\vec{I}$ and output bus $\vec{O}$ is a map $D \to \text{Gates}(\Sigma)$ such that:

- for any arc *E* in direction *d* ∈ {N, *E*, *S*, *W*} between two positions *a*, *b* ∈ *D*, let *w*<sub>*a*</sub> = *C*(*a*)·wiring and *w*<sub>*b*</sub> = *C*(*b*)·wiring; then *d* ∈ *w*<sub>*a*</sub>·Outputs, −*d* ∈ *w*<sub>*b*</sub>·Inputs, and *w*<sub>*a*</sub>·Outputs(*d*) = (−*d*, *w*<sub>*b*</sub>·Inputs),

- for any adjacent positions *a*, *b* in $\mathbb{Z}^2$ with no arc between *a* and *b* in *D*, *d* ∈ $C(a)$·wiring·Inert and −*d* ∈ $C(b)$·wiring·Inert

- and for any arc *e* of $\mathbb{Z}^2$ in direction *d* ∈ {N, *E*, *S*, *W*} between two positions *a* ∈ *D* and *b* ∈ $\mathbb{Z}^2 \setminus D$, either:

- *d* ∈ *C*a*·wiring·Inert and *e* is neither an element of *Ī* nor of *O*,

- *d* ∈ C(a)·wiring·Outputs and *e* is an element of O,

- $-d \in C(a) \cdot \text{wiring} \cdot \text{Inputs}$ and $-e$ is an element of $\vec{I}$.

The support of *C* is the vertex-set of *D*.

Let *C* be a circuit, and *A* the arc-set of its dependency graph *D*. A function *v* : *A* ↦ Σ
conforms to *C* at a position *z̃* in the support of *C*, if for any *d* ∈ *C(z̃)*·wiring·Outputs,
*v(o) = (C(v)·func(v(i₀), ..., v(i_m)))k* with *i₀, ..., i_m* the input arcs of *C(z̃)*, *o* its output arc
in direction *d* and *k* = *C(z̃)*·wiring·output-num(*d*).

A circuit is *well-founded* when its dependency graph has no cycle or infinite backwards
paths. For a well-founded circuit, given a vector of inputs $\vec{i}$ indexed by $\vec{I}$, there is a *unique*
<figure><img src="image_6.png" /></figure>

$$ 
\left\{ 
\begin{array}{l} 
i_1 : \Sigma \to \Sigma \\ 
i_1(x) = x \\ 
i_2 : \Sigma^2 \to \Sigma^2 \\ 
i_2(x, y) = (x, y) 
\end{array} 
\right. 
\quad 
\left\{ 
\begin{array}{l} 
m : \Sigma^2 \to \Sigma^2 \\ 
m(x, y) = (xy \bmod 10, \lfloor xy/10 \rfloor) \\ 
a : \Sigma^2 \to \Sigma^2 \\ 
a(x, y) = ((x + y) \bmod 10, \lfloor (x + y)/10 \rfloor) 
\end{array} 
\right. 
$$

<caption>■ **Figure 5** A multiplier circuit $M_2^1$ and the definition of the functions of its gates. The alphabet is the set of digits $\mathbb{Z}/10\mathbb{Z}$. The values in the grey squares are an example of evaluation: $32 \times 7 = 224$</caption>

function $\tilde{C}(\vec{i}, -)$ which conforms to $C$ and such that the values on $\vec{I}$ are $\vec{i}$. The circuit function $\tilde{C} : \Sigma^{\vec{I}} \to \Sigma^{\vec{O}}$ is defined by $\tilde{C}(\vec{i}) = (\tilde{C}(\vec{i}, O_k))_k$.

A circuit is *finitely rooted* when its input bus is finite and its number of gates with in-degree 0 is finite. It is *evaluable* if it is well-founded and finitely rooted.

The circuit $M_2^1$ on figure 5 is a multiplier. Take two natural integers $a < 10, b < 100$, pose $b = b_0 + 10b_1$ with $\forall i, 0 \le b_i < 10$. Let $\vec{i}_{a,b} = (a_0, b_0, b_1)$. Then $\tilde{C}(\vec{i}_{a,b}) = \vec{o}$, with $ab = \sum o_i 10^i$. Figure 5 gives an example of the evaluation of the circuit on inputs 32 and 7; the values of $\tilde{C}(\vec{i}, -)$ on each arc are given on the figure.

When the alphabet $\Sigma$ is structured in two layers, i.e. $\Sigma = A \times B$, the function $f$ of a gate $g$ may act independently on layer $A$ and layer $B$, i.e. $f = f_A \otimes f_B$. Then, taking $g_A = \{ \text{wiring} : w, \text{func} : f_A \} \in \text{Gates}(A)$ and $g_B = \{ \text{wiring} : w, \text{func} : f_B \} \in \text{Gates}(B)$, $g$ can be written as $g_A \otimes g_B$. In other words, the tensor product $\otimes$ applies to pairs of gates with the same wiring.

## 3.2 Self-description

The process of self-assembly in the aTAM and the evaluation of an evaluable embedded circuit are somewhat alike, in that information propagates from an initial region outwards. In both processes, there is no global synchronisation, but each step can take place as soon as its inputs are ready. In the aTAM, the initial region is the seed, while in a circuit, it is the input bus together with the gates of in-degree 0.

There are three differences between these processes. First, the input bus of a circuit does not have an analog in the aTAM. Hence, aTAM systems are akin to *closed* circuits. Secondly, there can be competition between attachments in the aTAM, as well as mismatches, both of which are ruled out in circuits. This entails that an aTAM derived from a circuit by the
<figure><img src="image_7.png" /></figure>

$$
\left\{
\begin{array}{l}
i_1 : \Sigma \to \Sigma \\
i_1(x) = x \\
i_2 : \Sigma^2 \to \Sigma^2 \\
i_2(x, y) = (x, y)
\end{array}
\right.
\qquad
\left\{
\begin{array}{l}
m : \Sigma^2 \to \Sigma^2 \\
m(x, y) = (xy \bmod 10, \lfloor xy/10 \rfloor) \\
a : \Sigma^2 \to \Sigma^2 \\
a(x, y) = ((x + y) \bmod 10, \lfloor (x + y)/10 \rfloor)
\end{array}
\right.
$$

<caption>■ **Figure 5** A multiplier circuit $M_2^1$ and the definition of the functions of its gates. The alphabet is the set of digits $\mathbb{Z}/10\mathbb{Z}$. The values in the grey squares are an example of evaluation: $32 \times 7 = 224$</caption>

function $\tilde{C}(\vec{i}, -)$ which conforms to $C$ and such that the values on $\vec{I}$ are $\vec{i}$. The circuit function $\bar{C} : \Sigma^{\vec{I}} \to \Sigma^{\vec{O}}$ is defined by $\bar{C}(\vec{i}) = (\tilde{C}(\vec{i}, O_k))_k$.

A circuit is *finitely rooted* when its input bus is finite and its number of gates with in-degree 0 is finite. It is *evaluable* if it is well-founded and finitely rooted.

The circuit $M_2^1$ on figure 5 is a multiplier. Take two natural integers $a < 10, b < 100$, pose $b = b_0 + 10b_1$ with $\forall i, 0 \le b_i < 10$. Let $\vec{i}_{a,b} = (a_0, b_0, b_1)$. Then $\tilde{C}(\vec{i}_{a,b}) = \vec{o}$, with $ab = \sum o_i 10^i$. Figure 5 gives an example of the evaluation of the circuit on inputs 32 and 7; the values of $\tilde{C}(\vec{i}, -)$ on each arc are given on the figure.

When the alphabet $\Sigma$ is structured in two layers, i.e. $\Sigma = A \times B$, the function $f$ of a gate $g$ may act independently on layer $A$ and layer $B$, i.e. $f = f_A \otimes f_B$. Then, taking $g_A = \{ \text{wiring : } w, \text{func : } f_A \} \in \text{Gates}(A)$ and $g_B = \{ \text{wiring : } w, \text{func : } f_B \} \in \text{Gates}(B)$, $g$ can be written as $g_A \otimes g_B$. In other words, the tensor product $\otimes$ applies to pairs of gates with the same wiring.

## 3.2 Self-description

The process of self-assembly in the aTAM and the evaluation of an evaluable embedded circuit are somewhat alike, in that information propagates from an initial region outwards. In both processes, there is no global synchronisation, but each step can take place as soon as its inputs are ready. In the aTAM, the initial region is the seed, while in a circuit, it is the input bus together with the gates of in-degree 0.

There are three differences between these processes. First, the input bus of a circuit does not have an analog in the aTAM. Hence, aTAM systems are akin to *closed* circuits. Secondly, there can be competition between attachments in the aTAM, as well as mismatches, both of which are ruled out in circuits. This entails that an aTAM derived from a circuit by the
compilation process detailed below will not exhibit mismatches or concurrent attachments. The last and most important difference is that in a circuit, the outputs of each gate depends not only on its input, but also on the function of the gate. For an aTAM system to simulate a circuit, this information needs to be derived from the inputs of the gate. Self-description captures the possibility to do so.

**Definition 21 (Self-describing circuit).** A normal circuit C on alphabet Σ is self-describing on input vector $\vec{i}$ if there is a decoding function $\text{dec-gate}: (\Sigma \times \{N, E, S, W\})^{<4} \to \text{Gates}(\Sigma)$ such that for any position p with incoming arcs $(e_0, \dots, e_{k-1}) = p + (C(p) \cdot \text{wiring} \cdot \text{Inputs}):$

$$ \text{dec-gate}((\tilde{C}(\vec{i}, e_0), d_0), \dots, (\tilde{C}(\vec{i}, e_{k-1}), d_{k-1})) = C(p), $$

where $d_j$ is the direction of $e_j$.

A closed self-describing circuit really is a circuit with only one function of each in-degree. Having one function per in-degree is a harmless technicality: in a circuit, successive gates have compatible wirings, so the in-degree of each gate is known from the wiring of any of its predecessor gates, whether or not the circuit is self-describing.

**Lemma 22.** Let C be a closed self-describing circuit. There is a closed circuit $C_1$ with only one function of each in-degree such that $\tilde{C} = C_1$.

**Proof.** $C_1$ has the same wirings as C, and for each i, all of its gates of in-degree i have as function $f_i: x_0 \dots x_{i-1} \mapsto (\delta_C(x_0, \dots, x_{i-1}) \cdot \text{func})(x_0, \dots, x_{i-1})$, where $\delta_C$ is the decoding function of C.

## 3.3 Locally deterministic patterns

If C is a self-describing closed circuit, then from $\tilde{C}$, one gets a coloring of the arcs of its dependency graph with the property of local determinism.

**Definition 23 (Locally deterministic arc coloring).** Let P be a coloring of the arcs of some acyclic oriented subgraph G of $\mathbb{Z}^2$. For each vertex v ∈ G with in-degree δ, note $\vec{i}_v = ((d_0, P(e_0)), \dots, (d_{\delta-1}, P(e_{\delta-1})))$ for the input vector of v, where $e_i$ is the i-th incoming edge of v and $d_i$ its direction

P is locally deterministic if there are two prediction functions pred-inputs: $\{N, E, S, W\} \times \Sigma \to P(\{N, E, S, W\})$ and pred-symbols: $\{(N, E, S, W) \times \Sigma\}^{<4} \times \{N, E, S, W\} \to \Sigma$ such that for each arc e from vertex a to vertex b in direction $d \in \{N, E, S, W\}$,

■ $P(e) = \text{pred-symbols}(\vec{i}_a, d)$

■ pred-inputs(d, P(e)) is the set of directions of the incoming arcs of b,

**Lemma 24.** Let C be a closed self-describing circuit on alphabet Σ, with dependency graph $D_C = (V, A)$. Let $C'$ be the self-describing circuit on alphabet Σ × W where each gate outputs its wiring in addition to its normal output. Then the function $\tilde{C}'$ is a locally deterministic coloring of $D_C$.

**Proof.** A candidate function for pred-inputs takes as input the direction d of an arc $e: a \to b$, and the value of $\tilde{C}'(e)$, that is, an element of Σ corresponding to $\tilde{C}(e)$ as well as the wiring w of the gate at a. Thus, the function $(d, x, w) \mapsto w$ outwires(d) must, by the constraints on neighboring gates in a circuit, output the set of directions of the incoming arcs at b.

Likewise, a candidate function for pred-symbols takes as input the direction of the arc $e: a \to b$, and a vector $\vec{m} \otimes \vec{d}$ of the inputs coming into a with their directions. Reorder $\vec{m} \otimes \vec{d}$ so that $\vec{d}$ is in the order of the inputs of C(a). Let $\{\text{wiring}: w, \text{func}: f\} = \text{dec-gate}(\vec{m} \otimes \vec{d})$. Then taking pred-symbols(e) = (f(\vec{m}), w) works.
compilation process detailed below will not exhibit mismatches or concurrent attachments. The last and most important difference is that in a circuit, the outputs of each gate depends not only on its input, but also on the function of the gate. For an aTAM system to simulate a circuit, this information needs to be derived from the inputs of the gate. Self-description captures the possibility to do so.

**Definition 21 (Self-describing circuit).** A normal circuit C on alphabet Σ is self-describing on input vector $\vec{i}$ if there is a decoding function $\text{dec-gate}: (\Sigma \times \{N, E, S, W\})^{<4} \to \text{Gates}(\Sigma)$ such that for any position p with incoming arcs $(e_0, \dots, e_{k-1}) = p + (C(p) \cdot \text{wiring} \cdot \text{Inputs})$:

$$ \text{dec-gate}((\tilde{C}(\vec{i}, e_0), d_0), \dots, (\tilde{C}(\vec{i}, e_{k-1}), d_{k-1})) = C(p), $$

where $d_j$ is the direction of $e_j$.

A closed self-describing circuit really is a circuit with only one function of each in-degree. Having one function per in-degree is a harmless technicality: in a circuit, successive gates have compatible wirings, so the in-degree of each gate is known from the wiring of any of its predecessor gates, whether or not the circuit is self-describing.

**Lemma 22.** Let C be a closed self-describing circuit. There is a closed circuit $C_1$ with only one function of each in-degree such that $\tilde{C} = C_1$.

**Proof.** $C_1$ has the same wirings as C, and for each i, all of its gates of in-degree i have as function $f_i: x_0 \dots x_{i-1} \mapsto (\delta_C(x_0, \dots, x_{i-1}) \cdot \text{func})(x_0, \dots, x_{i-1})$, where $\delta_C$ is the decoding function of C.

## 3.3 Locally deterministic patterns

If C is a self-describing closed circuit, then from $\tilde{C}$, one gets a coloring of the arcs of its dependency graph with the property of local determinism.

**Definition 23 (Locally deterministic arc coloring).** Let P be a coloring of the arcs of some acyclic oriented subgraph G of $\mathbb{Z}^2$. For each vertex v ∈ G with in-degree δ, note $\vec{i}_v = ((d_0, P(e_0)), \dots, (d_{\delta-1}, P(e_{\delta-1})))$ for the input vector of v, where $e_i$ is the i-th incoming edge of v and $d_i$ its direction

P is locally deterministic if there are two prediction functions pred-inputs: $\{N, E, S, W\} \times \Sigma \to P(\{N, E, S, W\})$ and pred-symbols: $\{(N, E, S, W) \times \Sigma\}^{<4} \times \{N, E, S, W\} \to \Sigma$ such that for each arc e from vertex a to vertex b in direction $d \in \{N, E, S, W\}$,

■ $P(e) = \text{pred-symbols}(\vec{i}_a, d)$

■ pred-inputs(d, P(e)) is the set of directions of the incoming arcs of b,

**Lemma 24.** Let C be a closed self-describing circuit on alphabet Σ, with dependency graph $D_C = (V, A)$. Let $C'$ be the self-describing circuit on alphabet Σ × W where each gate outputs its wiring in addition to its normal output. Then the function $\tilde{C}'$ is a locally deterministic coloring of $D_C$.

**Proof.** A candidate function for pred-inputs takes as input the direction d of an arc $e: a \to b$, and the value of $\tilde{C}'(e)$, that is, an element of Σ corresponding to $\tilde{C}(e)$ as well as the wiring w of the gate at a. Thus, the function $(d, x, w) \mapsto w$ outwires(d) must, by the constraints on neighboring gates in a circuit, output the set of directions of the incoming arcs at b.

Likewise, a candidate function for pred-symbols takes as input the direction of the arc $e: a \to b$, and a vector $\vec{m} \otimes \vec{d}$ of the inputs coming into a with their directions. Reorder $\vec{m} \otimes \vec{d}$ so that $\vec{d}$ is in the order of the inputs of C(a). Let $\{\text{wiring}: w, \text{func}: f\} = \text{dec-gate}(\vec{m} \otimes \vec{d})$. Then taking pred-symbols(e) = (f(\vec{m}), w) works.
<figure><img src="image_7.png" /><figcaption>■ **Figure 6** Three arc colorings on the alphabet $\Sigma = \{A, 0, 1\}$. All arcs go either to the right or up. The coloring $C_1$, in the upper left is locally deterministic. In the upper-right, $C_2$ is not because the two circled arcs have value 1 and direction $E$, but the vertices they point into have different incoming directions $(\{E\}$ versus $\{N, E\}$). At the bottom, $C_3$ is not locally deterministic, because the two triangle vertices get the same incoming values, but have different outputs: $(0, 0)$ versus $(1, 1)$.</figcaption></figure>

**From locally deterministic patterns to aTAM systems**

**Definition 25** (vertex type, atlas). Let $P$ be a coloring of the arcs of some acyclic oriented subgraph $G$ of $Z^2$. For a vertex $v$ of $G$, its vertex type is the partial function $\bar{v} : d \in \{N, E, S, W\} \to (o, x)$, where $o = -d$ if the edge $e$ in direction $d$ from $v$ is an incoming edge, $o = d$ if it is an outgoing edge, and $x \in \Sigma$ is $P(e)$. If $v$ has no edge in direction $d$, then $\bar{v}(d)$ is undefined.

The atlas of $P$ is the set of its vertex types.

A locally deterministic coloring can be reconstructed from its atlas and the positions of its in-degree 0 vertices.

**Lemma 26.** Let $P_1, P_2$ be locally deterministic colorings of the arcs of some oriented subgraphs of $Z^2$, $G_1$ and $G_2$ respectively. If

(1) $G_1$ and $G_2$ are acyclic and have no infinite backwards paths,

(2) $P_1$ and $P_2$ have the same atlas,

(3) $G_1$ and $G_2$ have the same vertices with in-degree 0, then $G_1 = G_2$ and $P_1 = P_2$.

**Proof.** By induction on the longest path to each position in $G_1$. ▼

<figure><img src="image_8.png" /></figure>

Finally, a locally deterministic pattern with a unique in-degree 0 vertex can be self-assembled in the aTAM.

**Lemma 27.** Let $\Sigma$ be some finite alphabet, and let $P$ be a locally deterministic coloring of the arcs of some acyclic graph $G$ with no infinite backwards path. Assume the maximal in-degree of a vertex in $G$ is $\delta$ and that $G$ has only one vertex with in-degree 0.

Then there is an aTAM system $S_P$ with temperature $\delta$ with $P$ as its only final production.

**Proof.** Let $A_P$ be the atlas of $P$, pred-inputs and pred-symbols the prediction functions of $P$. By convention, suppose pred-inputs returns an input vectors which is ordered clockwise, starting from direction $N$.

First define the glues of $S_P$ and their strength function $st$. Each glue is a pair $(s, d) \in \Sigma \times \{N, E, S, W\}$. For any symbol $s \in \Sigma$ and direction $d \in \{N, E, S, W\}$, let $\bar{s} = \text{pred-inputs}(s, d)$.
<figure><img src="image_8.png" /><figcaption>■ **Figure 6** Three arc colorings on the alphabet $\Sigma = \{A, 0, 1\}$. All arcs go either to the right or up. The coloring $C_1$, in the upper left is locally deterministic. In the upper-right, $C_2$ is not because the two circled arcs have value 1 and direction $E$, but the vertices they point into have different incoming directions $(\{E\}$ versus $\{N, E\}$). At the bottom, $C_3$ is not locally deterministic, because the two triangle vertices get the same incoming values, but have different outputs: $(0, 0)$ versus $(1, 1)$.</figcaption></figure>

**From locally deterministic patterns to aTAM systems**

**Definition 25 (vertex type, atlas).** Let $P$ be a coloring of the arcs of some acyclic oriented subgraph $G$ of $Z^2$. For a vertex $v$ of $G$, its vertex type is the partial function $\bar{v} : d \in \{N, E, S, W\} \to (o, x)$, where $o = -d$ if the edge $e$ in direction $d$ from $v$ is an incoming edge, $o = d$ if it is an outgoing edge, and $x \in \Sigma$ is $P(e)$. If $v$ has no edge in direction $d$, then $\bar{v}(d)$ is undefined.

The atlas of $P$ is the set of its vertex types.

A locally deterministic coloring can be reconstructed from its atlas and the positions of its in-degree 0 vertices.

**Lemma 26.** Let $P_1, P_2$ be locally deterministic colorings of the arcs of some oriented subgraphs of $Z^2$, $G_1$ and $G_2$ respectively. If

(1) $G_1$ and $G_2$ are acyclic and have no infinite backwards paths,

(2) $P_1$ and $P_2$ have the same atlas,

(3) $G_1$ and $G_2$ have the same vertices with in-degree 0, then $G_1 = G_2$ and $P_1 = P_2$.

**Proof.** By induction on the longest path to each position in $G_1$. ▶

<figure><img src="image_9.png" /></figure>

Finally, a locally deterministic pattern with a unique in-degree 0 vertex can be self-assembled in the aTAM.

**Lemma 27.** Let $\Sigma$ be some finite alphabet, and let $P$ be a locally deterministic coloring of the arcs of some acyclic graph $G$ with no infinite backwards path. Assume the maximal in-degree of a vertex in $G$ is $\delta$ and that $G$ has only one vertex with in-degree 0.

Then there is an aTAM system $S_P$ with temperature $\delta$ with $P$ as its only final production.

**Proof.** Let $A_P$ be the atlas of $P$, pred-inputs and pred-symbols the prediction functions of $P$. By convention, suppose pred-inputs returns an input vectors which is ordered clockwise, starting from direction $N$.

First define the glues of $S_P$ and their strength function $st$. Each glue is a pair $(s, d) \in \Sigma \times \{N, E, S, W\}$. For any symbol $s \in \Sigma$ and direction $d \in \{N, E, S, W\}$, let $\bar{s} = \text{pred-inputs}(s, d)$.
If $d$ is the first element of $\vec{i}$, then its strength is $\text{st}((s, d)) = (\delta + 1 - |\vec{i}|)$, otherwise it is 1.
Hence, for any vertex type $v \in A_P$ with input vector $\vec{v}$, $\sum_{g \in \vec{v}} \text{st}(g) = \delta$.

Then define the set of tile types $S_p$ to be $A_p$, with the glue on the $d$ side of the tile type $\vec{v}$ being $\vec{v}(d)$ if defined, and the null glue otherwise. The seed tile of $S_p$ is the only vertex type of $A_p$ with in-degree 0.

Indeed, any production of $S_P$ is an initial subset of $P$, as can be seen by induction on the attachments.

Then, consider a production $p$ of $S_P$. If $G$ contains some position not covered by $p$, then because $G$ contains neither loops nor infinite paths, it must contain some $v$ with all its predecessors within $\text{dom}(p)$. But then the total strength of glues into $v$ is $\delta$, and the tile corresponding to $P(v)$ must be attachable there. Hence $p$ is not terminal.

Finally, $S_P$ assembles $P$.

<figure><img src="image_9.png" /></figure>

Putting all this together, it is possible to compile a self-describing circuit into a self-assembling system.

**Theorem 28.** Let $C$ be a self-describing normal circuit with only one gate without inputs. Then there is an aTAM system $S_C$ which strictly self-assembles $\text{dom}(C)$.

**Proof.** By lemmas 24 and 27.

<figure><img src="image_10.png" /></figure>

# 4 A Self-Describing Embedded Circuit for the Sierpinski Cacarpet

The next step is to define a self-describing circuit on the Sierpinski Cacarpet.

**Theorem 29.** There is an evaluable circuit $C \square$ with domain $K_\infty$ and with an empty input bus which is self describing. Moreover, $C \square$ has only one gate without inputs.

The remainder of this section is the description of $C \square$. This circuit is built from two sets of messages: layer 1 messages in $\Sigma_1$ and layer 2 messages in $\Sigma_2$, and three fractal structures: a wiring layer $W_\square: K^\infty \to W$, and two function layers, $F_1$ operating on $\Sigma_1$ and $F_2$ operating on $\Sigma_2$.

The wiring layer $C_w: K^\infty \to W$ is the fixed point of a substitution $\kappa_w: W \to W^K$ starting from a seed wiring $s_w$:

$$ \begin{cases} C_w(\vec{0}) = s_w \\ C_w(\vec{z}) = \kappa_w(C_w(\lfloor \frac{z}{K} \rfloor))(z \bmod K) \end{cases} $$

The definition of the function layers is a bit more indirect: there are two sets of labels $L_1$ and $L_2$ respectively, with two rules $\kappa_1: W \to L_1^K$ and $\kappa_2: W \times L_2 \to L_2^K$. The rule $\kappa_2$ takes the form of a substitution.

Their fixpoints, starting from two seed labels $s_1$ and $s_2$ define two tiling of $K^\infty$ with labels of $L_1$ and $L_2$ respectively: $\Lambda_1$ and $\Lambda_2$. On layer 1, $\Lambda_1$ is defined for each position according to the wiring of its parent:

$$ \Lambda_1(\vec{z}) = \kappa_1(C_w(\lfloor \frac{z}{K} \rfloor))(z \bmod K) $$

On layer 2, $\Lambda_2$ is defined for each position according to the wiring and label of its parent in a substitutive manner:

$$ \begin{cases} \Lambda_2(\vec{0}) = s_2 \\ \Lambda_2(\vec{z}) = \kappa_2(C_w(\lfloor \frac{z}{K} \rfloor), C_2(\lfloor \frac{z}{K} \rfloor))(z \bmod K) \end{cases} $$
If $d$ is the first element of $\vec{i}$, then its strength is $\text{st}((s, d)) = (\delta + 1 - |\vec{i}|)$, otherwise it is 1. Hence, for any vertex type $v \in A_P$ with input vector $\vec{v}_v$, $\sum_{g \in \vec{v}_v} \text{st}(g) = \delta$.

Then define the set of tile types $S_p$ to be $A_p$, with the glue on the $d$ side of the tile type $\vec{v}$ being $\vec{v}(d)$ if defined, and the null glue otherwise. The seed tile of $S_p$ is the only vertex type of $A_p$ with in-degree 0.

Indeed, any production of $S_P$ is an initial subset of $P$, as can be seen by induction on the attachments.

Then, consider a production $p$ of $S_P$. If $G$ contains some position not covered by $p$, then because $G$ contains neither loops nor infinite paths, it must contain some $v$ with all its predecessors within $\text{dom}(p)$. But then the total strength of glues into $v$ is $\delta$, and the tile corresponding to $P(v)$ must be attachable there. Hence $p$ is not terminal.

Finally, $S_P$ assembles $P$.

Putting all this together, it is possible to compile a self-describing circuit into a self-assembling system.

**Theorem 28.** Let $C$ be a self-describing normal circuit with only one gate without inputs. Then there is an aTAM system $S_C$ which strictly self-assembles $\text{dom}(C)$.

**Proof.** By lemmas 24 and 27.

# 4 A Self-Describing Embedded Circuit for the Sierpinski Cacarpet

The next step is to define a self-describing circuit on the Sierpinski Cacarpet.

**Theorem 29.** There is an evaluable circuit $C \square$ with domain $K_\infty$ and with an empty input bus which is self describing. Moreover, $C \square$ has only one gate without inputs.

The remainder of this section is the description of $C \square$. This circuit is built from two sets of messages: layer 1 messages in $\Sigma_1$ and layer 2 messages in $\Sigma_2$, and three fractal structures: a wiring layer $W_\square: K^\infty \to W$, and two function layers, $F_1$ operating on $\Sigma_1$ and $F_2$ operating on $\Sigma_2$.

The wiring layer $C_w: K^\infty \to W$ is the fixed point of a substitution $\kappa_w: W \to W^K$ starting from a seed wiring $s_w$:

$$ \begin{cases} C_w(\vec{0}) = s_w \\ C_w(\vec{z}) = \kappa_w(C_w(\lfloor \frac{z}{K} \rfloor))(z \bmod K) \end{cases} $$

The definition of the function layers is a bit more indirect: there are two sets of labels $L_1$ and $L_2$ respectively, with two rules $\kappa_1: W \to L_1^K$ and $\kappa_2: W \times L_2 \to L_2^K$. The rule $\kappa_2$ takes the form of a substitution.

Their fixpoints, starting from two seed labels $s_1$ and $s_2$ define two tiling of $K^\infty$ with labels of $L_1$ and $L_2$ respectively: $\Lambda_1$ and $\Lambda_2$. On layer 1, $\Lambda_1$ is defined for each position according to the wiring of its parent:

$$ \Lambda_1(\vec{z}) = \kappa_1(C_w(\lfloor \frac{z}{K} \rfloor))(z \bmod K) $$

On layer 2, $\Lambda_2$ is defined for each position according to the wiring and label of its parent in a substitutive manner:

$$ \begin{cases} \Lambda_2(\vec{0}) = s_2 \\ \Lambda_2(\vec{z}) = \kappa_2(C_w(\lfloor \frac{z}{K} \rfloor), C_2(\lfloor \frac{z}{K} \rfloor))(z \bmod K) \end{cases} $$
<figure><img src="image_11.png" /><figcaption>Figure 7 $\kappa_1(w_s, \text{secd})$, the first iteration of $\kappa_1$ on the seed gate. The wirings are given graphically; all gates have the normal label, except the $s$ at (0,0) which has label secd. For the wiring with two inputs, the fat arrow represents the input number 0; all output wires have number 0: $w$-output-num($d$) = 0</figcaption></figure>

Finally, the actual gate functions are defined from two functions, instantiate_1 on layer 1 and instantiate_2 on layer 2, which define a function on $\Sigma_1$ (respectively $\Sigma_2$) from four elements, two wirings and two labels in $L_1$ (respectively $L_2$), one each for the gate and its parent. Together with the substitutions $\kappa_i$, they define a circuit $\mu_i(w, l)$ with domain $K$ known as the layer-$i$ meta-gate obtained by $w$ and $l$:

$$ \left\{ \begin{array}{l} \mu_1(w, l) : K \to \text{Gates}(\Sigma_1) \\ \mu_1(w, l) : \vec{z} \mapsto \{ \text{wiring} : \kappa_w(w)(\vec{z}), \text{func} : \text{in instances}_1(w, l, \kappa_w(w)(\vec{z}), \kappa_1(w)(\vec{z})) \} \\ \mu_2(w, l) : K \to \text{Gates}(\Sigma_2) \\ \mu_2(w, l) : \vec{z} \mapsto \{ \text{wiring} : \kappa_w(w)(\vec{z}), \text{func} : \text{in instances}_2(w, l, \kappa_w(w)(\vec{z}), \kappa_2(w, l)(\vec{z})) \}. \end{array} \right. $$

In this circuit, the wiring of each gate is given by $\kappa_w(w)$, and its function is given by instantiating the label given by $\kappa_i$. When iterating this process, a gate $g$ appearing at position $\vec{z}$ in some parent meta-gate $\mu_i(l, w)$, the child meta-gate $\mu_i(g)$ associated with $g$ is defined as $\mu_i(g \cdot \text{wiring}, \kappa_i(l, w))$. The functions instantiate_i are each injective in their last argument, ensuring this does not create any ambiguity.

Finally, these meta-gates beget the two layers of circuits $C_1$ and $C_2$ by:

$$ \left\{ \begin{array}{l} C_i(\vec{0}) = \{ \text{wiring} : s_w, \text{func} : s_i \} \\ C_i(\vec{z}) = \mu_i(C_i(\lfloor \frac{\vec{z}}{K} \rfloor))(\vec{z} \bmod K) \end{array} \right. . $$

By this definition, the wirings of $C_1(\vec{z})$ and $C_2(\vec{z})$ are the same —they are given by $C_w$, so $C_{\square} : \vec{z} \mapsto C_1(\vec{z}) \otimes C_2(\vec{z})$ defines a circuit with alphabet $\Sigma_1 \times \Sigma_2$ and domain $K^\infty$.

The next subsections are the description of $C_w$, followed by those of $C_1$, then $C_2$, and finally the proof of that $C_{\square}$ is self-describing.

## 4.1 The wiring layer

The seed wiring $s_w$ is represented on the left of figure 7. On the right of the same figure is its image $\kappa_w(s_z)$.

For any wiring $w$, $\kappa_1(w)$ will only contain wirings with at most two input sides, and these input sides are adjacent. Thus, all gates in $C_w$ have at most two input sides and they are adjacent. Hence, $\kappa_w$ only needs to be defined on wirings with that property.

The definition of $\kappa_w$ is isotropic: $\kappa_w$ commutes with a rotation of $\pi/2$ and with reflections. This property will be upheld simply by giving the definition of $\kappa_w$ up to rotation and reflection.
<figure><img src="image_10.png" /><figcaption>Figure 7 $\kappa_1(w_s, \text{secd})$, the first iteration of $\kappa_1$ on the seed gate. The wirings are given graphically; all gates have the normal label, except the $s$ at (0,0) which has label secd. For the wiring with two inputs, the fat arrow represents the input number 0; all output wires have number 0: $w$-output-num($d$) = 0</figcaption></figure>

Finally, the actual gate functions are defined from two functions, instantiate_1 on layer 1 and instantiate_2 on layer 2, which define a function on $\Sigma_1$ (respectively $\Sigma_2$) from four elements, two wirings and two labels in $L_1$ (respectively $L_2$), one each for the gate and its parent. Together with the substitutions $\kappa_i$, they define a circuit $\mu_i(w, l)$ with domain $K$ known as the layer-$i$ meta-gate obtained by $w$ and $l$:

$$ \left\{ \begin{array}{l} \mu_1(w, l) : K \to \text{Gates}(\Sigma_1) \\ \mu_1(w, l) : \vec{z} \mapsto \{ \text{wiring} : \kappa_w(w)(\vec{z}), \text{func} : \text{in instances}_1(w, l, \kappa_w(w)(\vec{z}), \kappa_1(w)(\vec{z})) \} \\ \mu_2(w, l) : K \to \text{Gates}(\Sigma_2) \\ \mu_2(w, l) : \vec{z} \mapsto \{ \text{wiring} : \kappa_w(w)(\vec{z}), \text{func} : \text{in instances}_2(w, l, \kappa_w(w)(\vec{z}), \kappa_2(w, l)(\vec{z})) \}. \end{array} \right. $$

In this circuit, the wiring of each gate is given by $\kappa_w(w)$, and its function is given by instantiating the label given by $\kappa_i$. When iterating this process, a gate $g$ appearing at position $\vec{z}$ in some parent meta-gate $\mu_i(l, w)$, the child meta-gate $\mu_i(g)$ associated with $g$ is defined as $\mu_i(g \cdot \text{wiring}, \kappa_i(l, w))$. The functions instantiate_i are each injective in their last argument, ensuring this does not create any ambiguity.

Finally, these meta-gates beget the two layers of circuits $C_1$ and $C_2$ by:

$$ \left\{ \begin{array}{l} C_i(\vec{0}) = \{ \text{wiring} : s_w, \text{func} : s_i \} \\ C_i(\vec{z}) = \mu_i(C_i(\lfloor \frac{\vec{z}}{K} \rfloor))(\vec{z} \bmod K) \end{array} \right. . $$

By this definition, the wirings of $C_1(\vec{z})$ and $C_2(\vec{z})$ are the same —they are given by $C_w$, so $C_\square : \vec{z} \mapsto C_1(\vec{z}) \otimes C_2(\vec{z})$ defines a circuit with alphabet $\Sigma_1 \times \Sigma_2$ and domain $K^\infty$.

The next subsections are the description of $C_w$, followed by those of $C_1$, then $C_2$, and finally the proof of that $C_\square$ is self-describing.

## 4.1 The wiring layer

The seed wiring $s_w$ is represented on the left of figure 7. On the right of the same figure is its image $\kappa_w(s_z)$.

For any wiring $w$, $\kappa_1(w)$ will only contain wirings with at most two input sides, and these input sides are adjacent. Thus, all gates in $C_w$ have at most two input sides and they are adjacent. Hence, $\kappa_w$ only needs to be defined on wirings with that property.

The definition of $\kappa_w$ is isotropic: $\kappa_w$ commutes with a rotation of $\pi/2$ and with reflections. This property will be upheld simply by giving the definition of $\kappa_w$ up to rotation and reflection.
Lastly, for each input wire in $w$ there are two wires in the input bus of $\kappa_w(w)$, and for each output wire in $w$ there are two wires in the output bus of $\kappa_w(w)$. The position of these wires are as follows, up to rotation:

<table><thead><tr><th colspan="2">input of w</th><th colspan="3">input i of κ<sub>w</sub>(w)</th></tr><tr><th>w·Inputs</th><th>direction</th><th>position</th><th>direction</th><th>i·Inputs</th></tr></thead><tbody><tr><td rowspan="2">(W)</td><td rowspan="2">W</td><td>(0, 2)</td><td>W</td><td>(W)</td></tr><tr><td>(0, 3)</td><td>W</td><td>(S, W)</td></tr><tr><td rowspan="4">(S, W)</td><td rowspan="2">W</td><td>(0, 0)</td><td>W</td><td>(S, W)</td></tr><tr><td>(0, 1)</td><td>W</td><td>(S, W)</td></tr><tr><td rowspan="2">S</td><td>(0, 0)</td><td>S</td><td>(S, W)</td></tr><tr><td>(1, 0)</td><td>S</td><td>(S, W)</td></tr></tbody></table>

<table><thead><tr><th colspan="2">output of g</th><th colspan="3">output o of κ<sub>w</sub>(g)</th></tr><tr><th>w·outwires(d)</th><th>direction d</th><th>position</th><th>direction d'</th><th>i·outwires(d')</th></tr></thead><tbody><tr><td rowspan="2">(W)</td><td rowspan="2">E</td><td>(5, 2)</td><td>E</td><td>W</td></tr><tr><td>(5, 3)</td><td>E</td><td>(S, W)</td></tr><tr><td rowspan="2">(S, W)</td><td rowspan="2">E</td><td>(5, 0)</td><td>E</td><td>(S, W)</td></tr><tr><td>(5, 1)</td><td>E</td><td>(S, W)</td></tr><tr><td rowspan="2">(S, W)</td><td rowspan="2">N</td><td>(0, 5)</td><td>N</td><td>(S, W)</td></tr><tr><td>(1, 5)</td><td>N</td><td>(S, W)</td></tr></tbody></table>

Thus, if $w$ has $w \cdot$ Inputs $= (W)$, $w \cdot$ Outputs $= \{N, E, S\}$ with $w \cdot$ outwires($N$) $= Sw$, $w \cdot$ outwires($E$) $= sW$ and $w \cdot$ outwires($S$) $= N$, then $\kappa_w(w)$ has the corresponding input and output busses and wires:

$$ \begin{cases} \vec{I} = ((-1, 2) \to (0, 2)\text{(with wire W}), (-1, 3) \to (0, 3)\text{(with wire Ws}) \\ \vec{O} = ((0, 5) \to (0, 6)\text{(with wire Sw}), (1, 5) \to (0, 6)\text{(with wire Sw}), (5, 0) \to (6, 0)\text{(with wire Ws}), (5, 1) \to (6, 1)\text{(with} \end{cases} $$

## Wirings with no inputs

All wirings without input are sent by $\kappa_w$ to the array of wirings represented on figure 7. The seed wiring $s_w$ is the only one to effectively appear when iterating $\kappa_w$.

## Wirings with one input

A wiring with one input is cut according to figure 9.

The wirings in $\kappa_w(g)$ depend on the input and outputs of $w$. Since $w$ has only one input, it is sufficient, up to rotation, to examine the case where $w \cdot$ Inputs $= \{W\}$. The black arrows of figure 9 depict the case where $w \cdot$ Outputs $= \emptyset$. For each $d \in w \cdot$ Outputs, some extra wires are needed. The additional wires for an output in the $N$ direction depend on whether the directions appearing in $w \cdot$ outwires($N$) are $\{S\}$, $\{S, E\}$ or $\{S, W\}$. The wires for the other output directions are derived from these by rotation. Figure 9 has one direction with each case, showing the complete range of possibilities for the extra wires; they are represented in dotted lines on the figure.

## Wirings with two (adjacent) inputs

The image of such a wiring $w$ by $\kappa_w$ is defined on figure 10, which is rotated and reflected so that the $S$ side of the figure is mapped to the 0 input of $w$, and the $W$ side to the 1 input of $w$.
Lastly, for each input wire in $w$ there are two wires in the input bus of $\kappa_w(w)$, and for each output wire in $w$ there are two wires in the output bus of $\kappa_w(w)$. The position of these wires are as follows, up to rotation:

<table><thead><tr><th colspan="2">input of w</th><th colspan="3">input i of κ<sub>w</sub>(w)</th></tr><tr><th>w·Inputs</th><th>direction</th><th>position</th><th>direction</th><th>i·Inputs</th></tr></thead><tbody><tr><td rowspan="2">(W)</td><td rowspan="2">W</td><td>(0, 2)</td><td>W</td><td>(W)</td></tr><tr><td>(0, 3)</td><td>W</td><td>(S, W)</td></tr><tr><td rowspan="4">(S, W)</td><td rowspan="2">W</td><td>(0, 0)</td><td>W</td><td>(S, W)</td></tr><tr><td>(0, 1)</td><td>W</td><td>(S, W)</td></tr><tr><td rowspan="2">S</td><td>(0, 0)</td><td>S</td><td>(S, W)</td></tr><tr><td>(1, 0)</td><td>S</td><td>(S, W)</td></tr></tbody></table>

<table><thead><tr><th colspan="2">output of g</th><th colspan="3">output o of κ<sub>w</sub>(g)</th></tr><tr><th>w·outwires(d)</th><th>direction d</th><th>position</th><th>direction d'</th><th>i·outwires(d')</th></tr></thead><tbody><tr><td rowspan="2">(W)</td><td rowspan="2">E</td><td>(5, 2)</td><td>E</td><td>W</td></tr><tr><td>(5, 3)</td><td>E</td><td>(S, W)</td></tr><tr><td rowspan="2">(S, W)</td><td rowspan="2">E</td><td>(5, 0)</td><td>E</td><td>(S, W)</td></tr><tr><td>(5, 1)</td><td>E</td><td>(S, W)</td></tr><tr><td rowspan="2">(S, W)</td><td rowspan="2">N</td><td>(0, 5)</td><td>N</td><td>(S, W)</td></tr><tr><td>(1, 5)</td><td>N</td><td>(S, W)</td></tr></tbody></table>

Thus, if $w$ has $w \cdot$ Inputs $= (W)$, $w \cdot$ Outputs $= \{N, E, S\}$ with $w \cdot$ outwires($N$) $= Sw$, $w \cdot$ outwires($E$) $= sW$ and $w \cdot$ outwires($S$) $= N$, then $\kappa_w(w)$ has the corresponding input and output busses and wires:

$$ \begin{cases} \vec{I} = ((-1, 2) \to (0, 2)\text{(with wire W}), (-1, 3) \to (0, 3)\text{(with wire Ws}) \\ \vec{O} = ((0, 5) \to (0, 6)\text{(with wire Sw}), (1, 5) \to (0, 6)\text{(with wire Sw}), (5, 0) \to (6, 0)\text{(with wire Ws}), (5, 1) \to (6, 1)\text{(with} \end{cases} $$

## Wirings with no inputs

All wirings without input are sent by $\kappa_w$ to the array of wirings represented on figure 7. The seed wiring $s_w$ is the only one to effectively appear when iterating $\kappa_w$.

## Wirings with one input

A wiring with one input is cut according to figure 9.

The wirings in $\kappa_w(g)$ depend on the input and outputs of $w$. Since $w$ has only one input, it is sufficient, up to rotation, to examine the case where $w \cdot$ Inputs $= \{W\}$. The black arrows of figure 9 depict the case where $w \cdot$ Outputs $= \emptyset$. For each $d \in w \cdot$ Outputs, some extra wires are needed. The additional wires for an output in the $N$ direction depend on whether the directions appearing in $w \cdot$ outwires($N$) are $\{S\}$, $\{S, E\}$ or $\{S, W\}$. The wires for the other output directions are derived from these by rotation. Figure 9 has one direction with each case, showing the complete range of possibilities for the extra wires; they are represented in dotted lines on the figure.

## Wirings with two (adjacent) inputs

The image of such a wiring $w$ by $\kappa_w$ is defined on figure 10, which is rotated and reflected so that the $S$ side of the figure is mapped to the 0 input of $w$, and the $W$ side to the 1 input of $w$.
<figure><img src="image_12.png" /><figcaption>■ **Figure 8** Location of the input wires in $\kappa_1(g)$ according to the input sides of $w$ = wiring $g$. The output wires mirror the input sides of the neighboring tiles.</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>■ **Figure 9** $\kappa_1(w,l)$ when $w$·Inputs = ($W$). The wirings are given graphically; on layer 1, all gates have the normal label (black), except for the gate at (0,3) which has label input (red). Dotted segments are parts of the wiring only if the corresponding element is in the outputs of $w$. For wirings with two inputs, the fat arrow represents the first input. The † marks the potential position for label $\mathfrak{D}$ on layer 2.</figcaption></figure>
<figure><img src="image_11.png" /><figcaption>■ **Figure 8** Location of the input wires in $\kappa_1(g)$ according to the input sides of $w$ = wiring $g$. The output wires mirror the input sides of the neighboring tiles.</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>■ **Figure 9** $\kappa_1(w,l)$ when $w$·Inputs = (W). The wirings are given graphically; on layer 1, all gates have the normal label (black), except for the gate at (0,3) which has label input (red). Dotted segments are parts of the wiring only if the corresponding element is in the outputs of $w$. For wirings with two inputs, the fat arrow represents the first input. The † marks the potential position for label $\mathfrak{O}$ on layer 2.</figcaption></figure>
<figure><img src="image_14.png" /></figure>

■ **Figure 10** $\kappa_1(w, l)$ when Inputs $w = (S, W)$. The wirings are given graphically; all gates have the **normal** label except for the input gate at (0,0) which has label **input**. This configuration gets rotated and reflected according to the inputs of the gate, so that the arrows on the outer ring form a path from the side with input 0 to the side with input 1, “the long way around”. The '*' marks the *special* position on layer 2, and the † marks the position where label $\mathfrak{O}$ may appear.

**▶ Lemma 30.** For each gate $w$, $\kappa_w(w)$ is the wiring of a normal circuit. Moreover, $C_w$ is the wiring of a normal, closed circuit.

**Proof.** This follows from observation of the schemata describing each $\kappa_w(w)$ and observing that for two wirings $w, w'$, if an output side in direction $d$ of $w$ matches an input side in direction $-d$ of $w'$, then the corresponding sides of $\kappa_w(w)$ and $\kappa_w(w')$ also match.

Additionally, each iteration of $\kappa_w$ on $s_w$ is without inputs, so $C_w$ is closed.

## 4.2 Layer 1

The components of layer 1 are an alphabet $\Sigma_1$, a finite set of labels $L_1$, a substitution $\kappa_1 : W \to L_1^K$, and for each label $l \in L_1$, and an instantiation function $\text{instantiate}_1$. Layer 1 can then be realized as described above into a circuit with the wirings of $C_w$ and the functions given by instantiating the fixpoint of $\kappa_1$.

The set of labels is $L_1 = \{\mathfrak{s}_1, \text{normal}, \text{input}\}$.

The elements of $\Sigma_1$ are *layer 1 messages*.

**▶ Definition 31 (Layer 1 Message).** A layer 1 message is a triple $\{ \text{pos} = \vec{z} \in K_1, \text{parent-wiring} = w \in W, \cdot \text{ parent} = l \in L_1 \}$.

The circuit $C_1$ is going to be defined by iterating $\kappa_w$ and $\kappa_1$ starting from $s_w$ and $\mathfrak{s}_1$, then instantiating the labels.

### Labels

The label function $\kappa_1 : W \to L_1^K$ assigns the label **normal** at all positions except:

$$ \kappa_1(s_w)(\vec{0}) = \mathfrak{s}_1 $$
<figure><img src="image_13.png" /></figure>

■ **Figure 10** $\kappa_1(w, l)$ when Inputs $w = (S, W)$. The wirings are given graphically; all gates have the **normal** label except for the input gate at (0,0) which has label **input**. This configuration gets rotated and reflected according to the inputs of the gate, so that the arrows on the outer ring form a path from the side with input 0 to the side with input 1, "the long way around". The '*' marks the *special* position on layer 2, and the † marks the position where label $\mathfrak{O}$ may appear.

**▶ Lemma 30.** For each gate $w$, $\kappa_w(w)$ is the wiring of a normal circuit. Moreover, $C_w$ is the wiring of a normal, closed circuit.

*Proof*. This follows from observation of the schemata describing each $\kappa_w(w)$ and observing that for two wirings $w, w'$, if an output side in direction $d$ of $w$ matches an input side in direction $-d$ of $w'$, then the corresponding sides of $\kappa_w(w)$ and $\kappa_w(w')$ also match.

Additionally, each iteration of $\kappa_w$ on $s_w$ is without inputs, so $C_w$ is closed.

## 4.2 Layer 1

The components of layer 1 are an alphabet $\Sigma_1$, a finite set of labels $L_1$, a substitution $\kappa_1 : W \to L_1^K$, and for each label $l \in L_1$, and an instantiation function $\text{instantiate}_1$. Layer 1 can then be realized as described above into a circuit with the wirings of $C_w$ and the functions given by instantiating the fixpoint of $\kappa_1$.

The set of labels is $L_1 = \{\mathfrak{s}_1, \text{normal}, \text{input}\}$.

The elements of $\Sigma_1$ are *layer 1 messages*.

**▶ Definition 31 (Layer 1 Message).** A layer 1 message is a triple $\{ \text{pos} = \vec{z} \in K_1, \text{parent-wiring} = w \in W, \cdot \text{ parent} = l \in L_1 \}$.

The circuit $C_1$ is going to be defined by iterating $\kappa_w$ and $\kappa_1$ starting from $s_w$ and $\mathfrak{s}_1$, then instantiating the labels.

### Labels

The label function $\kappa_1 : W \to L_1^K$ assigns the label **normal** at all positions except:

$$ \kappa_1(s_w)(\vec{0}) = \mathfrak{s}_1 $$
18 Strict Self-Assembly of Fractals

if $w$ has at least one input, then $\kappa_1(w)(\tilde{z})$ = **input** for the position $\tilde{z}$ which receives the input wire 0 in $\kappa_w(w)$.

The seed function

The starting label is $\mathfrak{s}_1$, it only ever appears at position $(0,0)$ in $\kappa_1(s_w, \mathfrak{s}_1)$.

Since $s_1$ has no inputs, its associated function $f_s = \text{enumerate}_1(s_w, \mathfrak{s}_1, s_w, \mathfrak{s}_1)$ is a constant function with value $f_s() = \{ \text{pos} : (0,0), \text{parent-label} : \mathfrak{s}_1, \text{parent-wiring} : s_w \}$.

Gate functions for layer 1

There are two types of functions for the gates output by $\kappa_1(g)$ other than the seed. They have a either an *increment* function incr[$k$, $D$] with $k \in \{1, 2\}$ and $D \in \{N, E, S, W\}$ or a *reparenting* function set-parent[$k$, $D$, $w$, $c$], with $k \in \{1, 2\}$, $D \in \{N, E, S, W\}$, $w$ a wiring and $c \in C$ a color. The versions with $k = 2$ take two inputs but ignore the second one. The functions incr and set-parent are defined as follows:

$$ \text{incr}[1, D](m) \cdot \text{parent} = m \cdot \text{parent}, $$

$$ \text{incr}[1, D](m) \cdot \text{pos} = \text{pos} m + D $$

$$ \text{set-parent}[1, D, w, c](m) \cdot \text{parent} = (w, c) $$

$$ \text{set-parent}[1, D, w, c](m) \cdot \text{pos} = m \cdot \text{pos} + D $$

$$ \text{incr}[2, D](m, m') = \text{incr}[1, D](m) $$

$$ \text{set-parent}[2, D, w, c](m, m') = \text{set-parent}[1, D, w, c](m). $$

The function of each gate is fixed from its label and wiring, and those of its parent through $\text{enumerate}_1$ as follows:

$$ \begin{cases} \text{enumerate}_1(w_p, l_p, w, \text{normal}) = \text{incr}[k, D] \\ \text{enumerate}_1(w_p, l_p, w, \text{input}) = \text{set-parent}[k, D, w_p, l_p], \end{cases} $$

where $k$ is the number of inputs of $w$, and $D$ is the direction of its first input.

Behavior and Self-Description of Layer 1

The circuit $C_1$ obtained from $\kappa_1$ is normal, by lemma 30. Let $e = \tilde{C}_1 : K^\infty \times \{N, E, S, W\} \to \Sigma_l$ be the evaluation function of $C_1$. That function $e$ enjoys a simple description, which reflects the fact that in $C_1$, the different meta-gates do not actually communicate. On layer 2 however, there will be some communication between meta-gates, as described in the next section.

**Lemma 32.** Let $w \in W$, $l \in L_1$ and $a : p \mapsto p'$ be an internal or outgoing arc in $\kappa_w(w)$. If $w$ has no inputs, assume $l = \mathfrak{s}_1$.

For any input $\tilde{t}$ of $\mu_1(w, l)$, let $m = \mu_1(w, l)(\tilde{t}, a)$ be the value of arc $a$ on input $\tilde{t}$. Then $m \cdot \text{pos} = p$, $m \cdot \text{parent-wiring} = w$ and $m \cdot \text{parent-label} = l$.

**Proof.** By induction on the non-incoming arcs of the (acyclic) dependency graph $D$ of $\kappa_w(w)$.

If $w$ is the seed wiring $s_w$, then the root of $D$ is also $s_1$ and its outputs satisfy $e_g(a) \cdot \text{pos} = (0,0)$, $e_g(a) \cdot \text{parent-wiring} = s_1$ wiring and $e_g(a) \cdot \text{parent-label} = \mathfrak{s}_1$.
18 Strict Self-Assembly of Fractals

if $w$ has at least one input, then $\kappa_1(w)(\tilde{z}) = \text{input}$ for the position $\tilde{z}$ which receives the input wire 0 in $\kappa_w(w)$.

The seed function

The starting label is $\mathfrak{s}_1$, it only ever appears at position $(0,0)$ in $\kappa_1(s_w, \mathfrak{s}_1)$.

Since $s_1$ has no inputs, its associated function $f_s = \text{enumerate}_1(s_w, \mathfrak{s}_1, s_w, \mathfrak{s}_1)$ is a constant function with value $f_s() = \{ \text{pos} : (0,0), \text{parent-label} : \mathfrak{s}_1, \text{parent-wiring} : s_w \}$.

Gate functions for layer 1

There are two types of functions for the gates output by $\kappa_1(g)$ other than the seed. They have a either an *increment* function incr[$k$, $D$] with $k \in \{1, 2\}$ and $D \in \{N, E, S, W\}$ or a *reparenting* function set-parent[$k$, $D$, $w$, $c$], with $k \in \{1, 2\}$, $D \in \{N, E, S, W\}$, $w$ a wiring and $c \in C$ a color. The versions with $k = 2$ take two inputs but ignore the second one. The functions incr and set-parent are defined as follows:

$$ \text{incr}[1, D](m) \cdot \text{parent} = m \cdot \text{parent}, $$

$$ \text{incr}[1, D](m) \cdot \text{pos} = \text{pos} m + D $$

$$ \text{set-parent}[1, D, w, c](m) \cdot \text{parent} = (w, c) $$

$$ \text{set-parent}[1, D, w, c](m) \cdot \text{pos} = m \cdot \text{pos} + D $$

$$ \text{incr}[2, D](m, m') = \text{incr}[1, D](m) $$

$$ \text{set-parent}[2, D, w, c](m, m') = \text{set-parent}[1, D, w, c](m). $$

The function of each gate is fixed from its label and wiring, and those of its parent through $\text{enumerate}_1$ as follows:

$$ \begin{cases} \text{enumerate}_1(w_p, l_p, w, \text{normal}) = \text{incr}[k, D] \\ \text{enumerate}_1(w_p, l_p, w, \text{input}) = \text{set-parent}[k, D, w_p, l_p], \end{cases} $$

where $k$ is the number of inputs of $w$, and $D$ is the direction of its first input.

Behavior and Self-Description of Layer 1

The circuit $C_1$ obtained from $\kappa_1$ is normal, by lemma 30. Let $e = \tilde{C}_1 : K^\infty \times \{N, E, S, W\} \to \Sigma_l$ be the evaluation function of $C_1$. That function $e$ enjoys a simple description, which reflects the fact that in $C_1$, the different meta-gates do not actually communicate. On layer 2 however, there will be some communication between meta-gates, as described in the next section.

**Lemma 32.** Let $w \in W$, $l \in L_1$ and $a : p \mapsto p'$ be an internal or outgoing arc in $\kappa_w(w)$. If $w$ has no inputs, assume $l = \mathfrak{s}_1$.

For any input $\tilde{t}$ of $\mu_1(w, l)$, let $m = \mu_1(w, l)(\tilde{t}, a)$ be the value of arc $a$ on input $\tilde{t}$. Then $m \cdot \text{pos} = p$, $m \cdot \text{parent-wiring} = w$ and $m \cdot \text{parent-label} = l$.

**Proof.** By induction on the non-incoming arcs of the (acyclic) dependency graph $D$ of $\kappa_w(w)$.

If $w$ is the seed wiring $s_w$, then the root of $D$ is also $s_1$ and its outputs satisfy $e_g(a) \cdot \text{pos} = (0,0)$, $e_g(a) \cdot \text{parent-wiring} = s_1$ and $e_g(a) \cdot \text{parent-label} = \mathfrak{s}_1$.
Otherwise, $\kappa_1(w)$ has a unique position $\tilde{z}_i$ with label input, corresponding to a gate in $\mu_1(l, w)$ with function set-parent[$k, D, w, l$], for some $k$ and $D$. By definition of set-parent, its outputs satisfy $e_g(a) \cdot \text{pos} = \tilde{z}_i$, $e_g(a) \cdot \text{parent-wiring} = w$ and $e_g(a) \cdot \text{parent-label} = l$.

In both cases, each other gate $g'$ at position $\tilde{z}$ of $\mu_1(l, w)$ has function incr[$k, D$], where $k$ is the number of inputs of $g'$, and $D$ is the direction of its first input arc $i = \tilde{z} - D \stackrel{D}{\longmapsto} z$. By induction, $e_g(i) \cdot \text{pos} = z - D$ and $e_g(i) \cdot \text{parent} = (g \cdot \text{wiring}, \text{label}(g))$. By definition of incr[$k, D$], each of the output arcs $o$ of $g'$ verify $e_g(o) \cdot \text{pos} = (\tilde{z} - D) + D = \tilde{z}$ and $e_g(a) \cdot \text{parent-wiring} = w$ and $e_g(a) \cdot \text{parent-label} = l$. ◀

Additionally, $C_1$ is “mostly self-describing”: the first input of a gate $g$ is enough to recover $g$, except for the value of $w$ and $c$ in gates with a function of the form set-parent[$k, D, w, c$].

**Lemma 33.** For a position $p \in K^\infty$, let $\vec{e} = \text{Inputs } C_1(p) \cdot \text{wiring be the input arcs of } C_1(p)$; let $d_i$ be the direction of $e_i$.

There is a function dec-gate : $\Sigma_1 \times \{N, E, S, W\} \to \text{Gates}(\Sigma_1) \cup \perp$ such that for all $p \in K^\infty$,

- if $C_1(p) \cdot \text{func is incr}[k, d_0]$, then dec-gate($\tilde{C}_1(e_0), d_0$) = $C_1(p)$

- if $C_1(p) \cdot \text{func is set-parent}[k, d_0, -, -]$ then dec-gate($\tilde{C}_1(e_0), d_0$) = $\perp$.

**Proof.** The function dec-gate is defined as follows: let $m \in \Sigma_1$ be a local message, and $d \in \{N, E, S, W\}$. Let $p = m \cdot \text{pos}$, if $p-d \notin \{0, \dots, 5\}^2$, then dec-gate($m, d$) = $\perp$. Otherwise, dec-gate($m, d$) is the gate at position $p$ in $\mu_1(m \cdot \text{parent-wiring}, m \cdot \text{parent})$.

By lemma 32, dec-gate satisfies the lemma. ◀

Moreover, when dec-gate($e(e_O), d_0$) = $\perp$, $g$ itself cannot be determined, but its label and wiring can, as well as $\mu_1(g)$.

**Corollary 34.** For a position $p \in K^\infty$, let $\vec{e} = C_1(p) \cdot \text{Inputs} \cdot \text{wiring be the input arcs of } C_1(p)$; let $d_i$ be the direction of $e_i$,

- there is a function dec-gate$_w$ : $\Sigma_1 \times \{N, E, S, W\} \to W$ such that for each position $p \in K^\infty$, dec-gate$_w(\tilde{C}_1(e_0), d_0) = C_1(p) \cdot \text{wiring}$

- there is a function dec-gate$_l$ : $\Sigma_1 \times \{N, E, S, W\} \to W$ such that for each position $p \in K^\infty$, dec-gate$_l(\tilde{C}_1(e_0), d_0) = \Lambda_1(p)$

**Proof.** For dec-gate$_w$ and dec-gate$_l$, it suffices to observe that whenever dec-gate($\tilde{C}_1(e_0), d_0$) = $\perp$ at some position $p$, $\tilde{C}_1(p)$ has label input, and its wiring only depends on its position within its metagate. ◀

## 4.3 Layer 2

A second layer is needed in order to get full self-description of the circuit on $K^\infty$. This layer routes global information between the meta-gates so that the input gate of each meta-gate can be identified by its incoming global message. The construction needs to “tie the knot”, so it is not only needed to recover the identity of the input gate on the layer 1, but also on layer 2 itself.

This layer is defined by a set $L_2$ of labels, an alphabet $\Sigma_2$, the label substitution $\kappa_2$ and its instantiation function. In contrast with layer 1, $\kappa_2$ takes as input a wiring, as well as a label. This makes the definition of $\Lambda_2$ recursive. In contrast with layer 1, on layer 2, the two-step definition of gates using labels and the function instantiate is actually *needed* because of a subtlety related to the tying of the knot. The functions of some gates make use
Otherwise, $\kappa_1(w)$ has a unique position $\tilde{z}_i$ with label input, corresponding to a gate in $\mu_1(l, w)$ with function set-parent[$k, D, w, l$], for some $k$ and $D$. By definition of set-parent, its outputs satisfy $e_g(a) \cdot \text{pos} = \tilde{z}_i$, $e_g(a) \cdot \text{parent-wiring} = w$ and $e_g(a) \cdot \text{parent-label} = l$.

In both cases, each other gate $g'$ at position $\tilde{z}$ of $\mu_1(l, w)$ has function incr[$k, D$], where $k$ is the number of inputs of $g'$, and $D$ is the direction of its first input arc $i = \tilde{z} - D \stackrel{D}{\longmapsto} z$. By induction, $e_g(i) \cdot \text{pos} = z - D$ and $e_g(i) \cdot \text{parent} = (g \cdot \text{wiring}, \text{label}(g))$. By definition of incr[$k, D$], each of the output arcs $o$ of $g'$ verify $e_g(o) \cdot \text{pos} = (\tilde{z} - D) + D = \tilde{z}$ and $e_g(a) \cdot \text{parent-wiring} = w$ and $e_g(a) \cdot \text{parent-label} = l$. ◀

Additionally, $C_1$ is “mostly self-describing”: the first input of a gate $g$ is enough to recover $g$, except for the value of $w$ and $c$ in gates with a function of the form set-parent[$k, D, w, c$].

**Lemma 33.** For a position $p \in K^\infty$, let $\vec{e} = \text{Inputs } C_1(p) \cdot \text{wiring be the input arcs of } C_1(p)$; let $d_i$ be the direction of $e_i$.

There is a function dec-gate : $\Sigma_1 \times \{N, E, S, W\} \to \text{Gates}(\Sigma_1) \cup \perp$ such that for all $p \in K^\infty$,

- if $C_1(p) \cdot \text{func is incr}[k, d_0]$, then dec-gate($\tilde{C}_1(e_0), d_0$) = $C_1(p)$

- if $C_1(p) \cdot \text{func is set-parent}[k, d_0, -, -]$ then dec-gate($\tilde{C}_1(e_0), d_0$) = $\perp$.

**Proof.** The function dec-gate is defined as follows: let $m \in \Sigma_1$ be a local message, and $d \in \{N, E, S, W\}$. Let $p = m \cdot \text{pos}$, if $p-d \notin \{0, \dots, 5\}^2$, then dec-gate($m, d$) = $\perp$. Otherwise, dec-gate($m, d$) is the gate at position $p$ in $\mu_1(m \cdot \text{parent-wiring}, m \cdot \text{parent})$.

By lemma 32, dec-gate satisfies the lemma. ◀

Moreover, when dec-gate($e(e_O), d_0$) = $\perp$, $g$ itself cannot be determined, but its label and wiring can, as well as $\mu_1(g)$.

**Corollary 34.** For a position $p \in K^\infty$, let $\vec{e} = C_1(p) \cdot \text{Inputs} \cdot \text{wiring be the input arcs of } C_1(p)$; let $d_i$ be the direction of $e_i$,

- there is a function dec-gate$_w$ : $\Sigma_1 \times \{N, E, S, W\} \to W$ such that for each position $p \in K^\infty$, dec-gate$_w(\tilde{C}_1(e_0), d_0) = C_1(p) \cdot \text{wiring}$

- there is a function dec-gate$_l$ : $\Sigma_1 \times \{N, E, S, W\} \to W$ such that for each position $p \in K^\infty$, dec-gate$_l(\tilde{C}_1(e_0), d_0) = \Lambda_1(p)$

**Proof.** For dec-gate$_w$ and dec-gate$_l$, it suffices to observe that whenever dec-gate($\tilde{C}_1(e_0), d_0$) = $\perp$ at some position $p$, $\tilde{C}_1(p)$ has label input, and its wiring only depends on its position within its metagate. ◀

## 4.3 Layer 2

A second layer is needed in order to get full self-description of the circuit on $K^\infty$. This layer routes global information between the meta-gates so that the input gate of each meta-gate can be identified by its incoming global message. The construction needs to “tie the knot”, so it is not only needed to recover the identity of the input gate on the layer 1, but also on layer 2 itself.

This layer is defined by a set $L_2$ of labels, an alphabet $\Sigma_2$, the label substitution $\kappa_2$ and its instantiation function. In contrast with layer 1, $\kappa_2$ takes as input a wiring, as well as a label. This makes the definition of $\Lambda_2$ recursive. In contrast with layer 1, on layer 2, the two-step definition of gates using labels and the function instantiate is actually *needed* because of a subtlety related to the tying of the knot. The functions of some gates make use
of $\kappa_2$. Thus $\kappa_2$ shall not directly manipulate the gates or their function, lest the definition of layer 2 becomes cyclical and possibly ill-founded.

The set of layer 2 labels is $L_2 = \{s, i_1, i_2, \partial\mathcal{L}, \partial\mathfrak{A}\}$.

## Layer 2 messages

A message on layer 2 is an element of $\Sigma_2$; it is built from:

- $m \cdot \text{parent-label}_2 \in L_2$,

- $m \cdot \text{global, itself consisting of:}$

- $m \cdot \text{global, label}_2 \in L_2$.

- $m \cdot \text{global, ancestor-msg} \in \Sigma_1$.

These messages make $C_2$ self-describing by completing the information available in layer 1 and used in lemma 33. A message $m_2$ output by a gate $g_2$ in $\kappa_2(p)$ identifies $p$ through $m_2 \cdot \text{parent-label}_2$ if $g_2$ is not the input gate of $\kappa_2(p)$, as in lemma 33. The global part $m_2 \cdot \text{global, identifies some ancestor of } g_2$, on layer 1 through $m \cdot \text{global, ancestor-msg}$ and on layer 2 through $m \cdot \text{global, label}_2$. This global information will enable the determination of the entry gate of each meta-gate, on both layers. From two messages $m_l, m_g \in \Sigma_1 \times \Sigma_2$ can be extracted by reading the local information from $m_l$, and the global information from $m_g$, as follows:

$$ \left\{ \begin{array}{l} m_1 = m_l \cdot \text{global, ancestor-msg} \\ m_2 \cdot \text{parent-label}_2 = m_l \cdot \text{global, label}_2 \\ m_2 \cdot \text{global} = m_g \cdot \text{global.} \end{array} \right. $$

The converse operation, embedding, takes as input three messages, a payload $(p_1, p_2) \in (\Sigma_1 \times \Sigma_2)$ and a context $c \in \Sigma_2$, and yields two messages $m_l$ and $m_g$

$$ \left\{ \begin{array}{l} m_l \cdot \text{parent-label}_2 = m_g \cdot \text{parent-label}_2 = c \cdot \text{parent-label}_2 \\ m_l \cdot \text{global, label}_2 = p_2 \cdot \text{parent-label}_2. \\ m_l \cdot \text{global, ancestor-msg} = p_1 \\ m_g \cdot \text{global} = p_2 \cdot \text{global.} \end{array} \right. $$

Extracting and embedding are dual operations, in the sense that

$$ \forall c, p_1, p_2, \text{extract } \circ \text{embed}(c, p_1, p_2) = (p_1, p_2). $$

## The substitution $\kappa_2$

Given a wiring $w$ and a label $l \in L_2$, the substitution $\kappa_2$ yields a label for each position in $K$;

- $s_2$ for the seed gate, i.e. for position $(0, 0)$ if $w$ has no inputs;

- $\partial\mathcal{L}$ for the gate receiving the input number 0 of the meta-gate;

- $\partial\mathfrak{A}$ for the gate receiving the input number 1 of the meta-gate whenever $l = \partial\mathcal{L}$;

- when $w$ has two inputs, there is a special position within the meta-gate where the value depends on $l$ as follows:

- $i_2$ if $l \in \{i_2, \partial\mathcal{L}\}$,

- $\partial\mathfrak{A}$ if $l = \partial\mathfrak{A}$;

- otherwise, $i_1$ for gates with one input and $i_2$ for gates with two inputs.

The special position is marked on figures 9 and 10 by a star.
of $\kappa_2$. Thus $\kappa_2$ shall not directly manipulate the gates or their function, lest the definition of layer 2 becomes cyclical and possibly ill-founded.

The set of layer 2 labels is $L_2 = \{s, i_1, i_2, \partial\mathcal{L}, \partial\mathfrak{A}\}$.

## Layer 2 messages

A message on layer 2 is an element of $\Sigma_2$; it is built from:

- $m \cdot \text{parent-label}_2 \in L_2$,

- $m \cdot \text{global, itself consisting of:}$

- $m \cdot \text{global, label}_2 \in L_2$.

- $m \cdot \text{global, ancestor-msg} \in \Sigma_1$.

These messages make $C_2$ self-describing by completing the information available in layer 1 and used in lemma 33. A message $m_2$ output by a gate $g_2$ in $\kappa_2(p)$ identifies $p$ through $m_2 \cdot \text{parent-label}_2$ if $g_2$ is not the input gate of $\kappa_2(p)$, as in lemma 33. The global part $m_2 \cdot \text{global, identifies some ancestor of } g_2$, on layer 1 through $m \cdot \text{global, ancestor-msg}$ and on layer 2 through $m \cdot \text{global, label}_2$. This global information will enable the determination of the entry gate of each meta-gate, on both layers. From two messages $m_l, m_g \in \Sigma_1 \times \Sigma_2$ can be extracted by reading the local information from $m_l$, and the global information from $m_g$, as follows:

$$ \left\{ \begin{array}{l} m_1 = m_l \cdot \text{global, ancestor-msg} \\ m_2 \cdot \text{parent-label}_2 = m_l \cdot \text{global, label}_2 \\ m_2 \cdot \text{global} = m_g \cdot \text{global.} \end{array} \right. $$

The converse operation, embedding, takes as input three messages, a payload $(p_1, p_2) \in (\Sigma_1 \times \Sigma_2)$ and a context $c \in \Sigma_2$, and yields two messages $m_l$ and $m_g$

$$ \left\{ \begin{array}{l} m_l \cdot \text{parent-label}_2 = m_g \cdot \text{parent-label}_2 = c \cdot \text{parent-label}_2 \\ m_l \cdot \text{global, label}_2 = p_2 \cdot \text{parent-label}_2. \\ m_l \cdot \text{global, ancestor-msg} = p_1 \\ m_g \cdot \text{global} = p_2 \cdot \text{global.} \end{array} \right. $$

Extracting and embedding are dual operations, in the sense that

$$ \forall c, p_1, p_2, \text{extract } \circ \text{embed}(c, p_1, p_2) = (p_1, p_2). $$

## The substitution $\kappa_2$

Given a wiring $w$ and a label $l \in L_2$, the substitution $\kappa_2$ yields a label for each position in $K$;

- $s_2$ for the seed gate, i.e. for position $(0,0)$ if $w$ has no inputs;

- $\partial\mathcal{L}$ for the gate receiving the input number 0 of the meta-gate;

- $\partial\mathfrak{A}$ for the gate receiving the input number 1 of the meta-gate whenever $l = \partial\mathcal{L}$;

- when $w$ has two inputs, there is a special position within the meta-gate where the value depends on $l$ as follows:

- $i_2$ if $l \in \{i_2, \partial\mathcal{L}\}$,

- $\partial\mathfrak{A}$ if $l = \partial\mathfrak{A}$;

- otherwise, $i_1$ for gates with one input and $i_2$ for gates with two inputs.

The special position is marked on figures 9 and 10 by a star.
## The layer-2 seed gate

The function $f_s^2 = \text{enumerate}_2(s_w, \mathfrak{s}_2, s_w, \mathfrak{s}_2)$ of the seed gate is a constant function with value $f_s^2() = \{\text{parent-label}_2 : \mathfrak{s}_2, \text{global} : \{\text{label}_2 : \mathfrak{s}_2, \text{ancestor-msg} : f_s^1()\}\}$. Recall that $f_s^1()$ is the message output by the seed gate on layer 1.

## Gate functions for layer 2

The functions of the gates depend on their label and on the direction $D$ of their first input, as dictated by the function instantiate:

$$ \left\{ \begin{array}{l} \text{enumerate}(D, \mathfrak{s}) = f_s^2 \\ \text{enumerate}(D, \mathfrak{i1}) : x \mapsto x \\ \text{enumerate}(D, \mathfrak{i2}) : (x, y) \mapsto (x, y) \\ \text{enumerate}(D, \mathfrak{dL}) = \text{decode}_L[D] \circ \text{incr}_G[D] \\ \text{enumerate}(D, \mathfrak{dA}) = (m_l, m_g) \mapsto \text{decode}_A[D](\text{incr}_G[D](m_l), m_g), \end{array} \right. $$

where $D$ is the direction of the first input of $w_p$.

The gate with labels $\mathfrak{i1}$ or $\mathfrak{i2}$ are wires; their function is the identity function of arity 1 or 2 respectively.

Given $m \in \Sigma_2$, the increment functions $\text{incr}_G[D]$ increments ancestor-msg global $m$-pos by the unit vector of direction $D$.

The two decoding functions $\text{decode}_L$ and $\text{decode}_A$ are based on the function decode : $\{N, E, S, W\} \times \Sigma_1 \times \Sigma_2 \to \Sigma_1 \times \Sigma_2$ defined as follows: let $m_1 \in \Sigma_1, m_2 \in \Sigma_2$, pose $z = m_1$-pos, $z_a = m_2$-global-ancestor-msg-pos, $a = m_2$-global-ancestor-msg. Let $l_p = \kappa_2(a$-parent-wiring, $a$-parent-label, $m_2$-global-label$_2, p')$ if $z \in K_1$, and $\mathfrak{dL}$ otherwise. Then decode$_D[D](m_1, m_2)$ is the pair $(m'_1, m'_2)$ with:

$$ m'_1 = \left\{ \begin{array}{l} \text{pos} : z \bmod K \\ \text{parent-wiring} : \text{dec-gate}_w(a, D) \\ \text{parent-label} : \text{dec-gate}_l(a, D) \end{array} \right\} $$

$$ m'_2 = \left\{ \begin{array}{l} \text{parent-label}_2 : p \\ \text{global-label}_2 : \text{global } m \cdot \text{label}_2 \\ \text{global-ancestor-msg} : \left\{ \begin{array}{l} \text{parent-wiring} : m \cdot \text{global-ancestor-msg} \cdot \text{parent-wiring} \\ \text{parent-label} : m \cdot \text{global-ancestor-msg} \cdot \text{parent-label} \\ \text{pos} : z_a \bmod K_1 \end{array} \right\} \end{array} \right\} $$

For a direction $D$ and a message $m_2 \in \Sigma_2$, take an arbitrary $m_1 \in \Sigma_1$ and let $(m'_1, m'_2) = \text{decode}_D[D](m_1, m_2)$; the value of $m'_2$ does not depend on $m_1$, so $\text{decode}_L[D](m_2)$ is defined to be the $m'_2 \in \Sigma$ returned by $\text{decode}(m_1, m_2)$ for any $m_1$.

For a direction $D$ and $m_l, m_g \in \Sigma_2$, $\text{decode}_A[D](m_l, m_g)$ is defined as follows. Let $(m_1, m_2) = \text{extract}(m_l, m_g)$, $(m'_1, m'_2) = \text{decode}_D[D](m_1, m_2)$. Then $\text{decode}_A[D](m_l, m_g)$ is the pair $m'_l, m'_g$ with:

$$ \left\{ \begin{array}{l} m'_l \cdot \text{parent-label}_2 = m'_g \cdot \text{parent-label}_2 = m_l \cdot \text{parent-label}_2 \\ m'_l \cdot \text{global-ancestor-msg} = m'_1 \\ m'_l \cdot \text{global-label}_2 = m'_g \cdot \text{parent-label}_2 \\ \text{global } m'_g = m' \cdot \text{global} \end{array} \right. $$

The function $\text{decode}_A$ is engineered in order to enjoy the following property, a kind of commutation between decode and extract.
## The layer-2 seed gate

The function $f_s^2 = \text{enumerate}_2(s_w, \mathfrak{s}_2, s_w, \mathfrak{s}_2)$ of the seed gate is a constant function with value $f_s^2() = \{ \text{parent-label}_2 : \mathfrak{s}_2, \text{global} : \{ \text{label}_2 : \mathfrak{s}_2, \text{ancestor-msg} : f_s^1() \} \}$. Recall that $f_s^1()$ is the message output by the seed gate on layer 1.

## Gate functions for layer 2

The functions of the gates depend on their label and on the direction $D$ of their first input, as dictated by the function instantiate:

$$ 
\left\{ 
\begin{array}{l} 
\text{instantiate}(D, \mathfrak{s}) = f_s^2 \\ 
\text{instantiate}(D, \mathfrak{i1}) : x \mapsto x \\ 
\text{instantiate}(D, \mathfrak{i2}) : (x, y) \mapsto (x, y) \\ 
\text{instantiate}(D, \mathfrak{dL}) = \text{decode}_L[D] \circ \text{incr}_G[D] \\ 
\text{instantiate}(D, \mathfrak{dA}) = (m_l, m_g) \mapsto \text{decode}_A[D](\text{incr}_G[D](m_l), m_g), 
\end{array} 
\right. 
$$

where $D$ is the direction of the first input of $w_p$.

The gate with labels $\mathfrak{i1}$ or $\mathfrak{i2}$ are wires; their function is the identity function of arity 1 or 2 respectively.

Given $m \in \Sigma_2$, the increment functions $\text{incr}_G[D]$ increments ancestor-msg global $m$-pos by the unit vector of direction $D$.

The two decoding functions $\text{decode}_L$ and $\text{decode}_A$ are based on the function decode : $\{N, E, S, W\} \times \Sigma_1 \times \Sigma_2 \to \Sigma_1 \times \Sigma_2$ defined as follows: let $m_1 \in \Sigma_1, m_2 \in \Sigma_2$, pose $z = m_1$-pos, $z_a = m_2$-global-ancestor-msg-pos, $a = m_2$-global-ancestor-msg. Let $l_p = \kappa_2(a$-parent-wiring, $a$-parent-label, $m_2$-global-label$_2, p')$ if $z \in K_1$, and $\mathfrak{dL}$ otherwise. Then decode$_L[D](m_1, m_2)$ is the pair $(m'_1, m'_2)$ with:

$$ m'_1 = \left\{ \begin{array}{l} \text{pos} : z \bmod K \\ \text{parent-wiring} : \text{dec-gate}_w(a, D) \\ \text{parent-label} : \text{dec-gate}_l(a, D) \end{array} \right\} $$

$$ m'_2 = \left\{ \begin{array}{l} \text{parent-label}_2 : p \\ \text{global-label}_2 : \text{global} \cdot \text{label}_2 \\ \text{global-ancestor-msg} : \left\{ \begin{array}{l} \text{parent-wiring} : m \cdot \text{global-ancestor-msg} \cdot \text{parent-wiring} \\ \text{parent-label} : m \cdot \text{global-ancestor-msg} \cdot \text{parent-label} \\ \text{pos} : z_a \bmod K_1 \end{array} \right\} \end{array} \right\} $$

For a direction $D$ and a message $m_2 \in \Sigma_2$, take an arbitrary $m_1 \in \Sigma_1$ and let $(m'_1, m'_2) = \text{decode}[D](m_1, m_2)$; the value of $m'_2$ does not depend on $m_1$, so $\text{decode}_L[D](m_2)$ is defined to be the $m'_2 \in \Sigma$ returned by $\text{decode}(m_1, m_2)$ for any $m_1$.

For a direction $D$ and $m_l, m_g \in \Sigma_2$, $\text{decode}_A[D](m_l, m_g)$ is defined as follows. Let $(m_1, m_2) = \text{extract}(m_l, m_g)$, $(m'_1, m'_2) = \text{decode}[D](m_1, m_2)$. Then $\text{decode}_A[D](m_l, m_g)$ is the pair $m'_l, m'_g$ with:

$$ 
\left\{ 
\begin{array}{l} 
m'_l \cdot \text{parent-label}_2 = m'_g \cdot \text{parent-label}_2 = m_l \cdot \text{parent-label}_2 \\ 
m'_l \cdot \text{global-ancestor-msg} = m'_1 \\ 
m'_l \cdot \text{global-label}_2 = m'_g \cdot \text{parent-label}_2 \\ 
\text{global} \cdot m'_g = m' \cdot \text{global} 
\end{array} 
\right. 
$$

The function $\text{decode}_A$ is engineered in order to enjoy the following property, a kind of commutation between decode and extract.
**Lemma 35.** For any direction $D \in \{N, E, S, W\}$,

$$ \text{decode}[D] \circ \text{extract} = \text{extract} \circ \text{decode}_A[D] $$

**Proof.** By computation.

<figure><img src="image_15.png" /></figure>

## Properties of $C_2$

The messages passing through the circuit $C_2$ built above hold all the necessary information for $C_\square$ to be self-describing: in other words, $C_2$ carries all the information needed to determine the entry gate of each meta-gate in $C_1$, as well as the information needed to determine each of its gates.

The global ancestor msg part of the messages on input 0 each meta-gate simulate the gates of layer 1, as long as each meta-gate simulating a gate with label input receives on input 1 the message of its parent meta-gate.

**Lemma 36.** Let $w \in W$ with $k$ inputs, $l_2 \in L_2$, and $M$ be the circuit $\mu_2(w, l_2)$. Note that $M$ has $2k$ inputs. Let $D$ be the direction of the first input of $w$.

Let $\vec{\iota} \in \Sigma^{2k}$, and let $\vec{\sigma}$ be the output of $M$ on input $\vec{\iota}$. Pose $i_a = i_0$ ancestor-msg global and $i_p = i_1$ ancestor-msg global.

Then, if $g_1 = \text{dec-gate}(i_a, D) \neq \perp$, then $o_0$ is the output of $g_1$ on input $i_a$; else, if $\text{dec-gate}(i_a, D) = \perp$, then $o_0$ is the output of $\text{dec-gate}_c(i_p, D)(i_a \cdot \text{pos})$ on input $i_a$.

**Proof.** By computation.

<figure><img src="image_16.png" /></figure>

The rest of the global part of the messages allows $C_2$ to simulate itself.

**Lemma 37.** Let $D \in \{N, E, S, W\}$, $w \in W$ with one input in direction $D$, $l_2 \in L_2$. Let $f = \text{enumerate}(D, l_2)$ and $C = \mu_2(w, l_2)$.

Let $c \in \Sigma_1, i_1 \in \Sigma_1, i_2 \in \Sigma_2$ and $(m_l, m_g) = \text{embed}(c, i_1, i_2)$. Let $(o_0, o_1)$ be the outputs of $C$ on input $(m_l, m_g)$. Then $\text{extract}(o_0, o_1) = f(i_2)$.

**Proof.** The proof proceeds by case on $l_2$, which can be either $i_1$ or $\mathfrak{d}\mathfrak{L}$. If $l_2 = i_1$, then $f$ is the identity function, and it suffices to follow the wirings to check the result.

If $l_2 = \mathfrak{d}\mathfrak{L}$, then following the wirings reduces the desired equality to the definition of $\text{decode}_L[D]$.

<figure><img src="image_17.png" /></figure>

**Lemma 38.** Let $w \in W$ with two inputs, $l_2 \in L_2$. Let $f = \text{enumerate}(l_2)$ and $C = \mu_2(w, l_2)$.

For $k \in \{0, 1\}$, let $c^k \in \Sigma_1, i_1^k \in \Sigma_1, i_2^k \in \Sigma_2$ and $(m_l^k, m_g) = \text{embed}(c^k, i_1^k, i_2^k)$. Let $(o_0^0, o_1^0, o_0^1, o_1^1)$ be the outputs of $C$ on input $(m_l^0, m_g^0, m_l^1, m_g^1)$. Then for $k \in \{0, 1\}$ extract $(o_0^k, o_1^k)$ is the $k$-th component of $f(i_2^0, i_2^1)$.

**Proof.** The proof proceeds by case on $l_2$. If $l_2 \in \{\mathfrak{s}, i_2, \mathfrak{d}\mathfrak{L}\}$, following the wirings in $\kappa_2(w, l_1, l_2)$ confirms that the lemma holds.

If $l_2 = \mathfrak{d}\mathfrak{L}$, the lemma follows from lemma 35 by again following the wirings.

<figure><img src="image_18.png" /></figure>

Together, these properties entail a substitutive structure of the messages in $C_\square$. Going up the hierarchy, the message between two gates of $C_\square$ can be extracted from the messages between the corresponding meta-gates.
**Lemma 35.** For any direction $D \in \{N, E, S, W\}$,

$$ \text{decode}[D] \circ \text{extract} = \text{extract} \circ \text{decode}_A[D] $$

**Proof.** By computation.

<figure><img src="image_14.png" /></figure>

## Properties of $C_2$

The messages passing through the circuit $C_2$ built above hold all the necessary information for $C_\square$ to be self-describing: in other words, $C_2$ carries all the information needed to determine the entry gate of each meta-gate in $C_1$, as well as the information needed to determine each of its gates.

The global ancestor msg part of the messages on input 0 each meta-gate simulate the gates of layer 1, as long as each meta-gate simulating a gate with label input receives on input 1 the message of its parent meta-gate.

**Lemma 36.** Let $w \in W$ with $k$ inputs, $l_2 \in L_2$, and $M$ be the circuit $\mu_2(w, l_2)$. Note that $M$ has $2k$ inputs. Let $D$ be the direction of the first input of $w$.

Let $\vec{\iota} \in \Sigma^{2k}$, and let $\vec{\sigma}$ be the output of $M$ on input $\vec{\iota}$. Pose $i_a = i_0$ ancestor-msg global and $i_p = i_1$ ancestor-msg global.

Then, if $g_1 = \text{dec-gate}(i_a, D) \neq \perp$, then $o_0$ is the output of $g_1$ on input $i_a$; else, if $\text{dec-gate}(i_a, D) = \perp$, then $o_0$ is the output of $\text{dec-gate}_c(i_p, D)(i_a \cdot \text{pos})$ on input $i_a$.

**Proof.** By computation.

<figure><img src="image_15.png" /></figure>

The rest of the global part of the messages allows $C_2$ to simulate itself.

**Lemma 37.** Let $D \in \{N, E, S, W\}$, $w \in W$ with one input in direction $D$, $l_2 \in L_2$. Let $f = \text{enumerate}(D, l_2)$ and $C = \mu_2(w, l_2)$.

Let $c \in \Sigma_1, i_1 \in \Sigma_1, i_2 \in \Sigma_2$ and $(m_l, m_g) = \text{embed}(c, i_1, i_2)$. Let $(o_0, o_1)$ be the outputs of $C$ on input $(m_l, m_g)$. Then $\text{extract}(o_0, o_1) = f(i_2)$.

**Proof.** The proof proceeds by case on $l_2$, which can be either $i_1$ or $\mathfrak{d}\mathfrak{L}$. If $l_2 = i_1$, then $f$ is the identity function, and it suffices to follow the wirings to check the result.

If $l_2 = \mathfrak{d}\mathfrak{L}$, then following the wirings reduces the desired equality to the definition of $\text{decode}_L[D]$.

<figure><img src="image_16.png" /></figure>

**Lemma 38.** Let $w \in W$ with two inputs, $l_2 \in L_2$. Let $f = \text{enumerate}(l_2)$ and $C = \mu_2(w, l_2)$.

For $k \in \{0, 1\}$, let $c^k \in \Sigma_1, i_1^k \in \Sigma_1, i_2^k \in \Sigma_2$ and $(m_l^k, m_g) = \text{embed}(c^k, i_1^k, i_2^k)$. Let $(o_0^0, o_1^0, o_0^1, o_1^1)$ be the outputs of $C$ on input $(m_l^0, m_g^0, m_l^1, m_g^1)$. Then for $k \in \{0, 1\}$ extract $(o_0^k, o_1^k)$ is the $k$-th component of $f(i_2^0, i_2^1)$.

**Proof.** The proof proceeds by case on $l_2$. If $l_2 \in \{\mathfrak{s}, i_2, \mathfrak{d}\mathfrak{L}\}$, following the wirings in $\kappa_2(w, l_1, l_2)$ confirms that the lemma holds.

If $l_2 = \mathfrak{d}\mathfrak{L}$, the lemma follows from lemma 35 by again following the wirings.

<figure><img src="image_17.png" /></figure>

Together, these properties entail a substitutive structure of the messages in $C_\square$. Going up the hierarchy, the message between two gates of $C_\square$ can be extracted from the messages between the corresponding meta-gates.
**Lemma 39.** Let $a = p \to p'$ be a wire between two positions $p, p'$ of $K^\infty$ in direction $D$. Let $a_l, a_g$ be the two wires crossing the edges between $pK$ and $p'K$ in clockwise order looking in direction $D$ (i.e., if $D$ is $E$, $a_l$ is the northernmost of the two; if $D$ is $S$, the westernmost...).

$$ \text{Let } m = \tilde{C}_{\square}(a), l = (l_1, l_2) = \tilde{C}_{\square}(a_l) \text{ and } g = (g_1, g_2) = \tilde{C}_{\square}(a_g). $$

$$ \text{Then } \text{extract}(l_2, g_2) = m. $$

*Proof.* By induction on $p$, following the wires of $C_{\square}$.

<figure><img src="image_19.png" /></figure>

**Lemma 40.** Let $\vec{p} \in K^\infty$. Let $g_1 = C_1(\vec{p})$, $g_2 = C_2(\vec{p})$, $g'_1 = C_1(\lfloor \vec{p} \rfloor)$, $g'_2 = C_2(\lfloor \vec{p} \rfloor)$. Let $g = g_1 \otimes g_2 = C_{\square}(\vec{p})$, and $g' = g'_1 \otimes g'_2 = C_{\square}(\lfloor \vec{p} \rfloor)$. Let $e$ be an output wire of $g$, and $m_1 \times m_2 = \tilde{C}_{\square}(e)$ its value in $C_{\square}$.

Then $m_2 \cdot \text{parent-label}_2$ is the label of $g'_2$, $m_1 \cdot \text{parent-label}_1$ is the label of $g'_1$, $m_1 \cdot \text{parent-wiring}$ is $g' \cdot \text{wiring}$, and $m_1 \cdot \text{pos}$ is $\vec{p} \bmod K$.

*Proof.* By the previous lemma, input 0 of each meta-gate $\mu_1(l_1, w) \otimes \mu_2(l_2, w)$ encodes $l_1, l_2$ and $w$. The gate after that input has label $\mathfrak{DL}$, so by definition of its function $\text{decode}_L$, its output satisfies the lemma. The other gates in the meta-gate preserve the local part of the messages.

<figure><img src="image_20.png" /></figure>

This local information is just what is needed to reconstruct each gate from its output, which is just short of self-description.

**Corollary 41.** There are is a function $\text{dec-gate}' : \Sigma_1 \times \Sigma_2 \to W \times L_1 \times L_2 \times K$ such that for any position $p \in K^\infty$ and any wire $a : p \to p'$ of $C_{\square}$,

$$ \text{dec-gate}'(\tilde{C}_{\square}(a)) = (\Lambda_1(\lfloor p/K \rfloor), \Lambda_2(\lfloor p/K \rfloor), C_w(\lfloor p/K \rfloor), p \bmod K). $$

With a tiny bit of extra work, each gate $g$ can be reconstructed from its input number 0, making $C_{\square}$ self-descriptive.

**Theorem 42.** The circuit $C_{\square}$ is self-descriptive.

*Proof.* Each gate $g$ in position $p$ can be reconstructed from its set of input directions and the message on its input number 0.

If $g$ has no inputs, then $g = s_1 \otimes s_2$.

Otherwise, let $D$ be the direction of its first input wire, and $m = (m_1, m_2)$ the message coming into its first wire.

Let $(w, l_1, l_2, p') = \text{dec-gate}'(m)$. Note that $p' = (p - D) \bmod K$. If $p' + D$ belongs to $K$, then $\lfloor \frac{p}{K} \rfloor = \lfloor \frac{p-D}{K} \rfloor$, so $p$ belongs to the same meta-gate as its predecessor $p - D$, hence $C_{\square}(p)$ is $\mu_1(w, l_1)(p' + D) \otimes \mu_2(w, l_2)(p' + D)$.

Otherwise, since $p' + D \notin K$, it must be the case that $\lfloor \frac{p}{K} \rfloor = \lfloor \frac{p-D}{K} \rfloor + D$: $p$ and its predecessor $p - D$ are in neighboring meta-gates. Let $a = \lfloor \frac{p}{K} \rfloor$ be the position of the parent gate. The position $a \bmod k$ of $a$ within its meta-gate is the position where input 0 enters that meta-gate.

A close examination of the values of $\mu_1(w, l_1)$ and $\mu_2(w, l_2)$ for all $w, l_1, l_2$ reveals that in each (non-seed) meta-gate the label and wiring of the gate in the position where input 0 comes only depends on the input directions of $w$. By lemma 40, those directions are exactly those of $m_2 \cdot \text{global} \cdot \text{ancestor}-\text{msg} \cdot \text{parent-wiring} \cdot \text{outwires}(D)$.

<figure><img src="image_21.png" /></figure>

This concludes the proof of Theorem 15. By theorem 28, this means that there is an aTAM system $S_{\square}$ which strictly self-assembles $K^\infty$.
**Lemma 39.** Let $a = p \to p'$ be a wire between two positions $p, p'$ of $K^\infty$ in direction D. Let $a_l, a_g$ be the two wires crossing the edges between $pK$ and $p'K$ in clockwise order looking in direction D (i.e., if D is E, $a_l$ is the northernmost of the two; if D is S, the westernmost...).

$$ \text{Let } m = \tilde{C}_{\square}(a), l = (l_1, l_2) = \tilde{C}_{\square}(a_l) \text{ and } g = (g_1, g_2) = \tilde{C}_{\square}(a_g). $$

$$ \text{Then } \text{extract}(l_2, g_2) = m. $$

**Proof.** By induction on $p$, following the wires of $C_{\square}$.

<figure><img src="image_18.png" /></figure>

**Lemma 40.** Let $\vec{p} \in K^\infty$. Let $g_1 = C_1(\vec{p})$, $g_2 = C_2(\vec{p})$, $g'_1 = C_1(\lfloor \vec{p} \rfloor)$, $g'_2 = C_2(\lfloor \vec{p} \rfloor)$. Let $g = g_1 \otimes g_2 = C_{\square}(\vec{p})$, and $g' = g'_1 \otimes g'_2 = C_{\square}(\lfloor \vec{p} \rfloor)$. Let $e$ be an output wire of $g$, and $m_1 \times m_2 = \tilde{C}_{\square}(e)$ its value in $C_{\square}$.

Then $m_2 \cdot \text{parent-label}_2$ is the label of $g'_2$, $m_1 \cdot \text{parent-label}_1$ is the label of $g'_1$, $m_1 \cdot \text{parent-wiring}$ is $g' \cdot \text{wiring}$, and $m_1 \cdot \text{pos}$ is $\vec{p} \bmod K$.

**Proof.** By the previous lemma, input 0 of each meta-gate $\mu_1(l_1, w) \otimes \mu_2(l_2, w)$ encodes $l_1, l_2$ and $w$. The gate after that input has label $\mathfrak{D}\mathfrak{L}$, so by definition of its function $\text{decode}_L$, its output satisfies the lemma. The other gates in the meta-gate preserve the local part of the messages.

<figure><img src="image_19.png" /></figure>

This local information is just what is needed to reconstruct each gate from its output, which is just short of self-description.

**Corollary 41.** There are is a function $\text{dec-gate}' : \Sigma_1 \times \Sigma_2 \to \mathcal{W} \times L_1 \times L_2 \times K$ such that for any position $p \in K^\infty$ and any wire $a : p \to p'$ of $C_{\square}$,

$$ \text{dec-gate}'(\tilde{C}_{\square}(a)) = (\Lambda_1(\lfloor p/K \rfloor), \Lambda_2(\lfloor p/K \rfloor), C_w(\lfloor p/K \rfloor), p \bmod K). $$

With a tiny bit of extra work, each gate $g$ can be reconstructed from its input number 0, making $C_{\square}$ self-descriptive.

**Theorem 42.** The circuit $C_{\square}$ is self-descriptive.

**Proof.** Each gate $g$ in position $p$ can be reconstructed from its set of input directions and the message on its input number 0.

If $g$ has no inputs, then $g = s_1 \otimes s_2$.

Otherwise, let $D$ be the direction of its first input wire, and $m = (m_1, m_2)$ the message coming into its first wire.

Let $(w, l_1, l_2, p') = \text{dec-gate}'(m)$. Note that $p' = (p - D) \bmod K$. If $p' + D$ belongs to $K$, then $\lfloor \frac{p}{K} \rfloor = \lfloor \frac{p-D}{K} \rfloor$, so $p$ belongs to the same meta-gate as its predecessor $p - D$, hence $C_{\square}(p)$ is $\mu_1(w, l_1)(p' + D) \otimes \mu_2(w, l_2)(p' + D)$.

Otherwise, since $p' + D \notin K$, it must be the case that $\lfloor \frac{p}{K} \rfloor = \lfloor \frac{p-D}{K} \rfloor + D$: $p$ and its predecessor $p - D$ are in neighboring meta-gates. Let $a = \lfloor \frac{p}{K} \rfloor$ be the position of the parent gate. The position $a \bmod k$ of $a$ within its meta-gate is the position where input 0 enters that meta-gate.

A close examination of the values of $\mu_1(w, l_1)$ and $\mu_2(w, l_2)$ for all $w, l_1, l_2$ reveals that in each (non-seed) meta-gate the label and wiring of the gate in the position where input 0 comes only depends on the input directions of $w$. By lemma 40, those directions are exactly those of $m_2 \cdot \text{global-ancestor}-\text{msg} \cdot \text{parent-wiring} \cdot \text{outwires}(D)$.

<figure><img src="image_20.png" /></figure>

This concludes the proof of Theorem 15. By theorem 28, this means that there is an aTAM system $S_{\square}$ which strictly self-assembles $K^\infty$.
<figure><img src="image_22.png" /><figcaption>Figure 11 A finite shape G, its grid neighborhood $G^+$ and its grid graph $G^\#$.</figcaption></figure>

## 5 A Characterization of Admissible Generators

The previous construction can be adapted to any self-similar discrete fractal within which the communication pattern used by $C_\square$ can be embedded. Whether a particular fractal is amenable to hosting such a communication pattern depends on the ability of its generator G to transport information to copies of itself around it.

**Definition 43.** Let G be a finite subset of $\mathbb{N}^2$, the grid $G^\#$ is the subset of $\mathbb{Z}^2$ defined by:

$$G^\# = \{ p \in \mathbb{Z}^2 | p \text{ mod } G \in G \}$$

The grid neighborhood graph $G^+$ of G is the subgraph of $G^\#$ induced by the distance 1 neighborhood of G:

$$G^+ = G \cup \{p \in G^\# | \exists d \in \{N, E, S, W\}, p + d \in G\}.$$

For a direction $d \in \{N, E, S, W\}$, the d-port in $G^+$ is $G^{+d} = \{p \in G^\# | p - d \in G\}$.

For $d, d' \in \{N, E, S, W\}$, the $(d, d')$-bandwidth of G is the number $G[d \leftrightarrow d']$ of vertex-disjoint paths from $G^{+d}$ to $G^{+d'}$ in $G^+$.

In order to compare generators, the classical notions of subgraph and graph subdivision is useful, accounting for marked vertices.

**Definition 44 (Pointed subgraph).** Let G, H be two graph, each with marked vertices. The graph H is a pointed subgraph of G if H is a subgraph of G in such a way that any marked vertex of H is mapped to a marked vertex of G. The graph G may have extra marked vertices.

**Definition 45 (Edge subdivision).** Let $G = (V, E)$ be a graph, with some marked vertices $(v_0, \dots, v_{k-1}) \in V^k$. The edge subdivision operation for an edge $e = \{u, v\} \in E$ is the deletion of $e$ from G and the addition of a new vertex $w \notin V$ and of the edges $\{u, w\}$ and $\{w, v\}$.

This operation generates a new graph H, where the same vertices are marked as in G.

$$H = (V \cup \{w\}, (E \setminus \{u, v\}) \cap \{\{u, w\}, \{w, v\}\})$$
<figure><img src="image_21.png" /><figcaption>Figure 11 A finite shape G, its grid neighborhood G⁺ and its grid graph G#.</figcaption></figure>

5 A Characterization of Admissible Generators

The previous construction can be adapted to any self-similar discrete fractal within which
the communication pattern used by C□ can be embedded. Whether a particular fractal is
amenable to hosting such a communication pattern depends on the ability of its generator G
to transport information to copies of itself around it.

► **Definition 43.** Let G be a finite subset of $\mathbb{N}^2$, the grid $G^\#$ is the subset of $\mathbb{Z}^2$ defined by:

$$
G^{\#} = \{ p \in \mathbb{Z}^2 | p \bmod G \in G \}
$$

The grid neighborhood graph G⁺ of G is the subgraph of G# induced by the distance 1 neighborhood of G:

$$
G^+ = G \cup \{p \in G^# \mid \exists d \in \{N, E, S, W\}, p + d \in G\}.
$$

For a direction $d \in \{N, E, S, W\}$, the $d$-port in $G^+$ is $G^{+d} = \{p \in G^# | p - d \in G\}$.

For $d, d' \in \{N, E, S, W\}$, the $(d, d')$-bandwidth of $G$ is the number $G[d \leftrightarrow d']$ of vertex-disjoint paths from $G^{+d}$ to $G^{+d'}$ in $G^+$.

In order to compare generators, the classical notions of *subgraph* and *graph subdivision* is
useful, accounting for marked vertices.

**Definition 44 (Pointed subgraph).** Let $G, H$ be two graph, each with marked vertices. The graph $H$ is a pointed subgraph of $G$ if $H$ is a subgraph of $G$ in such a way that any marked vertex of $H$ is mapped to a marked vertex of $G$. The graph $G$ may have extra marked vertices.

**Definition 45 (Edge subdivision).** Let $G = (V, E)$ be a graph, with some marked vertices $(v_0, \dots, v_{k-1}) \in V^k$. The edge subdivision operation for an edge $e = \{u, v\} \in E$ is the deletion of $e$ from $G$ and the addition of a new vertex $w \notin V$ and of the edges $\{u, w\}$ and $\{w, v\}$.

This operation generates a new graph $H$, where the same vertices are marked as in $G$.

$$
H = (V \cup \{w\}, (E \setminus \{u, v\}) \cap \{\{u, w\}, \{w, v\}\})
$$
<figure><img src="image_23.png" /><figcaption>Figure 12 The value of $\kappa_w(w)$ when $w$. Inputs = {$E, W$}. This case is not needed in section 4, but it is necessary to generalize $\kappa_w$ to $G$ when $K^+$ is a subdivision of $G^+$. No position needs to be provisionned for $\partial A$, since both inputs must be in the same metagate.</figcaption></figure>

**Definition 46 (Graph Subdivision).** A graph with marked vertices which has been derived from $G$ by a sequence of edge subdivision operations is called a pointed subdivision of $G$.

**Definition 47 (Subconnector).** Let $G, H$ be finite, connected shapes of $\mathbb{N}^2$, with $(0,0) \in G \cap H$.

Then $H$ is a subconnector of $G$, written $H \preceq G$ if $G^+$ has a (pointed) subgraph which is a (pointed) subdivision of $H^+$.

The notion of subconnector is well-suited to the study of substitutions given the following properties.

**Remark 48.** Let $G, H, I$ be finite, connected shapes of $\mathbb{N}^2$, with $G \preceq H$, then:

$$ \sigma_I(G) \preceq \sigma_I(H) $$

$$ \sigma_G(I) \preceq \sigma_H(I) $$

**Lemma 49.** Let $G \ni (0,0)$ a finite, connected subgraph of $\mathbb{N}^2$ such that $K \preceq G$. Then there is a self-descriptive circuit with domain $G^\infty$.

**Proof.** First, notice that $\kappa_w$ can be completed to cover the case where $w$ has two opposite input directions, as represented on figure 12 (modulo rotation and reflection).

Fix the vertices of $G^+$ which represent the vertices of $K^+$, the ones that sit in the middle of its edges, and the ones which are pending leaves.

Then it is possible to define a substitution $\gamma_w : W \to W^G$ by using $\kappa_w$ to fix a subdivision of $G^+$, then adding the extra vertices to $\gamma_w(w)$. This process may create vertices in $\gamma_w(w)$ with two opposite inputs, for which the extra cases of figure 12 are necessary.

The label substitutions $\kappa_1$ and $\kappa_2$ can also be adapted to $G^+$, defining $\gamma_1$ and $\gamma_2$. In $\gamma_1$, all vertices which do not represent a vertex of $K$ have label normal. For layer 2, each vertex of $G^+$ representing a vertex of $K$ keeps its label, each new vertex gets a label $i_1$.
<figure><img src="image_22.png" /><figcaption>Figure 12 The value of $\kappa_w(w)$ when $w$. Inputs = {$E, W$}. This case is not needed in section 4, but it is necessary to generalize $\kappa_w$ to $G$ when $K^+$ is a subdivision of $G^+$. No position needs to be provisionned for $\partial A$, since both inputs must be in the same metagate.</figcaption></figure>

**Definition 46 (Graph Subdivision).** A graph with marked vertices which has been derived from $G$ by a sequence of edge subdivision operations is called a pointed subdivision of $G$.

**Definition 47 (Subconnector).** Let $G, H$ be finite, connected shapes of $\mathbb{N}^2$, with $(0,0) \in G \cap H$.

Then $H$ is a subconnector of $G$, written $H \preceq G$ if $G^+$ has a (pointed) subgraph which is a (pointed) subdivision of $H^+$.

The notion of subconnector is well-suited to the study of substitutions given the following properties.

**Remark 48.** Let $G, H, I$ be finite, connected shapes of $\mathbb{N}^2$, with $G \preceq H$, then:

$$ \sigma_I(G) \preceq \sigma_I(H) $$

$$ \sigma_G(I) \preceq \sigma_H(I) $$

**Lemma 49.** Let $G \ni (0,0)$ a finite, connected subgraph of $\mathbb{N}^2$ such that $K \preceq G$. Then there is a self-descriptive circuit with domain $G^\infty$.

**Proof.** First, notice that $\kappa_w$ can be completed to cover the case where $w$ has two opposite input directions, as represented on figure 12 (modulo rotation and reflection).

Fix the vertices of $G^+$ which represent the vertices of $K^+$, the ones that sit in the middle of its edges, and the ones which are pending leaves.

Then it is possible to define a substitution $\gamma_w : W \to W^G$ by using $\kappa_w$ to fix a subdivision of $G^+$, then adding the extra vertices to $\gamma_w(w)$. This process may create vertices in $\gamma_w(w)$ with two opposite inputs, for which the extra cases of figure 12 are necessary.

The label substitutions $\kappa_1$ and $\kappa_2$ can also be adapted to $G^+$, defining $\gamma_1$ and $\gamma_2$. In $\gamma_1$, all vertices which do not represent a vertex of $K$ have label normal. For layer 2, each vertex of $G^+$ representing a vertex of $K$ keeps its label, each new vertex gets a label $i_1$.
<figure><img src="image_24.png" /><figcaption>■ **Figure 13** The second iteration $S$ of the Sierpinski Carpet (in the center) is a subconnector of $K$: $S^+$ contains a subdivision of $K^+$, in which the cells with a circle correspond to vertices of $K^+$, and those with a bar are obtained by dividing the edge of $K^+$ the bar represents. Not all edges are subdivided: adjacent circles in $G^+$ are indeed adjacent in $K^+$.</figcaption></figure>

Set $\Sigma_1^G = \Sigma_1$, except that pos takes values in $G$ rather than $K$. Then $\Sigma_2^G$ is $\Sigma_2$, except that ancestor msg takes values in $\Sigma_1^G$ rather than $\Sigma_1$.

Then a circuit $C_G$ on $\Sigma_1^G \times \Sigma_2^G$ can be defined from $\gamma_w, \gamma_1$ and $\gamma_2$ like $C_\square$. That circuit $C_G$ has the same properties as $C_\square$ and is also self-descriptive. When accounting for the local part of the messages, gates which are upstream from all the $K$-vertices show the local message of the corresponding input meta-gate.

Thus $C_G$ is self-descriptive.

<figure><img src="image_25.png" /></figure>

The question is now which $G$ are such that $G^+$ has a subdivision of $K^+$ as a subgraph. This condition seems constraining since $K$ is a rather large graph with its 32 vertices. Yet, one can make any $G$ larger by iterating the substitution generated by $G$ before trying to self-assemble $G^\infty$.

► **Remark 50.** Let $G \ni (0,0)$ be a finite shape of $\mathbb{N}^2$. For any $k > 0$, $G^\infty = (G^k)^\infty$.

By iterating $\sigma_G$, it is quite easy to get an instance of $K$ as a subconnector, as long as one starts with sufficient vertical and horizontal bandwidth.

► **Lemma 51.** Let $G \ni (0,0)$ be a finite shape of $\mathbb{N}^2$. If $G[N \leftrightarrow S] \ge 2$ and $G[E \to W] \ge 2$, then $K \subseteq G^3$

**Proof.** Let $H = \{0,1\}^2$. If $G[N \leftrightarrow S] \ge 2$ and $G[E \to W] \ge 2$, then $H \subseteq G$: pick two disjoint North-South paths, two disjoint East-West paths, their four intersections can act as the vertices of $H$.

By remark 48, since $H \subseteq G$, $H^3 \subseteq G^3$. But $H^3$ is an $8 \times 8$ grid, so $K \subseteq H^3$.

Hence, $K \subseteq G^3$.

<figure><img src="image_26.png" /></figure>

Finally, this characterization is tight, by a generalization of the impossibility result of Hendricks et al. [11].
<figure><img src="image_23.png" /><figcaption>■ **Figure 13** The second iteration $S$ of the Sierpinski Carpet (in the center) is a subconnector of $K$: $S^+$ contains a subdivision of $K^+$, in which the cells with a circle correspond to vertices of $K^+$, and those with a bar are obtained by dividing the edge of $K^+$ the bar represents. Not all edges are subdivided: adjacent circles in $G^+$ are indeed adjacent in $K^+$.</figcaption></figure>

Set $\Sigma_1^G = \Sigma_1$, except that pos takes values in $G$ rather than $K$. Then $\Sigma_2^G$ is $\Sigma_2$, except that ancestor msg takes values in $\Sigma_1^G$ rather than $\Sigma_1$.

Then a circuit $C_G$ on $\Sigma_1^G \times \Sigma_2^G$ can be defined from $\gamma_w, \gamma_1$ and $\gamma_2$ like $C_\square$. That circuit $C_G$ has the same properties as $C_\square$ and is also self-descriptive. When accounting for the local part of the messages, gates which are upstream from all the $K$-vertices show the local message of the corresponding input meta-gate.

Thus $C_G$ is self-descriptive.

<figure><img src="image_24.png" /></figure>

The question is now which $G$ are such that $G^+$ has a subdivision of $K^+$ as a subgraph. This condition seems constraining since $K$ is a rather large graph with its 32 vertices. Yet, one can make any $G$ larger by iterating the substitution generated by $G$ before trying to self-assemble $G^\infty$.

► **Remark 50.** Let $G \ni (0,0)$ be a finite shape of $\mathbb{N}^2$. For any $k > 0$, $G^\infty = (G^k)^\infty$.

By iterating $\sigma_G$, it is quite easy to get an instance of $K$ as a subconnector, as long as one starts with sufficient vertical and horizontal bandwidth.

► **Lemma 51.** Let $G \ni (0,0)$ be a finite shape of $\mathbb{N}^2$. If $G[N \leftrightarrow S] \ge 2$ and $G[E \to W] \ge 2$, then $K \subseteq G^3$

**Proof.** Let $H = \{0,1\}^2$. If $G[N \leftrightarrow S] \ge 2$ and $G[E \to W] \ge 2$, then $H \subseteq G$: pick two disjoint North-South paths, two disjoint East-West paths, their four intersections can act as the vertices of $H$.

By remark 48, since $H \subseteq G$, $H^3 \subseteq G^3$. But $H^3$ is an $8 \times 8$ grid, so $K \subseteq H^3$.

Hence, $K \subseteq G^3$.

<figure><img src="image_25.png" /></figure>

Finally, this characterization is tight, by a generalization of the impossibility result of Hendricks et al. [11].
<figure><img src="image_27.png" /><figcaption>■ **Figure 14** The set $C_k$ is the set of all glues which attach across the vertical lines at coordinate $x_k$. Ignoring any tiles which are not visible in the picture, $C_0 = C_1 = \{a \cdot E, b \cdot E, c \cdot E\}$, $C_2 = \{a \cdot E, b \cdot E\}$ and $C_3 = \{c \cdot E\}$. The tiles marked with a 1 are the ones which appear in their column in some production without other tiles right of the red line; the subset $F_k$ of $C_k$ contains their east glues: $F_0 = F_1 = \{a \cdot E, b \cdot E\}$, $C_2 = \{a \cdot E\}$ and $C_3 = \{c \cdot E\}$</figcaption></figure>

► **Theorem 52.** Let $G \ni (0,0)$ a finite shape of $\mathbb{N}$.

If for all $k > 0$, there is an $x_k$ such that there is only one $y$ with $(x_k, y) \in (G^k)^+$ and $(x_k, y + 1) \in (G^k)^+$, then $G^\infty$ cannot be strictly self-assembled in the aTAM model unless $G = \{\vec{0}\}$.

**Proof.** Let $w$ and $h$ be the width and height of $G$. Assume that there is an aTAM $G$ which self-assembles $G^\infty$ at temperature $\tau$.

Let $C_k$ be the set of all glues which appear on the eastern edge of position $(x_k, y)$ for some value of $y$. Since $G$ assembles $G^\infty$, all the $C_k$ are non-empty, so let $C_\infty = \bigcap_k (\bigcup_{k'>k} C_{k'})$ be the set of glues appearing in infinitely many $C_k$; $C_\infty$ is also non-empty. Let $F_k \subseteq C_k$ be the set of glues $g$ such that there is a position $\vec{z} = (x_k, y)$ and a production $\Pi_{k,t}$ of $G$ where:

- the eastern glue of $\Pi_{k,t}(\vec{z})$ is $g$

- $\Pi_{k,t}$ contains no tile right of $x_k$

Like $C_\infty$, $F_\infty = \bigcap_k (\bigcup_{k'>k} F_{k'})$ is non-empty. The sets $C_k$ and $F_k$ are illustrated on Figure 14.

Now let $t$ be a glue of $G$, and $s_t$ be a (new) tile with $t$ on its eastern side, and $\epsilon$ on all other sides. Let $G_t[x \ge 1]$ be the set of productions of $G$, starting from the seed configuration with $s_t$ at $\vec{0}$ and attaching no tiles at positions $x < 1$. Let $u_t = \min_{p \in G_t[x>1]} \max\{y|(x,y) \in p\}$ and $d_t = \min_{p \in G_t[x>1]} \min\{y|(x,y) \in p\}$. These two quantities are illustrated on Figure 15.

Since $G^\infty \subset \mathbb{N}^2$, it does not contain any infinite southward path. Therefore, for any $k$ and $t \in F_k$, $d_t > -\infty$, otherwise from $\Pi_{k,t}$ it would be possible to produce paths going arbitrarily far down, out of $\mathbb{N}^2$. Let $d_\infty = \max_{t \in F_\infty} \{d_t | t \in G\}$, $d_\infty$ is finite. On the other hand, $u_\infty = \max\{u_t | t \in F_\infty\}$ must be infinite. Indeed, if it is finite, let $s = u_\infty - d_\infty + 1$. Consider a maximal production $\Pi^*$ obtained by only placing tiles left of the vertical line $L^*$ at $x$-coordinate $x_s$. Starting from $\Pi^*$, the only attachable positions are isolated points on $L^*$, separated by a distance at least $w^s$. From each of them, it is possible to grow an arm which reaches no higher than $s$ upwards, whence, as illustrated on Figure 16, the part right of $L^*$ of that production is contained within a union of $(u_\infty - d_\infty)$-width horizontal bands, so its domain cannot be $G^\infty$.

For $t$ such that $u_t = +\infty$, all terminal productions on the right half-plane reach infinitely high. Thus, by applying Lemma 8 with increasing values of $m$, either one of these terminal productions contains a periodic path going up, or there are productions $P$ with arbitrarily
<figure><img src="image_26.png" /><figcaption>■ **Figure 14** The set $C_k$ is the set of all glues which attach across the vertical lines at coordinate $x_k$. Ignoring any tiles which are not visible in the picture, $C_0 = C_1 = \{a \cdot E, b \cdot E, c \cdot E\}$, $C_2 = \{a \cdot E, b \cdot E\}$ and $C_3 = \{c \cdot E\}$. The tiles marked with a 1 are the ones which appear in their column in some production without other tiles right of the red line; the subset $F_k$ of $C_k$ contains their east glues: $F_0 = F_1 = \{a \cdot E, b \cdot E\}$, $C_2 = \{a \cdot E\}$ and $C_3 = \{c \cdot E\}$</figcaption></figure>

► **Theorem 52.** Let $G \ni (0,0)$ a finite shape of $\mathbb{N}$.

If for all $k > 0$, there is an $x_k$ such that there is only one $y$ with $(x_k, y) \in (G^k)^+$ and $(x_k, y + 1) \in (G^k)^+$, then $G^\infty$ cannot be strictly self-assembled in the aTAM model unless $G = \{\vec{0}\}$.

**Proof.** Let $w$ and $h$ be the width and height of $G$. Assume that there is an aTAM $G$ which self-assembles $G^\infty$ at temperature $\tau$.

Let $C_k$ be the set of all glues which appear on the eastern edge of position $(x_k, y)$ for some value of $y$. Since $G$ assembles $G^\infty$, all the $C_k$ are non-empty, so let $C_\infty = \bigcap_k (\bigcup_{k'>k} C_{k'})$ be the set of glues appearing in infinitely many $C_k$; $C_\infty$ is also non-empty. Let $F_k \subseteq C_k$ be the set of glues $g$ such that there is a position $\vec{z} = (x_k, y)$ and a production $\Pi_{k,t}$ of $G$ where:

- the eastern glue of $\Pi_{k,t}(\vec{z})$ is $g$

- $\Pi_{k,t}$ contains no tile right of $x_k$

Like $C_\infty$, $F_\infty = \bigcap_k (\bigcup_{k'>k} F_{k'})$ is non-empty. The sets $C_k$ and $F_k$ are illustrated on Figure 14.

Now let $t$ be a glue of $G$, and $s_t$ be a (new) tile with $t$ on its eastern side, and $\epsilon$ on all other sides. Let $G_t[x \ge 1]$ be the set of productions of $G$, starting from the seed configuration with $s_t$ at $\vec{0}$ and attaching no tiles at positions $x < 1$. Let $u_t = \min_{p \in G_t[x>1]} \max\{y|(x,y) \in p\}$ and $d_t = \min_{p \in G_t[x>1]} \min\{y|(x,y) \in p\}$. These two quantities are illustrated on Figure 15.

Since $G^\infty \subset \mathbb{N}^2$, it does not contain any infinite southward path. Therefore, for any $k$ and $t \in F_k$, $d_t > -\infty$, otherwise from $\Pi_{k,t}$ it would be possible to produce paths going arbitrarily far down, out of $\mathbb{N}^2$. Let $d_\infty = \max_{t \in F_\infty} \{d_t | t \in G\}$, $d_\infty$ is finite. On the other hand, $u_\infty = \max\{u_t | t \in F_\infty\}$ must be infinite. Indeed, if it is finite, let $s = u_\infty - d_\infty + 1$. Consider a maximal production $\Pi^*$ obtained by only placing tiles left of the vertical line $L^*$ at $x$-coordinate $x_s$. Starting from $\Pi^*$, the only attachable positions are isolated points on $L^*$, separated by a distance at least $w^s$. From each of them, it is possible to grow an arm which reaches no higher than $s$ upwards, whence, as illustrated on Figure 16, the part right of $L^*$ of that production is contained within a union of $(u_\infty - d_\infty)$-width horizontal bands, so its domain cannot be $G^\infty$.

For $t$ such that $u_t = +\infty$, all terminal productions on the right half-plane reach infinitely high. Thus, by applying Lemma 8 with increasing values of $m$, either one of these terminal productions contains a periodic path going up, or there are productions $P$ with arbitrarily
<figure><img src="image_28.png" /><figcaption>■ **Figure 15** The definition of $u_t$ and $d_t$ given the two productions reachable from the glue $t$, without going left of the seed.</figcaption></figure>

<figure><img src="image_29.png" /><figcaption>■ **Figure 16** Faulty terminal productions which can be reached, left if some $d_t$ is infinite, right if all $u_t$ are finite: $\min_t(d_t) = -1$, $u_t = 1$, $u_s = 2$.</figcaption></figure>
<figure><img src="image_27.png" /><figcaption>■ **Figure 15** The definition of $u_t$ and $d_t$ given the two productions reachable from the glue $t$, without going left of the seed.</figcaption></figure>

<figure><img src="image_28.png" /><figcaption>■ **Figure 16** Faulty terminal productions which can be reached, left if some $d_t$ is infinite, right if all $u_t$ are finite: $\min_t(d_t) = -1$, $u_t = 1$, $u_s = 2$.</figcaption></figure>
<figure><img src="image_30.png" /><figcaption>■ **Figure 17** The part of the production that sees the seed only through $\tilde{z}_1$ contains cycles of $G^\infty$ of arbitrary size.</figcaption></figure>

large squares in their fill-in $P^\bullet$. In both cases, for each $k$, there is a production $F_k$ for which some $k \times k$ square is inaccessible from any point $(0, y)$ with $y > 0$ without crossing $F_k$, as illustrated on Figure 17.

For a large enough level of substitution, any glue $t$ for which $u_t$ is finite does not even grow one “meta-cell” up. Let $F_1 = \{g \in F_\infty | u_g = +\infty\}$, and $s_!$ be such that $\max\{u_g | g \notin F_1\} < h^{s_!}$ and $|d_\infty| < h^{s_!}$.

Consider a vertical line $L_x$ at some position $x$ between copies of $G^{s_!}$ in $G^\infty$. Let $P_y$ be a maximal subproduction of $P$ which can be assembled without attaching any tile right of $L_y$. In $P_y$, let $\tilde{z}_x = (x, y)$ be the lowest position on $L_x$ containing a tile $T$ of $F_{s_!}$.

By the pigeonhole principle, there must be two vertical lines $L_n$ and $L_m$ between copies of $G^{s_!}$ such that $P_n(\tilde{z}_n) = P_m(\tilde{z}_m)$. Let $\vec{v}$ be the vector $\tilde{z}_m - \tilde{z}_n$. By construction of $P_n$ and $P_m$, for any production $P_n^!$ obtained from $P_n$, there is a production $P_m^!$ obtained from $P_m$ such that the part of $P_n^!$ above and to the right of $\tilde{z}_n$ and the part of $P_m^!$ above and to the right of $\tilde{z}_m$ are identically filled. Hence, there is a vector which preserves either arbitrarily large cycles of $G^\infty$ or its intersection with a half-plane, thus $G$ must be trivial. ◀

This leaves open the case where in all the iterates $(G^k)^+$, there is a vertex which disconnects either the north and south or the east and west, but no straight line which crosses $(G^k)^+$ only once. A more precise variant of the previous proof takes care of that case.

► **Lemma 53.** Let $G \ni (0,0)$ a finite shape of $\mathbb{N}$, and for $k \in \mathbb{N}$, $G^k = \sigma_G^k(\{(0,0)\})$.
<figure><img src="image_29.png" /><figcaption>■ **Figure 17** The part of the production that sees the seed only through $\tilde{z}_!$ contains cycles of $G^\infty$ of arbitrary size.</figcaption></figure>

large squares in their fill-in $P^\bullet$. In both cases, for each $k$, there is a production $F_k$ for which some $k \times k$ square is inaccessible from any point $(0, y)$ with $y > 0$ without crossing $F_k$, as illustrated on Figure 17.

For a large enough level of substitution, any glue $t$ for which $u_t$ is finite does not even grow one “meta-cell” up. Let $F_! = \{g \in F_\infty | u_g = +\infty\}$, and $s_!$ be such that $\max\{u_g|g \notin F_!\} < h^{s_!}$ and $|d_\infty| < h^{s_!}$.

Consider a vertical line $L_x$ at some position $x$ between copies of $G^{s_!}$ in $G^\infty$. Let $P_y$ be a maximal subproduction of $P$ which can be assembled without attaching any tile right of $L_y$. In $P_y$, let $\tilde{z}_x = (x, y)$ be the lowest position on $L_x$ containing a tile $T$ of $F_{s!}$.

By the pigeonhole principle, there must be two vertical lines $L_n$ and $L_m$ between copies of $G^{s_!}$ such that $P_n(\tilde{z}_n) = P_m(\tilde{z}_m)$. Let $\vec{v}$ be the vector $\tilde{z}_m - \tilde{z}_n$. By construction of $P_n$ and $P_m$, for any production $P_n^!$ obtained from $P_n$, there is a production $P_m^!$ obtained from $P_m$ such that the part of $P_n^!$ above and to the right of $\tilde{z}_n$ and the part of $P_m^!$ above and to the right of $\tilde{z}_m$ are identically filled. Hence, there is a vector which preserves either arbitrarily large cycles of $G^\infty$ or its intersection with a half-plane, thus $G$ must be trivial. ◀

This leaves open the case where in all the iterates $(G^k)^+$, there is a vertex which disconnects either the north and south or the east and west, but no straight line which crosses $(G^k)^+$ only once. A more precise variant of the previous proof takes care of that case.

► **Lemma 53.** Let $G \ni (0,0)$ a finite shape of $\mathbb{N}$, and for $k \in \mathbb{N}$, $G^k = \sigma_G^k(\{(0,0)\})$.
If $\sup_k(G^k[N \leftrightarrow S]) = 1$ or $\sup(G^k[E \leftrightarrow W]) = 1$, then $G_\infty$ cannot be strictly self-assembled in the aTAM model unless it is trivial.

**Proof.** Omitted due to laziness [14]. In the previous proof, take a cut per $k$ which passes through the first occurence of each level of east-west bridges. Note that these cuts are not necessarily straight, but they remain within a bounded band around the bridges. The proof concludes as the previous one. ◀

Lemma 53 gives a dichotomy between generators for which the associated fractal can be strictly self-assembled and those for which it cannot. There is a polynomial time algorithm for determining which of Lemma 49 or Lemma 53 applies.

**▶ Theorem 54.** There is a polynomial time algorithm which, on input $G$ decides whether:

- there is a $k$ such that $G^k[N \leftrightarrow S] \ge 2$ and $G^k[E \leftrightarrow W] \ge 2$ and thus $G^\infty$ can be strictly self-assembled in the aTAM, or

- for all $k$, $G^k[N \leftrightarrow S] < 2$ and thus $G^\infty$ cannot be strictly self-assembled in the aTAM, or

- for all $k$, $G^k[E \leftrightarrow W] < 2$ and thus $G^\infty$ cannot be strictly self-assembled in the aTAM.

Notice that the second and third case are not mutually exclusive.

**Proof.** Without loss of generality, assume $G$ is connected.

First, use a max-flow algorithm to compute $G[d \leftrightarrow d']$ for all directions $d, d'$. If both $G[E \leftrightarrow W]$ and $G[N \leftrightarrow S]$ are 2 or more, then the first case applies.

Let $D$ be a set of pairs of directions, $v$ is a $D$-disconnector if $v$ disconnects $G^{+d}$ from $G^{+d'}$ for any $(d, d') \in D$. If $G[E \leftrightarrow W] = 1$, then there is at least one $\{EW\}$-disconnector. For any $D$-disconnector, define $\text{Cause}(v, D)$ as the set of pair of directions $(\delta, \delta')$ such that there are $(d, d') \in D$ and a path from $G^{+d}$ to $G^{+d'}$ which enters $v$ from direction $\delta$ and leaves it through direction $\delta'$.

Compute the disconnect causation graph $\Delta$. It is a directed graph whose vertices are couples $(v, D)$ where $v$ is a $D$-disconnector, and there is an arc from $(v, D)$ to each vertex $(v', \text{Cause}(v, D))$. The causation graph $\Delta$ has size at most $64|G|$ and the existence of each of its arcs can be tested in polynomial time.

The graph $\Delta$ contains a cycle reachable from $(v, \{EW\})$, if and only if for all $k$, $G^k[E \leftrightarrow W] < 2$, likewise for $N$ and $S$. Indeed, for $k > 0$, a vertex $v$ is a $D$-disconnector in $G^k$ if and only if:

- The vertex of $\lfloor v/G^{k-1} \rfloor$ of $G$ corresponding to the copy of $G^{k-1}$ containing $v$ is a $D$-disconnector, and

- the vertex $(v \bmod G^{k-1})$ of $G^{k-1}$ corresponding to the position of $v$ within that copy is a $\text{Cause}(v, D)$-disconnector.

Hence, from $\Delta$, it is possible to distinguish between the three cases. ◂

A Proof of the Tree Pump Lemma

The proof of Lemma 8 needs some ancillary definitions. The objects they introduce may seem overly sophisticated in view of the concreteness of the statement of Lemma 8, but one needs to soldier on. The reader may find solace in knowing that they are the result of persistent failure in the author's search of a more down-to-earth argument. The proof plainly needs systems endowed with the ability to escape the confines of the Euclidian plane $\mathbb{Z}^2$ and those of a merely infinite time. Hence, the definition and use of *Ordinal-length* sequences of *Free Assemblies*.
If $\sup_k(G^k[N \leftrightarrow S]) = 1$ or $\sup(G^k[E \leftrightarrow W]) = 1$, then $G_\infty$ cannot be strictly self-assembled in the aTAM model unless it is trivial.

**Proof.** Omitted due to laziness [14]. In the previous proof, take a cut per $k$ which passes through the first occurence of each level of east-west bridges. Note that these cuts are not necessarily straight, but they remain within a bounded band around the bridges. The proof concludes as the previous one. ◀

Lemma 53 gives a dichotomy between generators for which the associated fractal can be strictly self-assembled and those for which it cannot. There is a polynomial time algorithm for determining which of Lemma 49 or Lemma 53 applies.

**▶ Theorem 54.** There is a polynomial time algorithm which, on input $G$ decides whether:

- there is a $k$ such that $G^k[N \leftrightarrow S] \ge 2$ and $G^k[E \leftrightarrow W] \ge 2$ and thus $G^\infty$ can be strictly self-assembled in the aTAM, or

- for all $k$, $G^k[N \leftrightarrow S] < 2$ and thus $G^\infty$ cannot be strictly self-assembled in the aTAM, or

- for all $k$, $G^k[E \leftrightarrow W] < 2$ and thus $G^\infty$ cannot be strictly self-assembled in the aTAM.

Notice that the second and third case are not mutually exclusive.

**Proof.** Without loss of generality, assume $G$ is connected.

First, use a max-flow algorithm to compute $G[d \leftrightarrow d']$ for all directions $d, d'$. If both $G[E \leftrightarrow W]$ and $G[N \leftrightarrow S]$ are 2 or more, then the first case applies.

Let $D$ be a set of pairs of directions, $v$ is a $D$-disconnector if $v$ disconnects $G^{+d}$ from $G^{+d'}$ for any $(d, d') \in D$. If $G[E \leftrightarrow W] = 1$, then there is at least one $\{EW\}$-disconnector. For any $D$-disconnector, define $\text{Cause}(v, D)$ as the set of pair of directions $(\delta, \delta')$ such that there are $(d, d') \in D$ and a path from $G^{+d}$ to $G^{+d'}$ which enters $v$ from direction $\delta$ and leaves it through direction $\delta'$.

Compute the disconnect causation graph $\Delta$. It is a directed graph whose vertices are couples $(v, D)$ where $v$ is a $D$-disconnector, and there is an arc from $(v, D)$ to each vertex $(v', \text{Cause}(v, D))$. The causation graph $\Delta$ has size at most $64|G|$ and the existence of each of its arcs can be tested in polynomial time.

The graph $\Delta$ contains a cycle reachable from $(v, \{EW\})$, if and only if for all $k$, $G^k[E \leftrightarrow W] < 2$, likewise for $N$ and $S$. Indeed, for $k > 0$, a vertex $v$ is a $D$-disconnector in $G^k$ if and only if:

- The vertex of $\lfloor v/G^{k-1} \rfloor$ of $G$ corresponding to the copy of $G^{k-1}$ containing $v$ is a $D$-disconnector, and

- the vertex $(v \bmod G^{k-1})$ of $G^{k-1}$ corresponding to the position of $v$ within that copy is a $\text{Cause}(v, D)$-disconnector.

Hence, from $\Delta$, it is possible to distinguish between the three cases. ◂

A Proof of the Tree Pump Lemma

The proof of Lemma 8 needs some ancillary definitions. The objects they introduce may seem overly sophisticated in view of the concreteness of the statement of Lemma 8, but one needs to soldier on. The reader may find solace in knowing that they are the result of persistent failure in the author's search of a more down-to-earth argument. The proof plainly needs systems endowed with the ability to escape the confines of the Euclidian plane $\mathbb{Z}^2$ and those of a merely infinite time. Hence, the definition and use of *Ordinal-length* sequences of *Free Assemblies*.
## A.1 Free Assemblies

In this appendix, assemblies sit on a graph called an *assembly support* instead of $Z^2$.

**► Definition 55 (Assembly support).** An assembly support is a directed graph $G$ with labels in $\{N, E, S, W\}$ on its arcs, such that:

- each vertex has at most one incoming arc with each label,

- each vertex has at most one outgoing arc with each label,

- for any cycle $c$ of $G$, the sum of the labels of the arcs of $c$ is equal to $\vec{0}$ as a vector of $Z^2$,

- for any path $\pi$ of 1 or 3 arcs from $u$ to $v$, if the sum in $Z^2$ of the labels of $\pi$ is $\vec{d} \in \{N, E, S, W\}$, then there is an arc from $v$ to $u$ with label $-\vec{d}$.

An example of a correct assembly support is given on Figure 19, while Figure 18 shows some counter-examples of labeled graphs which are not assembly supports. Because of the conditions on the incoming and outgoing arcs of each vertex, it makes sense to represent the vertices as tiles, and arcs as sides the tiles share. This hopefully helps build the intuition that assembly support are “like $Z^2$, but long separated paths which should come to the same position may avoid each other”. On Figure 18, the direction corresponding to each side of the tile is given explicitely. With correct Assembly Supports, like the ones on Figure 19, the convention is that the direction of each side corresponds roughly to its direction on the page, and small adjustments allow tiles which would otherwise be adjacent on the page not to be. The appearance of tiles avoiding each other by going in the third dimension is deliberate, as a way to build intuition.

An *embedding* from an assembly support $G$ to another assembly support $G'$ is a graph embedding which preserves the label of the arcs. An *isomorphism* between $G$ and $G'$ is a graph isomorphism preserving the arc labels.

**► Definition 56 (Perspective difference, Translation).** For any two vertices $(z, z')$ of a connected component of an assembly support $G$, their perspective difference $z' \circled{-} z$ is $\sum_{a \in p} a$, where $p \in \{N, E, S, W\}^*$ is the sequence of labels of a path from $z$ to $z'$. For any embedding $e: G \to Z^2$, $e(z') - e(z) = z' \circled{-} z$. By convention, $z, z'$ are in different connected components, $z' \circled{-} z = \infty$.

A translation between two subgraphs $A \subset G$ and $B \subset G'$ of two assembly support is an isomorphism from $A$ to $B$ which preserves perspective differences. Any isomorphism between connected subgraphs is a translation.

For any Assembly Support $G$ and $z \in G$, squash$_{z,G}: G \to Z^2$ is the embedding $z' \mapsto (z' \circled{-} z)$. Since changing $z$ in squash$_{z,G}$ only amounts to a translation, it will generally be omitted. The index $G$ will be omitted as well when this causes no ambiguity.

The analysis in the Tree Pump Lemma relies on an examination of the *holes* of the productions of $S$. These holes need to be suitably defined now that the assemblies are no longer necessarily planar.

**► Definition 57 (Exterior Arc).** An exterior arc of an assembly support $G$ is a pair of a vertex $v$ of $G$ and a direction $d$ such that $v$ has no arc labelled $d$ in $G$.

**► Definition 58 (Converging Exterior Arcs, Growth).** Two exterior arcs $(v, d)$, $(v', d')$ are converging when $v' \circled{-} v = d' - d$ -they virtually point to the same empty position.

Given an assembly support $G$ and a set $Z$ of converging arcs, the assembly support $G + Z$ ($G$ grown by $Z$) is $G \cup \{\zeta\}$, where there is an arc $z \to \zeta$ (for $z \in G$) in direction $d$ whenever $(z, d) \in Z$.
## A.1 Free Assemblies

In this appendix, assemblies sit on a graph called an *assembly support* instead of $Z^2$.

**► Definition 55 (Assembly support).** An assembly support is a directed graph $G$ with labels in $\{N, E, S, W\}$ on its arcs, such that:

- each vertex has at most one incoming arc with each label,

- each vertex has at most one outgoing arc with each label,

- for any cycle $c$ of $G$, the sum of the labels of the arcs of $c$ is equal to $\vec{0}$ as a vector of $Z^2$,

- for any path $\pi$ of 1 or 3 arcs from $u$ to $v$, if the sum in $Z^2$ of the labels of $\pi$ is $\vec{d} \in \{N, E, S, W\}$, then there is an arc from $v$ to $u$ with label $-\vec{d}$.

An example of a correct assembly support is given on Figure 19, while Figure 18 shows some counter-examples of labeled graphs which are not assembly supports. Because of the conditions on the incoming and outgoing arcs of each vertex, it makes sense to represent the vertices as tiles, and arcs as sides the tiles share. This hopefully helps build the intuition that assembly support are “like $Z^2$, but long separated paths which should come to the same position may avoid each other”. On Figure 18, the direction corresponding to each side of the tile is given explicitely. With correct Assembly Supports, like the ones on Figure 19, the convention is that the direction of each side corresponds roughly to its direction on the page, and small adjustments allow tiles which would otherwise be adjacent on the page not to be. The appearance of tiles avoiding each other by going in the third dimension is deliberate, as a way to build intuition.

An *embedding* from an assembly support $G$ to another assembly support $G'$ is a graph embedding which preserves the label of the arcs. An *isomorphism* between $G$ and $G'$ is a graph isomorphism preserving the arc labels.

**► Definition 56 (Perspective difference, Translation).** For any two vertices $(z, z')$ of a connected component of an assembly support $G$, their perspective difference $z' \diamond z$ is $\sum_{a \in p} a$, where $p \in \{N, E, S, W\}^*$ is the sequence of labels of a path from $z$ to $z'$. For any embedding $e: G \to Z^2$, $e(z') - e(z) = z' \diamond z$. By convention, $z, z'$ are in different connected components, $z' \diamond z = \infty$.

A translation between two subgraphs $A \subset G$ and $B \subset G'$ of two assembly support is an isomorphism from $A$ to $B$ which preserves perspective differences. Any isomorphism between connected subgraphs is a translation.

For any Assembly Support $G$ and $z \in G$, squash$_{z,G}: G \to Z^2$ is the embedding $z' \mapsto (z' \diamond z)$. Since changing $z$ in squash$_{z,G}$ only amounts to a translation, it will generally be omitted. The index $G$ will be omitted as well when this causes no ambiguity.

The analysis in the Tree Pump Lemma relies on an examination of the *holes* of the productions of $S$. These holes need to be suitably defined now that the assemblies are no longer necessarily planar.

**► Definition 57 (Exterior Arc).** An exterior arc of an assembly support $G$ is a pair of a vertex $v$ of $G$ and a direction $d$ such that $v$ has no arc labelled $d$ in $G$.

**► Definition 58 (Converging Exterior Arcs, Growth).** Two exterior arcs $(v, d)$, $(v', d')$ are converging when $v' \diamond v = d' - d$ — they virtually point to the same empty position.

Given an assembly support $G$ and a set $Z$ of converging arcs, the assembly support $G + Z$ ($G$ grown by $Z$) is $G \cup \{\zeta\}$, where there is an arc $z \to \zeta$ (for $z \in G$) in direction $d$ whenever $(z, d) \in Z$.
<figure><img src="image_31.png" /><figcaption>■ **Figure 18** *Ceci n'est pas un Assembly Support:* three labelled graphs which fail to be assembly supports. Each vertex is represented by a tile, the labels of its sides are the labels of its outgoing arcs. A label on a side with no neighbor corresponds to an exterior arc. The bottom-left graph has a path of length 1 with label *E* from *z* to *u* but the *−E* = *W* neighbor of *u* is *t*. Also, the *N* neighbor of *t* is *u*, which has no *S* neighbor. The one in the top right has a 3 arc path "nope" whose labels sum to *N* + *E* + *S* = *E*, but *n* is not the *W* neighbor of *e* (actually, there is none). The one on the right has a cycle "*ϵ* miscounted" for which the sum of the labels is 3*E* + 3*N* + 2*W* + 3*S* = *E*, which is not $\vec{0}$.</figcaption></figure>

► **Definition 59** (Step, Exterior Path, Hole). There is a step between two arcs or exterior arcs (*v*, *d*) and (*v*', *d*') if:

G = G' and d, d' form a ±π/2 angle,

d = d' and there is an (non-exterior) arc from v to v' with label d'', with d, d'' forming a
±π/2 angle

d, d' form a ±π/2 angle and there is a cell v'' with v'' + d = v and v'' + d' = v'.

A (simple) exterior path is a sequence P = (p₀, p₁, ..., pₖ) of arcs, such that:

for each *i*, there is a step between *p*ᵢ and *p*ᵢ₊₁, and

for 0 < i < k, pᵢ is an exterior arc.

A hole is a simple exterior path which loops back to its starting exterior arc.

The perimeter of a hole $H = (h_0, \dots, h_k = h_0)$ is the set of vertices appearing in the exterior vertices $h_i$.

These definitions are illustrated on Figure 19, which features an assembly support with two holes of perimeter 20. These holes are “morally infinite”, so they resist attempts at a definition of area —at least the author’s naive ones. For an assembly which embeds into $\mathbb{Z}^2$, the free definition of hole corresponds to the intuition of a hole in an assembly, up to the detail that the exterior of the assembly forms a hole, so that all finite assemblies have at least one hole. Note that exterior paths are oriented: they turn in the positive direction around each tile.

► **Definition 60** (Free Assembly). A free assembly *A* of the TAS *S* is composed of an assembly support *A*·support and a total function *A*·tile : *A*·support $\rightarrow$ *S*·tileset.

For a TAS S, the set of free assemblies of S is written S<sup>Free</sup>.
<figure><img src="image_30.png" /><figcaption>■ **Figure 18** *Ceci n'est pas un Assembly Support:* three labelled graphs which fail to be assembly supports. Each vertex is represented by a tile, the labels of its sides are the labels of its outgoing arcs. A label on a side with no neighbor corresponds to an exterior arc. The bottom-left graph has a path of length 1 with label $E$ from $z$ to $u$ but the $-E = W$ neighbor of $u$ is $t$. Also, the $N$ neighbor of $t$ is $u$, which has no $S$ neighbor. The one in the top right has a 3 arc path "nope" whose labels sum to $N + E + S = E$, but $n$ is not the $W$ neighbor of $e$ (actually, there is none). The one on the right has a cycle "$\epsilon$ miscounted" for which the sum of the labels is $3E + 3N + 2W + 3S = E$, which is not $\vec{0}$.</figcaption></figure>

► **Definition 59** (Step, Exterior Path, Hole). There is a step between two arcs or exterior arcs $(v, d)$ and $(v', d')$ if:

■ $G = G'$ and $d, d'$ form a $\pm\frac{\pi}{2}$ angle,

■ $d = d'$ and there is an (non-exterior) arc from $v$ to $v'$ with label $d''$, with $d, d''$ forming a $\pm\frac{\pi}{2}$ angle

■ $d, d'$ form a $\pm\frac{\pi}{2}$ angle and there is a cell $v''$ with $v'' + d = v$ and $v'' + d' = v'$.

A (simple) exterior path is a sequence $P = (p_0, p_1, \dots, p_k)$ of arcs, such that:

■ for each $i$, there is a step between $p_i$ and $p_{i+1}$, and

■ for $0 < i < k$, $p_i$ is an exterior arc.

A hole is a simple exterior path which loops back to its starting exterior arc.

The perimeter of a hole $H = (h_0, \dots, h_k = h_0)$ is the set of vertices appearing in the exterior vertices $h_i$.

These definitions are illustrated on Figure 19, which features an assembly support with two holes of perimeter 20. These holes are “morally infinite”, so they resist attempts at a definition of area—at least the author’s naive ones. For an assembly which embeds into $\mathbb{Z}^2$, the free definition of hole corresponds to the intuition of a hole in an assembly, up to the detail that the exterior of the assembly forms a hole, so that all finite assemblies have at least one hole. Note that exterior paths are oriented: they turn in the positive direction around each tile.

► **Definition 60** (Free Assembly). A free assembly $A$ of the TAS $S$ is composed of an assembly support $A$-support and a total function $A$-tile: $A$-support $\rightarrow S$-tileset.

For a TAS $S$, the set of free assemblies of $S$ is written $S^{\text{Free}}$.
<figure><img src="image_32.png" /><figcaption>■ **Figure 19** An example of an assembly support, the shifts in the 3rd dimension between *e* and *g* as well as between *r* and *n* are artistic license to show the absence of adjacencies between those two branches. The sum of the vectors between neighbors on the cycle *abcdefghijklmnopqrsta* is $3E + 4N + 3E + 2S + 6E + 2S = \vec{0}$. The sum of vectors between neighbors on the path *fedcbatsrqp* is $2S + 3W + 2N + 3E = \vec{0}$, yet the vertices *f* and *p* are distinct. The small pending vertices next to the tiles are the exterior arcs; they form two holes, one for the square exterior arcs, and one for the circles. The dotted lines show the steps between the exterior arcs of the “circle” hole. The step between the exterior arcs (*m*, *S*) and (*m*, *E*) stems from the first case of the definition, the one between (*b*, *N*) and (*c*, *N*) from the second case, and the one between (*t*, *E*) and (*r*, *S*) because of the third. In this last case, *s* acts as the pivot between *r* and *s*. Both holes have perimeter 20.</figcaption></figure>
<figure><img src="image_31.png" /><figcaption>■ **Figure 19** An example of an assembly support, the shifts in the 3rd dimension between *e* and *g* as well as between *r* and *n* are artistic license to show the absence of adjacencies between those two branches. The sum of the vectors between neighbors on the cycle *abcdefghijklmnopqrsta* is $3E + 4N + 3E + 2S + 6E + 2S = \vec{0}$. The sum of vectors between neighbors on the path *fedcbatsrqp* is $2S + 3W + 2N + 3E = \vec{0}$, yet the vertices *f* and *p* are distinct. The small pending vertices next to the tiles are the exterior arcs; they form two holes, one for the square exterior arcs, and one for the circles. The dotted lines show the steps between the exterior arcs of the “circle” hole. The step between the exterior arcs (*m*, *S*) and (*m*, *E*) stems from the first case of the definition, the one between (*b*, *N*) and (*c*, *N*) from the second case, and the one between (*t*, *E*) and (*r*, *S*) because of the third. In this last case, *s* acts as the pivot between *r* and *s*. Both holes have perimeter 20.</figcaption></figure>
When there is an injective embedding $e: A$-support $\to G$, it naturally defines a free assembly $e(A)$ with $e(A)$-support $= e(A)$-support and for $z \in e(A)$-support, $e(A)(e(z)) = A(z)$. An assembly $A$ embeds into $\mathbb{Z}^2$ if squash is a one-to-one embedding $A$-support $\to \mathbb{Z}^2$; as above, this embedding naturally defines an assembly squash($A$).

**► Definition 61 (Free Attachment, Free Assembly Sequence).** Let $A, A'$ be free assemblies of some TAS system $S$, and $\eta: A \to A'$ an embedding. The tuple $(A, A', \eta)$ is an assembly candidate if:

- there is a $z \in A'$-support such that $\eta: A$-support $\to A'$-support $\setminus \{z\}$ is a translation,

- for any $z' \in A$-support, $A$-tile($z'$) = $A$-tile($\eta(z')$).

The definitions of attachment, assembly sequence, production and terminal production extend to free assemblies. The $\mathbb{Z}^2$ version of each definition is simply the particular case where every assembly embeds into $\mathbb{Z}^2$.

For a TAS $S$, the set of free assembly sequences of $S$ is written $\mathcal{H}^{\text{Free}}[S]$.

The definition of free attachment is illustrated on Figure 20. The fact that $\eta$ is an isomorohpism ensures that parts of the assembly which do not touch the position $z$ are unaffected by the attachment. This preserves the locality of the aTAM process, in contrast to what happens in the FTAM [5] for instance. Hence, while the above definition of attachment is given from the point of view of $A'$, “after the fact”, from the point of view of $A$, an attachment candidate can be defined from a tile type $t$ and a set $Z$ of convergent exterior arcs: $t@Z$ is the attachment candidate $(A, A', \eta)$ where:

- $A'$-support $= A$-support $+Z$, and $\zeta$ is the vertex of $A'$-support which is not in $A$-support,

- $\eta$ is the identity on $A$-support,

- $A'$-tile($\zeta$) = $t$,

- $A'$-tile($z$) = $A$-tile($z$) whenever $z \neq \zeta$.

For clarity, a “normal” assembly will be referred to as a $\mathbb{Z}^2$-assembly, likewise for the other concepts which were just endowed with a “free” variant.

Embeddings act not only on assembly supports and assemblies, but also on assembly sequences. In doing so, they may break the correctness of attachments if they are not one-to-one; when that happens, the sequence is cut short.

**► Definition 62 (Assembly Sequence Embedding).** Let $\alpha = (A_0 \to A_1 \to \dots) \in \mathcal{H}^{\text{Free}}[S]$, let $G = (\lim \alpha)$-support and $G'$ an assembly support. Let $e: G \to G'$ be an embedding; since up to translation, $A_0$-support $\subset A_1$-support $\subset \dots \subset (\lim \alpha)$-support, for each $i$, $e$ induces an embedding from $A_i$-support into $G'$.

Let $k$ be the largest $i$ such that $e$ is an isomorphism on $A_i$-support, then $e(\alpha)$ is the assembly sequence $(e(A_0), \dots, e(A_k))$.

## A.2 Ordinal Assembly Sequences

It is often practical to consider what happens in an assembly sequence $\alpha$ after it has placed an infinity of tiles. For this, ordinal assembly sequences come useful.

**► Definition 63 (Ordinal Assembly Sequence).** Let $o \in \omega_1$ be a countable ordinal, an o-Assembly Sequence starting from an assembly $A_0$ is a sequence of length $o$ of free assemblies such that for any $i < j \le o$, there is an injective embedding $\eta_{i \to j}: A_i \to A_j$ with:

- for $i < o$, $(A_i, A_{i+1}, \eta_{i \to i+1})$ is a free attachment,

- for $i < j < k \le o$, $\eta_{j \to k} \circ \eta_{i \to j} = \eta_{i \to k}$
When there is an injective embedding $e: A$-support $\to G$, it naturally defines a free assembly $e(A)$ with $e(A)$-support $= e(A)$-support and for $z \in e(A)$-support, $e(A)(e(z)) = A(z)$. An assembly $A$ embeds into $\mathbb{Z}^2$ if squash is a one-to-one embedding $A$-support $\to \mathbb{Z}^2$; as above, this embedding naturally defines an assembly squash($A$).

**Definition 61 (Free Attachment, Free Assembly Sequence).** Let $A, A'$ be free assemblies of some TAS system $S$, and $\eta: A \to A'$ an embedding. The tuple $(A, A', \eta)$ is an assembly candidate if:

- there is a $z \in A'$-support such that $\eta: A$-support $\to A'$-support $\setminus \{z\}$ is a translation,

- for any $z' \in A$-support, $A$-tile($z'$) = $A$-tile($\eta(z')$).

The definitions of attachment, assembly sequence, production and terminal production extend to free assemblies. The $\mathbb{Z}^2$ version of each definition is simply the particular case where every assembly embeds into $\mathbb{Z}^2$.

For a TAS $S$, the set of free assembly sequences of $S$ is written $\mathcal{H}^{\text{Free}}[S]$.

The definition of free attachment is illustrated on Figure 20. The fact that $\eta$ is an isomorohpism ensures that parts of the assembly which do not touch the position $z$ are unaffected by the attachment. This preserves the locality of the aTAM process, in contrast to what happens in the FTAM [5] for instance. Hence, while the above definition of attachment is given from the point of view of $A'$, “after the fact”, from the point of view of $A$, an attachment candidate can be defined from a tile type $t$ and a set $Z$ of convergent exterior arcs: $t@Z$ is the attachment candidate $(A, A', \eta)$ where:

- $A'$-support $= A$-support $+Z$, and $\zeta$ is the vertex of $A'$-support which is not in $A$-support,

- $\eta$ is the identity on $A$-support,

- $A'$-tile($\zeta$) = $t$,

- $A'$-tile($z$) = $A$-tile($z$) whenever $z \neq \zeta$.

For clarity, a “normal” assembly will be referred to as a $\mathbb{Z}^2$-assembly, likewise for the other concepts which were just endowed with a “free” variant.

Embeddings act not only on assembly supports and assemblies, but also on assembly sequences. In doing so, they may break the correctness of attachments if they are not one-to-one; when that happens, the sequence is cut short.

**Definition 62 (Assembly Sequence Embedding).** Let $\alpha = (A_0 \to A_1 \to \dots) \in \mathcal{H}^{\text{Free}}[S]$, let $G = (\lim \alpha)$-support and $G'$ an assembly support. Let $e: G \to G'$ be an embedding; since up to translation, $A_0$-support $\subset A_1$-support $\subset \dots \subset (\lim \alpha)$-support, for each $i$, $e$ induces an embedding from $A_i$-support into $G'$.

Let $k$ be the largest $i$ such that $e$ is an isomorphism on $A_i$-support, then $e(\alpha)$ is the assembly sequence $(e(A_0), \dots, e(A_k))$.

## A.2 Ordinal Assembly Sequences

It is often practical to consider what happens in an assembly sequence $\alpha$ after it has placed an infinity of tiles. For this, ordinal assembly sequences come useful.

**Definition 63 (Ordinal Assembly Sequence).** Let $o \in \omega_1$ be a countable ordinal, an o-Assembly Sequence starting from an assembly $A_0$ is a sequence of length $o$ of free assemblies such that for any $i < j \le o$, there is an injective embedding $\eta_{i \to j}: A_i \to A_j$ with:

- for $i < o$, $(A_i, A_{i+1}, \eta_{i \to i+1})$ is a free attachment,

- for $i < j < k \le o$, $\eta_{j \to k} \circ \eta_{i \to j} = \eta_{i \to k}$
<figure><img src="image_33.png" /><figcaption>■ **Figure 20** Some possible and impossible free attachments from a starting free assembly *S*, at temperature *τ*. Again, the third coordinate is a visual aid to show non-adjacencies; small dashed lines link points which embed in the same position in $\mathbb{Z}^2$. Assemblies *A* and *D* are reachable through one attachment $t_D@z$, where in each case, *z* is the position in dark gray. The assembly *B* is an attachment candidate, but it is not stable, since the new tile $t_D$ only binds through a strength-1 glue. The assembly *C* can not even form an attachment candidate from *S*, as *C*-support does not contain an isomorphic copy of *S*-support</figcaption></figure>
<figure><img src="image_32.png" /><figcaption>■ **Figure 20** Some possible and impossible free attachments from a starting free assembly *S*, at temperature *τ*. Again, the third coordinate is a visual aid to show non-adjacencies; small dashed lines link points which embed in the same position in $\mathbb{Z}^2$. Assemblies *A* and *D* are reachable through one attachment $t_D@z$, where in each case, *z* is the position in dark gray. The assembly *B* is an attachment candidate, but it is not stable, since the new tile $t_D$ only binds through a strength-1 glue. The assembly *C* can not even form an attachment candidate from *S*, as *C*-support does not contain an isomorphic copy of *S*-support</figcaption></figure>