Impossibility of strict assembly of infinite fractals by oritatami

Abstract

RNA cotranscriptional folding is the phenomenon in which an RNA transcript folds upon itself while being synthesized out of a gene. The oritatami system is a computation model of this phenomenon, which lets its sequence (transcript) of beads (abstract molecules) fold cotranscriptionally by the interactions between beads according to the binding ruleset. In such models based on self-assembly, one of the key questions is the ability to construct fractal structures. We focus on the problem of generating an infinite fractal curves using a cyclic oritatami system, which has an infinite periodic transcript. We first establish a formal definition of drawing a curve using an oritatami system, proposing conditions and restrictions with reference to prior oritatami designs for possibly infinite conformations. Under such definition, we prove that it is impossible to draw a Koch curve or a Minkowski curve infinitely. We then establish sufficient conditions of infinite aperiodic curves that a cyclic oritatami system cannot fold.

1 Introduction

Self-assembly is the process where smaller components autonomously form a larger complex structure using rather simple interactions among components. Self-assembly plays an important role in constructing biological structures and high polymers (Whitesides and Boncheva 2002). One well-known mathematical model of the self-assembly phenomenon is the abstract tile assembly model (aTAM) (Winfree 1998). Recently, Geary et al. (2016) proposed a new computation model, called the oritatami system, based on cotranscriptional self-assembly phenomenon from the experimental RNA transcription called RNA origami (Geary et al. 2014). In general, the oritatami system use beads to describe basic components, and a sequence of beads is transcribed linearly to fold a geometric structure on the planar triangular lattice according to the predefined set of interactions and the reaction rate of the folding. The oritatami system consists of a transcript (a sequence of beads) and a set of rules for possible intermolecular reactions between beads (Fig. 1). For each bead in the sequence, the system takes a lookahead of a few upcoming beads and determines the best location of the bead that maximizes the number of possible interactions from the lookahead. The lookahead represents the reaction rate of the cotranscriptional folding and the number of interactions represents the energy level (see Fig. 2 for the analogy between RNA origami and oritatami).

Fig. 1

The motivation of the oritatami system. a An illustration of an RNA origami (Geary et al. 2016), which transcribes an RNA strand that self-assembles. b The product of an RNA origami. c Abstraction of the product in the oritatami system

Fig. 2

a Analogy between RNA origami and oritatami. b Visualization of an oritatami system and its terms

Since the oritatami system is a geometric computation model, many researchers focused on the capability of folding geometric structures. It is proved that we can fold arbitrary geometric shapes with the fixed bead types and rulesets (Demaine et al. 2018; Han and Kim 2018). Rogers and Seki (2017) proved the decidability of geometric structure constructions based on the delay.

A fractal is an infinite pattern that is self-similar across different scales, and is an important structure in nature. The construction of fractals is one of the most important topics in both geometric computation models (Hendricks et al. 2018; Hendricks and Opseth 2017; Lathrop et al. 2009) and experiments (Tesoro and Ahnert 2016; Tikhomirov et al. 2017). There are two types of shape self-assembly: strict self-assembly, where the target shape is distinguished by existence of the constructed structure, and weak self-assembly, where the target shape is distinguished by different tile types. In aTAM, it is known that we can weakly assemble the Sierpinski triangle (Rothemund et al. 2004), but not strictly without a few modifications (Lathrop et al. 2009). In oritatami, fractals that can be embedded in 1D cellular automata can be weakly and infinitely assembled (Pchelina et al. 2020). On the other hand, Masuda et al. (2018) proposed how to strictly construct a finite Heighway dragon using a cyclic oritatami system, which has a periodic transcript.

We focus on the problem of strictly drawing an infinite aperiodic curves on the plane. It is crucial to establish an agreement on the definition of strict drawing. Based on prior oritatami designs for possibly infinite conformations, we first establish a formal definition of drawing a curve using an oritatami system in Sect. 3, proposing reasonable conditions and restrictions. Under such definition, we first prove that regardless of the delay and the period, it is impossible to strictly fold Koch curves in Sect. 4. Then, we propose sufficient conditions of an infinite aperiodic curve and a cyclic oritatami system such that the curve is not strictly foldable under the given delay and period in Sect. 5.

2 Preliminaries

Let $w = a_1 a_2 \ldots a_n$ be a string over $\Sigma$ for some integer n and bead types $a_1, \ldots , a_n \in \Sigma$. The length |w| of w is n. For two indices i, j with $1\le i\le j\le n$, we let w[i, j] be the substring $a_ia_{i{+}1}\ldots a_{j{-}1}a_j$; we use w[i] to denote w[i, i]. We use $w^m$ to denote the concatenation of m copies of w.

Oritatami systems operate on the triangular lattice $\Lambda _t$ with the vertex set V and the edge set E. A configuration on $\Lambda _t$ is a triple (P, w, H) of a directed path P in $\Lambda _t$, $w \in \Sigma ^* \cup \Sigma ^\omega$, and a set $H \subseteq \{(i, j) \bigm | 1 \le i, i+2 \le j, \{P[i], P[j]\} \in E \}$ of interactions. This is to be interpreted as the sequence w being folded while its i-th bead w[i] is placed on the i-th point P[i] along the path and there is an interaction between the i-th and j-th beads if and only if $(i, j) \in H$. Configurations $(P_1, w_1, H_1)$ and $(P_2, w_2, H_2)$ are congruent provided $w_1 = w_2$, $H_1 = H_2$, and $P_1$ can be transformed into $P_2$ by a combination of a translation, a reflection, and rotations by 60 degrees. The set of all configurations congruent to a configuration (P, w, H) is called the conformation of the configuration and denoted by $C=[(P, w, H)]$. We call w a transcript of C.

A ruleset ${\mathcal {H}}\subseteq \Sigma \times \Sigma$ is a symmetric relation specifying between which bead types can form an interaction. An interaction $(i, j) \in H$ is valid with respect to ${\mathcal {H}}$, or simply ${\mathcal {H}}$-valid, if $(w[i], w[j]) \in {\mathcal {H}}$. We say that a conformation C is ${\mathcal {H}}$-valid if all of its interactions are ${\mathcal {H}}$-valid. For an integer $\alpha \ge 1$, C is of arity $\alpha$ if the maximum number of interactions per bead is $\alpha$, that is, if for any $k \ge 1$, $\bigl |\{i \mid (i, k) \in H \} \bigr | + \bigl |\{j \mid (k, j) \in H\} \bigr | \le \alpha$ and this inequality holds as an equation for some k. By ${\mathcal {C}}_{\le \alpha }$, we denote the set of all conformations of arity at most $\alpha$.

Oritatami systems grow conformations by elongating them under their own ruleset. For a finite conformation $C_1$, we say that a finite conformation $C_2$ is an elongation of $C_1$ by a bead $b \in \Sigma$ under a ruleset ${\mathcal {H}}$, written as $C_1 {\mathop {\rightarrow }\limits ^{\mathcal {H}}}_b C_2$, if there exists a configuration (P, w, H) of $C_1$ such that $C_2$ includes a configuration $(P\cdot p, w\cdot b, H \cup H')$, where $p \in V$ is a point not in P and $H' \subseteq \left\{ (i, |P|{+}1) \bigm | 1 \le i \le |P|-1, \{P[i], p\} \in E, (w[i], b) \in {\mathcal {H}} \right\}$. This operation is recursively extended to the elongation by a finite sequence of beads as follows: For any conformation C, $C {\mathop {\rightarrow }\limits ^{\mathcal {H}}}_\lambda ^* C$; and for a finite sequence of beads w and a bead b, a conformation $C_1$ is elongated to a conformation $C_2$ by $w\cdot b$, written as $C_1 {\mathop {\rightarrow }\limits ^{\mathcal {H}}}_{w\cdot b}^* C_2$, if there is a conformation $C^\prime$ that satisfies $C_1 {\mathop {\rightarrow }\limits ^{\mathcal {H}}}_w^* C^\prime$ and $C' {\mathop {\rightarrow }\limits ^{\mathcal {H}}}_b C_2$.

An oritatami system is a 6-tuple $\Xi = (\Sigma , w, {\mathcal {H}},$

$\delta , \alpha , C_\sigma =[(P_\sigma ,w_\sigma ,H_\sigma )])$, where ${\mathcal {H}}$ is a ruleset, $\delta \ge 1$ is a delay, and $C_\sigma$ is an ${\mathcal {H}}$-valid initial seed conformation of arity at most $\alpha$, upon which its transcript $w \in \Sigma ^* \cup \Sigma ^\omega$ is to be folded by stabilizing beads of w one at a time and minimize energy collaboratively with the succeeding $\delta -1$ nascent beads. The set $\mathcal {F}(\Xi )$ of conformations foldable by this system is defined recursively, as follows: the seed $C_\sigma$ is in $\mathcal {F}(\Xi )$; then provided that an elongation $C_i$ of $C_\sigma$ by the prefix w[1 : i] is foldable (i.e., $C_0 = C_\sigma$), its further elongation $C_{i{+}1}$ by the next bead $w[i{+}1]$ is foldable if

$$\begin{aligned} C_{2} \in \mathop {argmin}_{C \in {\mathcal {E}}_{\alpha }(C_{1}, x[1])} \min \left\{ \Delta G(C') \bigm | C' \in {\mathcal {E}}_{\alpha }(C, x[2, d]))\right\} , \end{aligned}$$

(1)

where $\Delta G(C^\prime)$ is an energy function that assigns to $C^\prime$ with the negation of the number of h-interactions within $C'$ as energy. Informally speaking, $C_2$ is a conformation obtained by elongating $C_1$ by the bead x[1] such that the beads $x[1], x[2], \ldots ,x[d]$ create as many h-interactions as possible. Then, we write $C_1\overset{\Xi }{\hookrightarrow }_{x}C_2$, and the superscript $\Xi$ is omitted whenever $\Xi$ is clear from the context. Through the folding, the first bead of x is stabilized. A conformation foldable by $\Xi$ is terminal if none of its elongations is foldable by $\Xi$. An oritatami system is deterministic if, for all i, there exists at most one $C_{i{+}1}$ that satisfies (1). Namely, a deterministic oritatami system folds into a unique terminal conformation. An oritatami system is cyclic if its transcript $w=w_o^\omega$ is a repetition of some string $w_o$. We say that the oritatami system has a period $|w_o|$.

Fig. 3

An example oritatami system with delay 3 and arity 4. The seed is colored in red, elongations are colored in blue, and the stabilized beads and interactions are colored in black. (Color figure online)

Figure 3 illustrates an example of an oritatami system with delay 3, arity 4, ruleset $\{(a,\bar{a})\}$ and transcript $w=\bar{a}\bar{a}\bar{a}{aaa}\bar{a}\bar{a}\bar{a}$; in (a), the system tries to stabilize the first bead $\bar{a}$ of the transcript, and the elongation $P_1$ gives 2 interactions, while the elongation $P_2$ gives 4 interactions, which is the most stable one. Thus, the first bead $\bar{a}$ is stabilized according to the location in $P_2$. In (b) and (c), $P_2$ is the most stable elongation and $\bar{a}$’s are stabilized according to $P_2$. As a result, the terminal conformation is given as in (d). Note that the terminal conformation has repeated patterns that may grow infinitely, and we can use $w=(\bar{a}\bar{a}\bar{a}aaa)^\omega$ to fold an infinite periodic conformation. This example is called a glider (Geary et al. 2018).

The bead stabilization in an oritatami system is a local optimization of finding the best position of the bead using the next $\delta$ beads. Thus, the stabilization of a bead w[i] in a delay-$\delta$ oritatami system is not affected by any bead whose distance from $w[i{-}1]$ is greater than $\delta +1$. On the triangular lattice, we can draw a hexagonal border of radius $\delta +1$ from $w[i{-}1]$, which we call the event horizon of w[i] (Han et al. 2020), to identify the set of points that may affect the stabilization of w[i]. While stabilizing a bead w[i], we define the event horizon context of w[i] (Han et al. 2020) to be the pair of beads and interactions within this hexagon. We call the stabilization point of w[i] as the center of the event horizon (context). Namely, the event horizon context is the context used to stabilize w[i]. Thus, if two beads w[i] and w[j] have the same event horizon context, then w[i] and w[j] are stabilized congruently (see Fig. 4). In general, we define the event horizon of a point on $\Lambda _t$ to be a hexagonal border of radius $\delta +1$ from the point, regardless of bead existence on the point. Given a number of event horizons, we define the union of event horizons to be the border surrounding points within one of the event horizons, and the union of event horizon contexts to be the partial conformation within the unified event horizon.

Fig. 4

Two same event horizon contexts when $\delta =2$. We consider two bead types (dots and circles). The current bead is colored in cyan and the previous bead is colored in blue. Since all the beads and interactions within two event horizons are congruent, they have the same event horizon context. Note that two partial conformations inside the event horizons are not congruent due to red paths. (Color figure online)

An L-system is a parallel rewriting system and its recursive nature makes the system easy to describe fractal-like structures (Rozenburg and Salomaa 1980). An L-system is defined as $G=(V,C,\omega ,P)$, where

• V is the set of variables that can be replaced by production rules,

• C is the set of constants that do not get replaced,

• $\omega \in (V\cup C)^*$ is the axiom, the initial string, and

• $P\subseteq V\times (V\cup C)^*$ is the set of production rules defining rewriting of variables.

The system starts with $\omega$, and as many rules as possible are applied simultaneously for each iteration. With graphical semantics on variables and constants, the L-system is often used to represent self-similar fractals (Fig. 5). In this paper, we focus on the curves that can be plotted on the triangular or square grid. We assume that curves are represented by strings, whose characters represent turns and unit segments. Then, an infinite curve is periodic if there exists a periodic string representation with a fixed finite period, and is aperiodic otherwise. Note that all fractal infinite curves are aperiodic. A curve is self-touching if it intersects with itself. For example, the Heighway dragon is self-touching while a spiral is not, as in Fig. 10

Fig. 5

(left) The Heighway dragon is self-touching (right) A spiral is not self-touching

3 Strict drawing of a curve

We establish a few assumptions on the drawing of a curve by the oritatami system, with reference to prior oritatami designs.

• 1. Since the oritatami system folds a linear transcript on the plane, it is natural to consider fractal curves, which are infinite sequences of segments (and points).

• 2. We only consider a deterministic oritatami system (that only folds into a unique conformation). Note that it is trivial to make a nondeterministic oritatami system that may fold into several different structures including a target structure.

• 3. We consider an infinite fractal construction. Masuda et al. (2018) proposed how to construct a finite fractal by implementing a counter and an automaton periodically inside the transcript. This approach can be used to construct an arbitrary long fractal but not an infinite one, since the counter is finite. Maruyama and Seki (2020) proposed a periodic infinite counter, but the counter is not suitable as a (finite) component of construction since the width infinitely increases to cover increasing digits.

• 4. Since we need an infinite transcript with a formal finite representation, it is a natural choice to use a cyclic oritatami system that has an infinitely repeated transcript. Researchers already used cyclic oritatami systems to construct conformations that can grow infinitely (Geary et al. 2018).

Let a shape be a set of points on the triangular lattice $\Lambda _t$, whose grid graph is connected. A curve can be represented as a sequence of alternating points and segments. We say that a sequence of shapes represents a curve if there exists one-to-one correspondence between shapes and alternating points and segments, and a point and a segment should be adjacent on the curve if and only if two shapes corresponding to them are adjacent. We formally define the strict drawing of the curve by a deterministic oritatami system as follows:

Definition 1

Given a (possibly infinite) curve on the plane and the (possibly infinite) sequence $(S_k)$ of shapes that represents the curve, we say that a deterministic oritatami system strictly draws the curve if the following condition holds: There exists a (possibly infinite) sequence $(i_k)$ of indices that corresponds to the sequence of shapes, where, for all k’s, there exists a partial configuration for $w[i_{k{-}1}{+}1,i_k]$ that folds within $S_k$. We say that the oritatami system covers $S_k$ with the partial transcript $w[i_{k{-}1}{+}1,i_k]$.

Figure 6 shows two examples of strict curve drawing by an oritatami system. Here, the target curve is represented by three shapes $(S_1,S_2,S_3)$. By Definition 1, an oritatami system draws the curve in Fig. 6a but does not in Fig. 6b since the partial configuration for w[3, 11] is not within $S_2$. Note that shapes limit paths of conformations, and it is not necessary to fill all points in the shape with the conformation.

From the design perspective, it is crucial to assume this locality of partial configuration. Oritatami designs are usually modular (Geary et al. 2016, 2018; Han et al. 2018; Masuda et al. 2018)—a partial transcript is folded locally under a controlled context, and we connect these partial transcripts to perform complex computations. Especially, for an infinite transcript, it becomes almost impossible to remove unintended interferences without this locality. Previous cyclic oritatami systems such as a binary counter (Geary et al. 2016) or a cyclic tag system (Geary et al. 2018) follow this assumption. Remark that the drawing in Definition 1 is general in the sense that it does not restrict the oritatami system to be infinite or cyclic, and the curve to be infinite.

Fig. 6

a An oritatami system draws the target curve and b an oritatami system does not draw the target curve by Definition 1

4 Impossibility of strict drawing of the infinite Koch curve

We start with one example of infinite fractal curves—the Koch curve. The Koch curve can be constructed by starting with a segment, then recursively altering each line segment as follows:

• 1. Divide the line segment into three segments of equal length.

• 2. Draw an equilateral triangle that has the middle segment from step 1 as its base and points outward.

• 3. Remove the line segment that is the base of the triangle from step 2.

Using the L-system, the Koch curve can be encoded as follows:

• Variable: F

• Constants: $+,-$

• Axiom: F

• Production Rule: $F\rightarrow F+F-F+F$,

where F denotes a segment, − denotes $120^\circ$ right turn and $+$ denotes $60^\circ$ left turn. Fig. 7 illustrates the Koch curve after three iterations.

Fig. 7

The Koch curve after three iterations

We assume the followings to draw the Koch curve:

• 1. The Koch curve consists of an infinite sequence of alternating points and segments on the triangular lattice $\Lambda _c$, which is with vertical rows with unit triangles pointing left and right. We use a hexagon $S_d$ of side length d to represent a point on the curve. For a segment on the curve, we use a shape $S_l$ of d points ($l+1$ rows in total) and $d+1$ points (l rows in total) in alternative positions which are orthogonal to the direction of the segment (see Fig. 8a). The oritatami system starts covering the first $S_d$, and denote the ith $S_d$ ($S_l$) by $S_d[i]$ ($S_l[i]$). We define the unit distance between two $S_d$’s as the unit distance between two points corresponding to $S_d$’s on $\Lambda _c$.

• 2. We use constant numbers of beads for segments or points—$p_d$ beads in $S_d$, and $p_l$ beads in $S_l$. This assumption is reasonable in the modular design of the oritatami system.

Fig. 8

a Shapes used to draw the Koch curve b an example of an oritatami system with $p_l=9$ and $p_d=11$

Figure 8 shows an example of shapes that can be used to draw the Koch curve, and a part of an oritatami system that draws the curve, following the above assumptions. In Fig. 8a, $S_d$’s are drawn in red, and $S_l$’s are drawn in blue, where $d=2$ and $l=3$. In Fig. 8b, from the assumption (2), the number of beads for segments or points are constant, even if there are different paths in different $S_d$’s or $S_l$’s. For example, paths in $S_d$ use 11 beads and paths in $S_l$ use 9 beads.

Under these assumptions, we claim the following theorem.

Theorem 1

Suppose we assume the followings to draw the Koch curve:

• 1. We use a hexagon $S_d$ of side length d to represent a point on the curve. For a segment on the curve, we use a shape $S_l$ of d points ($l+1$ rows in total) and $d+1$ points (l rows in total) in alternative positions which are orthogonal to the direction of the segment. The oritatami system starts covering the first $S_d$.

• 2. We use constant numbers of beads for segments or points—$p_d$ beads in $S_d$, and $p_l$ beads in $S_l$.

Under these assumptions, there is no deterministic oritatami system that can strictly draw the Koch curve.

Proof

Assume that there exists a deterministic cyclic oritatami system $\Xi$ with delay $\delta$ that draws the Koch curve. Note that for two $S_d$’s which are two unit distances apart by a $120^\circ$ in the middle, the distance between centering points of $S_d$’s on $\Lambda _t$ is $3d+3l+3$. Based on this, we first assume that $\delta \le 3d+3l+1$, which makes the radius of an event horizon less than $3d+3l+3$. We denote the event horizon context for the maximum delay as the “maximum” event horizon context, and omit the term maximum if the context is clear (see Fig. 9a). For convenience, we use $S_{dl}[i]$ to denote the shape resulted from connecting $S_d[i]$ and $S_l[i]$.

Let E(i) be an event horizon context used to fold the conformation in $S_{dl}[i]$. It is straightforward that the boundary of E(i) includes the union of event horizon contexts of all points in $S_{dl}[i]$. Moreover, we observe that the first bead of the conformation in $S_{dl}[i]$ is stabilized using the event horizon context of the previous bead, which should be the last bead of the conformation in $S_l[i{-}1]$. Thus, event horizon contexts of all points that are in $S_l[i{-}1]$ and adjacent to $S_d[i]$ should also be unified to E(i). We have two types of turns in the Koch curve—$120^\circ$ right turn and $60^\circ$ left turn, which correspond to two possible directions of $S_l[i{-}1]$. Figure 9b illustrates the boundary of E(i), including the event horizons of points in orange $S_l$’s and adjacent to $S_p[i]$. Due to the delay upper bound, all $S_d$’s that overlap with E(i) are at most two unit distances apart from $S_d[i]$.

Fig. 9

a The maximum event horizon of the center of $S_d[i]$ is represented by a red hexagon. b The boundary of the event horizon context E(i) is represented by a red polygon. Small squares in orange $S_l$’s indicate points outside $S_{dl}[i]$ and affecting E(i). All $S_l$’s and $S_d$’s that overlap with E(i) are depicted

Since the Koch curve does not touch itself, if a point in $\Lambda _c$ is adjacent to two segments of the curve, there is no segment other than two that are adjacent to the point. Moreover, due to the self-similarity of the curve, the same statement holds for any scale of the power of 3—for a point $q_0$ in $\Lambda _c$, if there exist two points $q_1$ and $q_2$ on the curve that are $3^t$ unit distances straight away from $q_0$, then there is no segment within $3^t-1$ unit distances from $q_0$, other than segments on the curve from $q_1$ and $q_2$ (see Fig. 10).

Fig. 10

An example of $q_0$, $q_1$ and $q_2$. Points $q_1$ and $q_2$ are 3 unit distances straight away from $q_0$. Aside from curves from $q_1$ and $q_2$, there is no segment within 2 unit distances from $q_0$ (surrounded by a dotted hexagon)

In Fig. 11, since the boundary of E(i) covers up to two unit distances from $S_d[i]$, we consider the relative position of $S_{dl}[i]$ (illustrated by dots) on the (partial) Koch curve after one iteration (orange shape), with four segments and the maximum unit distance among points being 3. We first transcribe the green curve (if it exists), and then the orange curve. For each of four distinct positions, we have two different cases of the former curve which overlaps with E(i), except 3). In total, we have seven different cases of the former Koch curve which overlaps with E(i). The thick black hexagons represent candidates of $q_0$ in Fig. 10. We can observe that in all cases, all $S_d$’s are at most three unit distances apart from one of $q_0$’s, and they are empty except the green and orange shapes. Moreover, in all cases, all beads within E(i) are from $S_d[i{-}4]$ to $S_l[i{-}1]$, a consecutive sequence of shapes before $S_l[i]$. In other words, a partial conformation in $S_{dl}[i]$ is dependent on beads in the sequence of shapes from $S_d[i{-}4]$ to $S_l[i{-}1]$.

The upper bound for the number of possible paths within $S_d$ ($S_l$) is $5^{p_d}$ ($5^{p_l}$). We have beads from $S_d[i{-}4]$ to $S_l[i{-}1]$ that determine the partial conformation in $S_{dl}[i]$. Regarding the period $p_o$ of the system, we have j and k such that $1\le j<k\le 1{+}p_o\cdot 5^{4p_l+4p_d}$, and $S_{dl}[j]$ and $S_{dl}[k]$ have exactly the same conformation. Moreover, since beads from $S_d[i{-}4]$ to $S_l[i{-}1]$ are consecutively transcribed, $S_{dl}[j]$ and $S_{dl}[k]$ result in a periodic sequence of segment turns of length $k-j$ (see Fig. 12). Since the Koch curve is aperiodic, we know that the first assumption $\delta <3l+3d+2$ is wrong.

Fig. 11

Seven different cases of the former Koch curve which overlaps with E(i). Dots represent points in $S_{dl}[i]$

Fig. 12

A series of event horizon contexts (in dotted hexagons) for the first bead of $S_l[i]$. Shapes $S_l$’s and $S_d$’s are simplified for better readability. There exist indices $1\le j<k\le 1{+}p_o\cdot 5^{4p_l+4p_d}$ such that they have exactly the same event horizon contexts for beads within $S_d[j]$ ($S_l[j]$) and $S_d[k]$ ($S_l[k]$)

Now we generalize the upper bound for the delay. Let $x(t)=3\cdot 4^{t-1}(l+d+1)-2$. For $x(t{-}1)<\delta \le x(t)$, the event horizon context for beads in $S_{dl}[i]$ covers only $S_d$’s which are within $3^t-1$ unit distances from $S_d[i]$. The case analysis is similar to the previous delay bound, and at most $2\cdot 4^t$ segments before $S_{dl}[i]$ can overlap with E(i). Thus, among $S_{dl}[1]$ to $S_{dl}[1{+}p_o\cdot 5^{2\cdot 4^t(p_l+p_d)}]$, there should exist $S_{dl}[j]$ and $S_{dl}[k>j]$ that have exactly the same event horizon context for points within. Therefore, we know that for any given $\delta$, there is no delay-$\delta$ deterministic oritatami system that can draw the Koch curve. $\square$

5 Impossibility of strict drawing of infinite aperiodic curves

We further inspect conditions for impossibility of strict drawing of infinite aperiodic curves, which include fractals. Construction of infinite periodic curves using a cyclic oritatami system seems to be reasonable if we can design a partial oritatami system that folds one period of the curve, and we have one running example—the glider in Sect. 2. On the other hand, for infinite aperiodic curves, we propose sufficient conditions that makes curves impossible to fold. We make the following assumptions:

• The curve is on an arbitrary lattice $\Lambda _c$, and each point (segment) in $\Lambda _c$ is mapped to a shape $S_d$ ($S_l$) in the triangular lattice $\Lambda _t$.

• The oritatami system uses $p_d$ ($p_l$) beads for $S_d$ ($S_l$). We say $p_{dl}=p_d+p_l$.

• The oritatami system has the period of $p_o$.

• The curve is represented by an infinite alternation of $S_d$ and $S_l$, starting from $S_d[1]$. For convenience, we refer to the union of $S_d[i]$ and $S_l[i]$ as $S_{dl}[i]$.

Let $\delta _{\texttt {max}}$ be an upper bound of the delay $\delta$. We propose the condition that curves are not foldable when $\delta \le \delta _{\texttt {max}}$, and expand the result to all possible delays. Suppose we want to stabilize beads in $S_{dl}[i]$. Then, the maximum event horizon context $E(i,\delta _{\texttt {max}})$ for beads in $S_{dl}[i]$ is defined by the union of event horizon contexts of 1) all points in $S_{dl}[i]$ and 2) points which are in the possible $S_l[i{-}1]$’s and adjacent to $S_d[i]$, for stabilization of the first bead in $S_d[i]$. Now, for each i, we have $S_d[r(i,\delta _{\texttt {max}})]$ that appears first in $E(i,\delta _{\texttt {max}})$. Let $\displaystyle D(i,\delta _{\texttt {max}})=\max _{1\le j\le i} (j-r(j,\delta _{\texttt {max}}))$ to be the maximum difference between j and $r(j,\delta _{\texttt {max}})$ for all $j\le i$. Then, it takes $1 + gcd (p_{o} ,p_{{dl}} ) \cdot 5^{{D(i,\delta _{{\max }} )p_{{dl}} }}$ to have exactly the same conformation for the previous $D(i,\delta _{\texttt {max}})$ segments, which results in the same maximum event horizon context and the same conformation for two shapes $S_{dl}[j]$ and $S_{dl}[k>j]$. After $S_{dl}[j]$ and $S_{dl}[k]$, it is assured that previous $D_{i,\delta _{\texttt {max}}}$ beads have exactly the same conformation for the consecutively following shapes, and these shapes fold exactly the same. Since $D(i,\delta _{\texttt {max}})$ is dependent on i, we have the following theorem.

Theorem 2

If there exists i such that $1 + gcd (p_{o} ,p_{{dl}} ) \cdot 5^{{D(i,\delta _{{\max }} )p_{{dl}} }} \le i$, then it is impossible to strictly draw a given infinite aperiodic curve with a cyclic oritatami system whose delay is less than or equal to $\delta _{\texttt {max}}$ and period is $p_o$.

In practice, the delay of the oritatami system is bounded by the transcript length. If we consider a cyclic oritatami system that has an infinite transcript, the delay can be arbitrarily large. We extend Theorem  2 for arbitrarily large delays and obtain the following statement.

Theorem 3

Suppose for all $\delta _{\texttt {max}}\ge 1$, there exists i such that $1 + gcd (p_{o} ,p_{{dl}} ) \cdot 5^{{D(i,\delta _{{\max }} )p_{{dl}} }} \le i$. Then, it is impossible to strictly draw a given aperiodic infinite curve with a cyclic oritatami system whose period is $p_o$.

If there exists $i_{\texttt {max}}$ such that $D(i,\delta _{\texttt {max}})=D(i_{\texttt {max}},\delta _{\texttt {max}})$ for all $i\ge i_{\texttt {max}}$, then we may use $i\ge i_{\texttt {max}}$ to satisfy the conditions for all $\delta _{\texttt {max}}$’s regardless of $gcd(p_o,p_{dl})$. In such a case, the following statement holds.

Theorem 4

Suppose for all $\delta _{\texttt {max}}$, there exists $i_{\texttt {max}}$ such that $D(i,\delta _{\texttt {max}})=D(i_{\texttt {max}},\delta _{\texttt {max}})$ for all $i\ge i_{\texttt {max}}$, then it is impossible to strictly draw a given infinite aperiodic curve with a cyclic oritatami system regardless of the delay and the period.

We can prove impossibility of strict drawing of the Koch curve by Theorem  4. Based on Fig. 9, for a given delay upper bound $x(t)=3\cdot 4^{t-1}(l+d+1)-2$, at most $2\cdot 4^t$ segments before $S_{dl}[i]$ can overlap with E(i). Thus, $D(i,x(t))\le 2\cdot 4^t$ for all i’s, and since the upper bound is independent of i, the Koch curve is impossible to strictly draw.

Another example of Theorem  4 is the Minkowski curve. The Minkowski curve starts from a segment, then recursively alternates each line segment as follows:

• 1. Divide the line segment into four segments (we call these segment 1 to 4 from the start) of equal length.

• 2. Draw a square with segment 2 as a side to the left of the original segment, and the other square with segment 3 as a side to the right.

• 3. Remove segments 2 and 3.

Using the L-system, the Minkowski curve can be encoded as follows:

• Variable: F

• Constants: $+,-$

• Axiom: F

• Production Rule: $F\rightarrow F+F-F-FF+F+F-F$,

where F denotes a segment, − denotes $90^\circ$ right turn and $+$ denotes $90^\circ$ left turn. Figure 13 illustrates the Minkowski curve after three iterations.

Fig. 13

The Minkowski curve after three iterations

For the Minkowski curve case, since the oritatami system works on the triangular lattice, we assume that the Minkowski curve is slanted to fit into the triangular lattice—a square in the square lattice is mapped into a rhombus in the triangular lattice. We assume the followings for drawing the Minkowski curve:

• 1. The (tilted) Minkowski curve consists of an infinite sequence of alternating points and segments on the square lattice $\Lambda _c$. We use a parallelogram $S_l$ of width d and length l to represent a segment on the curve, and a rhombus $S_d$ of side length d to represents a point on the curve. The oritatami system starts with covering the first $S_d$, and denote the ith $S_d$ ($S_l$) by $S_d[i]$ ($S_l[i]$).

• 2. We use constant numbers of beads for a connecting line and a point—$p_d$ beads for $S_d$, and $p_l$ beads for $S_l$.

We observe the property of the curve based on self-similarity (Fig. 14). For a given t, let $q_1$ be the starting point of a periodic substructure of length $8^t$, and $q_2$ be the ending point. Points $q_1$ and $q_2$ should be $4^t$ unit distance away. Now, suppose we draw the square of size $2\cdot 4^t$ with the center $q_2$. Then, the point $q_3$ that appears first in the square (including the boundary) is at most $8^{t{+}1}$ segments away from $q_2$.

Fig. 14

Properties of the curve when $t=1$. $q_3$ is 64 segments away from $q_2$

Similar to the proof for Theorem 1, let $x(t)=4^t(l+d+2)-l-2$. For $x(t{-}1)<\delta \le x(t)$, the event horizon context for beads in $S_{dl}[i]$ covers only $S_d$’s which are within $4^t$ unit distances from $S_d[i]$ (see Fig. 15). Then, at most $8^{t{+}1}$ segments before $S_{dl}[i]$ can overlap with E(i), and $D(i,x(t))\le 8^{t{+}1}$. Since the upper bound is independent of i, the Minkowski curve is impossible to strictly draw.

Fig. 15

Case analysis when $t=1$. The event horizon context E(i) for beads in $S_{dl}[i]$ is drawn in a red polygon, which is the union of event horizon contexts of points denoted by dots. All $S_d$’s and $S_l$’s that overlap with E(i) are depicted

6 Conclusions

The oritatami system is a computational model inspired by RNA cotranscriptional folding, where an RNA transcript folds upon itself while synthesized out of a gene. Since the oritatami system is a geometric computation model, it is natural to consider the problem of constructing fractal curves using the oritatami system. We have formally defined the strict drawing of the curve by an oritatami system. Then we have proved that it is impossible to strictly draw two infinite fractal curves (Koch curve and Minkowski curve) by a cyclic oritatami system. Moreover, we have proposed sufficient conditions that make the strict folding of general infinite curves impossible.

Fig. 16

Implementation of a self-touching point in the Heighway dragon (Masuda et al. 2018). A point in the curve is partitioned into $3\times 3$ rhombi colored in red

It is open to fill the gap between this impossibility result about strict drawing and possibility about weak drawing (Pchelina et al. 2020). In Theorem  1, we have calculated the maximum length of the curve that affects bead stabilization, which turns out to be constant for an arbitrary segment on the curve. This property is caused by “sparseness” of the curve without self-touching. For self-touching curves, we can implement such self-touching points by partitioning each point into a number of shapes as in Fig. 16. Such technique can be extended to implement planar fractal structures such as Sierpinski Triangles by drawing a (self-touching) Eulerian path of the grid graph that correspond to the given structure. Still, it is open whether we can strictly draw self-touching curves infinitely by oritatami—for example, $D_{i,n}$ of the Heighway dragon grows linear to i, which fails the condition of Theorem 2.

In general, information propagation of oritatami systems is local, since a system can probe an event horizon of the fixed size at a time. Such limitation is independent of strictness or weakness of structure drawing. On the other hand, construction of fractal structures often requires distant information propagation for each point to be drawn. We can detour such long-distance propagation by an incremental counter and a function that defines the behavior of the fractal according to the count (Masuda et al. 2018). However, such counter (with a finite size) cannot be infinite, which determines finiteness of Heighway dragon drawing. There are a few fractal structures that can be implemented using a set of local information propagation rules, such as Sierpinski triangles using Rule 90 (Wolfram 2002). We assume that except for these rare fractals, it is impossible to strictly or even weakly draw fractals using a cyclic oritatami systems.