On the Power of Oritatami Cotranscriptional Folding with Unary Bead Sequence

Abstract

An oritatami system is a novel mathematical model of RNA cotranscriptional folding, which has recently proven extremely significant in information processing in organisms and also controllable artificially in a test tube to construct an artificial structure by folding an RNA sequence. This model has turned out to be Turing universal. One next step is to simplify the Turing universal oritatami system and another is to characterize weaker oritatami systems as we may not need Turing universality for applications. In this paper, we look at oritatami systems that folds a unary sequence, and show that under reasonable assumptions, these systems are not universal.

This work is supported in part by KAKENHI Grant-in-Aid for Challenging Research (Exploratory) No. 18K19779 granted to S. Z. F. and S. S. and JST Program to Disseminate Tenure Tracking System No. 6F36 granted to S. S.

1 Introduction

Transcription is the first essential step of gene expression, in which a DNA template sequence is copied into a single stranded RNA sequence of nucleotides A, C, G, and U (letter of RNA alphabet) by a ‘molecular Xerox’ called RNA polymerase, nucleotide by nucleotide according to the complimentarity relation $\mathtt{A} \rightarrow \mathtt{U}$, $\mathtt{G} \rightarrow \mathtt{C}$, $\mathtt{C} \rightarrow \mathtt{G}$, and $\mathtt{T} \rightarrow \mathtt{A}$. The copied RNA sequence is called transcript. The transcript does NOT remain single-stranded until it is fully synthesized. It rather starts folding upon itself into intricate stable conformations (structures) primarily via hydrogen bonds, immediately after it emerges from the polymerase, as illustrated in Fig. 1 (Left).

Fig. 1.

(Left) RNA origami. (Right) an abstraction of its product, i.e., an RNA tile, as a configuration of an oritatami system. A dot $\bullet$ in the figure on the right represents a sequence of 3-4 nucleotides (oligonucleotides). The solid arrow and dashed lines represent respectively its RNA transcript and interactions based on hydrogen bonds between nucleotides.

In a recent breakthrough in molecular engineering by Geary, Rothemund and Andersen [8] the co-transcriptional folding of RNA is controlled by careful design of the DNA template. As demonstrated in laboratory, this method, called RNA Origami, makes it possible to cotranscriptionally self-assemble a unique RNA rectangular tile highly probably (see Fig. 1 (Left)). This breakthrough and the design of RNA tile has encouraged the research on the nano-scale RNA structure self-assembly so that several successful attempts to self-assemble artificial structures by folding a single-stranded RNA sequence [4, 10]. Geary et al. [6] proposed a mathematical model for this process, called oritatami system. In this model, an oligonucleotide (a short sequence of RNA nucleotides) is considered to be a bead and an RNA structure is abstracted as a directed path with information on hydrogen-based interaction (bonds) between beads over the triangular grid graph $\mathbb {T}$ as illustrated in Fig. 1. An oritatami system folds a transcript of abstract molecules (beads) of finite number of types over $\mathbb {T}$. This model has been just proved efficiently Turing universal in [7] by simulating cyclic tag systems introduced by Cook [2]. The simulation involves a very large and complex oritatami system. This system is deterministic in the sense that every bead is stabilized uniquely point-wise as well as interaction-wise (for the formal definition, see Sect. 2). One future direction of research is to quest for a smaller Turing-universal oritatami system.

Closely related is the question of where not to look for universal systems, i.e., what are the limitations of simple oritatami system. In search for simple oritatami systems, there are a number of restrictions one can pose on them:

• bounds on the relative speed of transcription to folding (delay), the number of bead types, or the number of hydrogen bonds per bead (arity);

• bounds on the length of the transcript or on the complexity of rules to decide what types of beads interact with each other (attraction rules);

• structural conditions on the transcript or the attraction rules.

In [3], Demaine et al. proved that at delay 1 and arity 1, upon an initial structure of n beads, a deterministic oritatami system cannot fold into any conformation of more than 10n beads, no matter how many bead types are available. We consider this finiteness problem for unary oritatami systems under various settings of the values of delay and arity, which is formalized as follows (Table 1).

Problem 1

Give an upper bound on the length of a transcript of a delay-$\delta$, arity-$\alpha$ deterministic unary oritatami system whose seed is of length n by a function in $\delta$, $\alpha$, and n.

Fig. 2.

The zig-zag conformation. This is the only one infinite conformation foldable deterministically by an unary oritatami system at delay 1 and arity 2.

Table 1. Upper bounds on the length of a conformation foldable by a deterministic unary oritatami system at delay $\delta$ and arity $\alpha$. At any combination of delay and arity without anything written, no upper bound is known yet.

In this paper, we will solve this problem completely at delay 1 and partially at arity 1 in Sect. 4. At delay 1, we will provide a quadratic upper bound $3n(n+1)+1$ for the case of arity being 4, while a linear upper bound $4n+14$ for arity 3. At the delay 1 and arity 2, one infinite structure turns out to be foldable deterministically, which is the zigzag conformation shown in Fig. 2. At arity 1, we will prove that at delay 2 or 3, the upper bound is $(3n+1)(n+1)$. Upper bounds for longer delays remain open. These results as well as known upper bounds are summarized in Fig. 1. As shown at the end of Sect. 2, the stabilization of the first t beads of transcript by a deterministic oritatami system can be simulated by a deterministic Turing machine within $t^3$ steps (Corollary 1). Thus, the above mentioned upper bounds show that at delay 1 and arity 1, 3, or 4, or at delay 2 or 3 and arity 1, the class of deterministic unary oritatami systems is not Turing universal. The Turing universal oritatami system by Geary et al. [7] employs more than 500 types of beads. Thus, this weakness result is not surprising at all. The unary oritatami system might not be practical very much, though one bead may abstract an oligonucleotide (a short sequence of nucleotides), and in that case, unary transcript can be a repetitive but nonunary sequence, which is not so unrealistic in experiments (see [5]). Nevertheless, this paper makes a first considerable step towards the characterization of non-Turing-universal oritatami systems.

As a result of independent significance, in Sect. 3, we show that increasing the delay from 1 to 2 enables an oritatami system to yield a conformation of quadratic length in n as long as 9 types of beads are available.

2 Preliminaries

Let $\varSigma$ be a finite set of types of abstract molecules, or beads. A bead of type $a \in \varSigma$ is called an a-bead. By $\varSigma ^*$ and $\varSigma ^\omega$, we denote the set of finite sequences of beads and that of one-way infinite sequences of beads, respectively. The empty sequence is denoted by $\lambda$. Let $w = b_1 b_2 \cdots b_n \in \varSigma ^*$ be a sequence of length n for some integer n and bead types $b_1, \ldots , b_n \in \varSigma$. The length of w is denoted by |w|, that is, $|w| = n$. For two indices i, j with $1 \le i \le j \le n$, we let w[i..j] refer to the subsequence $b_i b_{i+1} \cdots b_{j-1}b_j$; if $i = j$, then w[i..i] is simplified as w[i]. For $k \ge 1$, w[1..k] is called a prefix of w.

Oritatami systems fold their transcript, which is a sequence of beads, over the triangular grid graph $\mathbb {T} = (V, E)$ cotranscriptionally. We designate one point in V as the origin O of $\mathbb {T}$. For a point $p \in V$, let denote the set of points which lie in the regular hexagon of radius d centered at the point p. Note that consists of $3d(d+1)+1$ points. A directed path $P = p_1 p_2 \cdots p_n$ in $\mathbb {T}$ is a sequence of pairwise-distinct points $p_1, p_2, \ldots , p_n \in V$ such that $\{p_i, p_{i+1}\} \in E$ for all $1 \le i < n$. Its i-th point is referred to as P[i]. Now we are ready to abstract RNA single-stranded structures in the name of conformation. A conformation C (over $\varSigma$) is a triple (P, w, H) of a directed path P in $\mathbb {T}$, $w \in \varSigma ^*$ of the same length as P, and a set of h-interactions $H \subseteq \bigl \{\{i, j\} \bigm | 1 \le i, i+2 \le j, \{P[i], P[j]\} \in E \bigr \}$. This is to be interpreted as the sequence w being folded along the path P in such a manner that its i-th bead w[i] is placed at the i-th point P[i] and the i-th and j-th beads are bound (by a hydrogen-bond-based interaction) if and only if $\{i, j\} \in H$. The condition $i+2 \le j$ represents the topological restriction that two consecutive beads along the path cannot be bound. The length of C is defined to be the length of its transcript w (that is, equal to the length of the path P). A rule set $R \subseteq \varSigma \times \varSigma$ is a symmetric relation over $\varSigma$, that is, for all bead types $a, b \in \varSigma$, $(a, b) \in R$ implies $(b, a) \in R$. A bond $\{i, j\} \in H$ is valid with respect to R, or simply R-valid, if $(w[i], w[j]) \in R$. This conformation C is R-valid if all of its bonds are R-valid. For an integer $\alpha \ge 1$, C is of arity $\alpha$ if it contains a bead that forms $\alpha$ bonds but none of its beads forms more. By $\mathcal {C}_{\le \alpha }(\varSigma )$, we denote the set of all conformations over $\varSigma$ whose arity is at most $\alpha$; its argument $\varSigma$ is omitted whenever $\varSigma$ is clear from the context.

The oritatami system grows conformations by an operation called elongation. Given a rule set R and an R-valid conformation $C_1 = (P, w, H)$, we say that another conformation $C_2$ is an elongation of $C_1$ by a bead $b \in \varSigma$, written as $C_1 \xrightarrow {R}_b C_2$, if $C_2 = (P p, wb, H \cup H')$ for some point $p \in V$ not along the path P and set $H' \subseteq \bigl \{ \{i, |w|+1\} \bigm | 1 \le i < |w|, \{P[i], p\} \in E, (w[i], b) \in R \bigr \}$ of bonds formed by the b-bead; this set $H'$ can be empty. Note that $C_2$ is also R-valid. This operation is recursively extended to the elongation by a finite sequence of beads as: for any conformation C, $C \xrightarrow {R}_\lambda ^* C$; and for a finite sequence of beads $w \in \varSigma ^*$ and a bead $b \in \varSigma$, a conformation $C_1$ is elongated to a conformation $C_2$ by wb, written as $C_1 \xrightarrow {R}_{wb}^* C_2$, if there is a conformation $C'$ that satisfies $C_1 \xrightarrow {R}_w^* C'$ and $C' \xrightarrow {R}_b C_2$.

An oritatami system (OS) $\varXi = (\varSigma , R, \delta , \alpha , \sigma , w)$ is composed of

• a set $\varSigma$ of bead types,

• a rule set $R \subseteq \varSigma \times \varSigma$,

• a positive integer $\delta$ called the delay,

• a positive integer $\alpha$ called the arity,

• an initial R-valid conformation $\sigma \in C_{\le \alpha }(\varSigma )$ called the seed, whose first bead is assumed to be at the origin O without loss of generality,

• a (possibly infinite) transcript $w \in \varSigma ^* \cup \varSigma ^\omega$, which is to be folded upon the seed by stabilizing beads of w one at a time so as to minimize energy collaboratively with the succeeding $\delta {-}1$ nascent beads.

The energy of a conformation $C = (P, w, H)$, denoted by $\varDelta G(C)$, is defined to be ${-}|H|$; the more bonds a conformation has, the more stable it gets. The set $\mathcal {F}(\varXi )$ of conformations foldable by the system $\varXi$ is recursively defined as: the seed $\sigma$ is in $\mathcal {F}(\varXi )$; and provided that an elongation $C_i$ of $\sigma$ by the prefix w[1..i] be foldable (i.e., $C_0 = \sigma$), its further elongation $C_{i+1}$ by the next bead $w[i+1]$ is foldable if

$$\begin{aligned} C_{i+1} \in \mathop {\text {arg min}}\limits _{ \begin{array}{c} C \in \mathcal {C}_{\le \alpha } s.t. \\ C_i \xrightarrow {R}_{w[i+1]}C \\ \end{array} } \min \Bigl \{ \varDelta G(C') \Bigm | C \xrightarrow {R}^*_{w[i+2...i+k]}C', k\le \delta , C' \in \mathcal {C}_{\le \alpha } \Bigr \}. \end{aligned}$$

(1)

Then we say that the bead $w[i+1]$ and the bonds it forms are stabilized according to $C_{i+1}$. The easiest way to understand this stabilization process should be the video available at https://www.dailymotion.com/video/x3cdj35, in which the Turing universal oritatami system by Geary et al. [7], whose delay is 3, is running. Note that an arity-$\alpha$ oritatami system cannot fold any conformation of arity larger than $\alpha$. A conformation foldable by $\varXi$ is terminal if none of its elongations is foldable by $\varXi$. The oritatami system $\varXi$ is deterministic if for all $i \ge 0$, there exists at most one $C_{i+1}$ that satisfies (1). A deterministic oritatami system folds into a unique terminal conformation. An oritatami system with the empty rule set just folds into an arbitrary elongation of its seed nondeterministically. Thus, the rule set is reasonably assumed non-empty.

In this paper, we considerably focus on the unary oritatami system. An oritatami system is unary if it involves only one type of bead, say a, that is, $\varSigma = \{a\}$. Its rule set is $R = \{(a, a)\}$. Its transcript is a sequence of a-beads so that nothing can be hardcoded on it.

Proposition 1

For any rule set R, arity $\alpha$ and conformation $C = (P,w,H)$ it is possible to check whether C is R-valid and whether $C\in \mathcal {C}_{\le \alpha }$ in time $\mathcal {O}(|H|\cdot |w|\cdot |R|)$.

Proof

To check whether C is R-valid:

• 1. FOR each $(i,j)\in H$:

• 2.         IF $(w[i],w[j])\notin R$ THEN answer NO and HALT

• 3. answer YES and HALT.

Checking the condition in 2. can be done in $\mathcal {O}(|w|\cdot |R|)$ time for any reasonable representation of w and R, hence the whole process takes $\mathcal {O}(|H|\cdot |w|\cdot |R|)$ time. To check the arity constraint $C\in \mathcal {C}_{\le \alpha }$:

• 1. FOR each $i\in \{1,\dots ,|w|\}$:

• 2.         IF $\mathrm {degree}(i)=|\{j | (i,j)\in H \}|>\alpha$ THEN answer NO and HALT

• 3. answer YES and HALT.

Checking the condition in 2. can be done in $\mathcal {O}(|H|)$ time for any reasonable representation of H, hence the whole process takes $\mathcal {O}(|w|\cdot |H|)$ time.    $\square$

Theorem 1

There is an algorithm that simulates any deterministic oritatami system $\varXi = (\varSigma , R, \delta , \alpha , \sigma , w)$ in time $2^{\mathcal {O}(\delta )}\cdot |R|\cdot |w|$.

Proof

Take any step in the computation, up to which some $i \ge 0$ first beads of w have been stabilized, with the last bead at a point p. The number of all possible elongations of the current conformation by the next $\delta$-beads is $(6 \times 5^{\delta -1}) \times ((2^4)^{\delta -1} \times 2^5) \in 2^{O(\delta )}$. By Proposition 1, we can check for each of these elongations whether its arity is at most $\alpha$ or not and whether it is R-valid or not in time $\mathcal {O}((2^4)^{\delta -1}\cdot 2^5\cdot \delta \cdot |R|)=2^{\mathcal {O}(\delta )}\cdot |R|$. Therefore, the total running time is $2^{\mathcal {O}(\delta )}\cdot |R|\cdot |w|$.    $\square$

Corollary 1

For fixed $\delta$, the class of problems solvable by deterministic oritatami systems $(\varSigma , R, \delta , \alpha , \sigma , w)$ is included in $\mathrm {DTIME}(|w|^3)$.

Proof

The claim follows from Theorem 1 and the fact that |R| is implicitly bounded by $|w|^2$.    $\square$

Considering the following decision problem: given an oritatami system, integer i, and a point p, decides whether the bead w[i] is stabilized at p. By Corollary 1, this problem is in $\mathrm {P}$ for a fixed delay $\delta$. Because of the time hierarchy theorems, we know that $\mathrm {P}\subsetneq \mathrm {EXP}$ (see, e.g., [1]), so we can conclude that OS which cannot deterministically fold transcripts of length exponential in the length of the seed are not computationally universal.

3 Quadratic Lower Bound for Delay 2, Arity 1

First we present a lower bound construction for arity 1 systems. At $\alpha =1$, having delay $\delta =2$ allows the deterministic folding of quadratic length transcripts compared with $\delta =1$, where, as stated before, the maximum length is linear in the length of the seed. We demonstrate this with an infinite family of OS, which fold deterministically a transcript of length $\frac{(n-1)^2}{4}$ starting from a given seed of length n.

Fig. 3.

Quadratic length transcript folding deterministically into pyramid shape. Seed: thick black path. Transcript: thin blue path. Bonds: dashed red lines. (Color figure online)

Consider the following $\delta =2$, $\alpha =1$ system with bead types $\{0,1,\dots ,8\}$ and attraction rules $\{(i,i) \mid 1\le i\le 8\}$. Let the seed $\sigma$ be a conformation of a $4k+1$ long bead sequence of the form $(10205060)^{k/2}0$ and $(10205060)^{(k-1)/2}(1020)0$, for k even and odd, respectively. Bead $\sigma [i]$ of the seed is stabilized at point (i, 0), for all $1\le i\le 4k-1$. Bead 4k is at $(4k-1,-1)$ and bead $4k+1$ is at (4k, 0).

The transcript is $w=\mathrm {row}_1\cdots \mathrm {row}_{2k}$, where

• $\mathrm {row}_1=(24136857)^{(k-1)/2}241$ if k is odd, and $\mathrm {row}_1=(68572413)^{k/2-1}6857241$ if k is even;

• $\mathrm {row}_{i+1}=(\mathrm {row}_i[2..|\mathrm {row}_i|-1])^r$ for $i\in \{1,\dots , 2k-1\}$, where $w^r$ is the reverse of w. In other words, each row is the reverse of the previous without its first and last bead.

The transcript above is written in rows which correspond to beads in the conformation stabilized along the same row on the grid. To simplify the argument we will use row both for the transcript above and for the conformation it stabilizes in (note that in the figure the row index grows from bottom to top).

Row 1 is of length $4k-1$ and row $\ell +1$ is two beads shorter than row $\ell$, so the length of the whole transcript is $|w|=4k^2=\frac{(4k\,+\,1\,-\,1)^2}{4}=\frac{(|\sigma |\,-\,1)^2}{4}$. As an example, see Fig. 3, where $k=5$, so the length of the seed is $4k+1=21$ and the transcript is $4k^2 = 100$ beads long.

Stabilizing the first bead of a row goes by binding to the penultimate bead of the previous row, as they are of the same type according to how we constructed the transcript, and they have free hands (see Fig. 5).

As for the other beads, in rows $j\equiv 1,3\mod 4$, beads of type 1, 2, 5, 6 bind to a bead in row $j-1$. In rows $j\equiv 2,4\mod 4$ beads of type 3, 4, 7, 8 can bind to a bead in row $j-1$. This is true for row 1, because beads of type 1, 2, 5, 6 from row 1 can only bind to every second bead of the seed, whereas the other beads of row 1 cannot bind to anything (Fig. 4, (c)). Once this dynamic holds for a row, it holds inductively for the next, as a bead that binds to another loses its only free hand at arity 1.

Within one row of the transcript, no bead i can bind to a preceding bead, because if there is a previous bead of the same type in that row, it is stabilized at a distance of at least 6 from any point where i could be placed.

By the arguments above, the beads in row i of the transcript are stabilized along row i on the grid, forming the pyramid-like conformation from Fig. 3.

Fig. 4.

Fixing transcript beads in first row, when k is odd

Fig. 5.

Beads $4k, 8k-2, \dots$ stabilize at turning points because the bead two positions before is the same type and has a free hand.

4 Upper Bounds for Determinisitc Unary Oritatami Systems at Delay 1 or Arity 1

In this section, we consider Problem 1 at delay 1 first and then at arity 1. Let $\varXi = (\varSigma , R, \delta , \alpha , \sigma , w)$ be a deterministic oritatami system of delay 1. For $i \ge 0$ let $C_i$ be the unique elongation of $\sigma$ by w[1..i], that is, foldable by $\varXi$. Hence $C_0 = \sigma$.

At delay 1, a bead cannot collaborate with its successors in order to stabilize itself. In fact, there are just two ways for a bead to get stabilized at delay 1 (or the bead has no place to be stabilized around so that the system halts), as observed in [3]. One is to be bound to another bead and the other is through a 1-in-1-out structure called the tunnel section. See Fig. 6. A tunnel section consists of one free point $p_c$ and four beads that occupy four neighbors of $p_c$. In order for an oritatami system to stabilize the bead w[i] at the central point $p_c$, its predecessor $w[i-1]$ must be put at one of the two free neighbors of p. Thus, at the stabilization of w[i], only one neighbor of p is left free so that the successor $w[i+1]$ is to be stabilized there, even without being bound. In this case, the point $p_e$ where $w[i-1]$ is stabilized is considered to be an entrance of the tunnel section and the point $p_s$ where $w[i+1]$ is stabilized is considered as its exit. A tunnel is a maximal set of tunnel sections whose central points form a path.

Fig. 6.

Tunnel sections of all possible three types: straight (Type S), obtuse turn (Type O), and acute turn (Type A).

Fig. 7.

A tunnel divides the world into two.

The behavior of an oritatami system at delay 1 can be described by a sequence of S of b (bound), $t_s$ (straight tunnel section), $t_o$ (obtuse-turn tunnel section), and $t_a$ (acute-turn tunnel section); priority is given to tunnel, that is, S[i] is $t_s$ (resp. $t_o$, $t_a$) if the i-th bead of the system is stabilized not only by being bonded but also through a straight (resp. obtuse-turn, acute-turn) tunnel section. Let us introduce t as a wildcard for $t_s$, $t_o$, and $t_a$. We also let S take the value $\blacksquare$ for halt (due to the lack of free neighbors).

We say that a neighbor of a point p is reachable from a conformation C if there exists an elongation of C in which a bead occupies the neighbor and it binds with a bead at p. For example, in Fig. 7, the transcript w is about to step into a tunnel. The wall beads $w[i-\ell ]$ and $w[i-k]$ are both older than the bead at the entrance, w[i]. Even if w[i] leaves a free neighbor, the neighbor is not reachable because the path of a conformation must be non-self-intersecting, and its subpath between these two wall beads divides the plane into two regions, one of which includes the entrance of the tunnel and the other of which includes the exit (Jordan curve theorem [9]). Taking this reachability into account, we define the binding capability of a conformation as the number of free bonds of its beads available geometrically for elongations of C. It is defined formally as follows:

Definition 1

(Binding Capability). Let $\alpha$ be an arity and $C = (P,w,H)$ be a conformation of arity at most $\alpha$. Let $H_k = H \cap \{ (i,j) \mid i=k{ or}j=k \}$. Moreover, let $R_k$ be a set of neighbors of the point P[k] that are free and reachable from C. The binding capability of C at arity $\alpha$, denoted by $\#bc_\alpha (C)$, is defined by $\sum ^{|w|}_{k=1} \min \{\alpha -|H_k|, |R_k|\}$. The subscript $\alpha$ is omitted whenever it is clear from context.

Observe one almost-trivial but important fact that a bead inside a tunnel does not increase the binding capability. This is because for such a bead w[k], $|R_k| = 0$.

We now prove that in “almost all” tunnels is a troll domiciled and robs the transcript of binding capability (the original story is from [11]). Originally, we tried to find a troll in every tunnel but failed; a troll seems to dislike the very first bead w[1], or its property that only $\alpha$+1 beads around may take all hands of w[1] thanks to the absence of its predecessor; any other bead must be surrounded by at least $\alpha +2$ beads in order to be free from free hand because a bead cannot bind with its predecessor or successor. We call a bead singular if it is surrounded by only $\alpha +1$ beads but forms $\alpha$ bonds. No bead but w[1] can be singular because of their predecessor and successor. A tunnel is singular if its entrance or exit is next to w[1] that is singular. There can be at most 3 tunnels around one bead so that no more than 3 tunnels can be singular. A singular tunnel will be denoted with the superscript $\times$ like $t_s^\times$ or $t^\times$. In contrast, the notation without $\times$ such as $t_s$ and t shall imply their non-singularity.

Theorem 2

(Tunnel Troll Theorem). Let $\varXi$ be a deterministic unary oritatami system of delay $\delta = 1$. The following statements hold.

• 1. At arity $\alpha \ge 3$, if $S[i] = t$ (i.e. the tunnel that stabilizes w[i] is not singular) and $S[i+1] \ne \blacksquare$, then $\#bc(C_{i-1}) > \#bc(C_i)$.

• 2. At arity $\alpha = 2$, if m is the number of occurrences of bt as a factor in S[1..k] for an index k, then $\#bc(C_{0}) - m \ge \#bc(C_{k})$.

In order to prove this theorem, we use the following three lemmas.

Lemma 1

Let $\varXi$ be a deterministic unary oritatami system at delay $\delta = 1$ and arity $\alpha =2$. Assume $\varXi$ stabilizes the transcript until $w[i-1]$. If $S[i+1] = b$ and $S[i+2] \in \{ t_s, t_o \}$, then $\#bc(C_{i-1}) > \#bc(C_{i})$.

Proof

See Fig. 8. $S[i+2] \in \{ t_s, t_o \}$ means that $w[i+2]$ is stabilized by a tunnel section of type S or O. Thus, its predecessor $w[i+1]$ must be inside the tunnel section, that is, $n_1$ and $n_2$ must be occupied. Free bonds of w[i], if any, cannot be used in future by another bead w[j] because otherwise the part of transcript w[i..j] and the bond between w[i] and w[j] would form a closed curve and the curve would cross the path of $C_{i-1}$ between $n_1$ and $n_2$, contradiction. Therefore, if w[i] forms a bond at its stabilization $\#bc(C_{i-1}) > \#bc(C_{i})$ holds. We now prove that w[i] must form a bond.

Suppose w[i] were stabilized without any bond, that is, by a tunnel. For that the two points that are a neighbor of both $w[i-1]$ and w[i] must be occupied already. In addition, at least one of the neighbors of w[i] must be free because $S[i+1] = b$. Thus, only the case to be considered is Fig. 8 (middle) with $n_5$ being occupied (that is, $n_4$ is free). In this case, before w[i] is stabilized, at lest three neighbors of $n_2$ were free and hence, a bead at $n_2$ was provided with one free bond and could form a bond with w[i].    $\square$

Fig. 8.

The three ways to enter a tunnel: (Left) straight, (Middle) obtuse, (Right) acute. The bead w[i] is stabilized at the entrance and $w[i+1]$ is stabilized inside.

Fig. 9.

Two kinds of exit of a tunnel: (Left) Both $n_1$ and $n_2$ are free, (Right) One of $n_1$ and $n_2$ is occupied.

Lemma 2

Let $\varXi$ be a deterministic unary oritatami system of delay $\delta = 1$ and arity $\alpha =2$. If $S[i+1..j+1] = bt^{(j-i-1)}b$ for some i, j with $i \le j-2$ and $S[j] \in \{ t_s, t_o\}$, then $\#bc(C_{j-2}) \ge \#bc(C_j)$, and hence, $\#bc(C_{i}) \ge \#bc(C_j)$. If $i \le j-3$, then the second inequality is strengthened as $\#bc(C_{i}) > \#bc(C_{j})$.

Proof

Since the binding capability never increases inside a tunnel, we just need to consider the exit of a tunnel. See Fig. 9. At least one of points $n_1$ or $n_2$ must be free because otherwise w[j] would be inside of a tunnel, that is, $S[j+1]$ would not be b.

Let m be the number of bonds $w[j-1]$ forms, that is, $\#bc(C_{j-2}) - \#bc(C_{j-1}) = m$. We claim $\#bc(C_{j}) - \#bc(C_{j-1}) \le m$. Indeed, if both $n_1$ and $n_2$ are free (see Fig. 9), the predecessor $w[j-1]$ must be bound to both beads at $n_3$ and at $n_4$ because both of them still have a free hand. Hence, $m \ge 2$. Since $\#bc(C_{j}) - \#bc(C_{j-1})$ is less than the arity, this difference is at most m.

If $n_1$ is occupied, then $n_2$ is free. The predecessor $w[j-1]$ must be bound $n_4$. Hence, $m \ge 1$. The bead w[j] can increase the binding capability at most by 1 because one of its free neighbors would, $n_0$ or $n_2$, is to be occupied by the successor $w[j+1]$. Therefore, $\#bc(C_{j}) - \#bc(C_{j-1}) \le m$.

Thus, $\#bc(C_{j-2}) \ge \#bc(C_j)$, and hence, $\#bc(C_{i}) \ge \#bc(C_j)$. If $i \le j-3$, then the second inequality is strengthened as $\#bc(C_{i}) > \#bc(C_{j})$ because $S[i+1] = b$, that is, $\#bc(C_{i}) > \#bc(C_{i+1})$ and $\#bc(C_{i+1}) \ge \#bc(C_j)$.    $\square$

Fig. 10.

The bead $w[i+2]$ is stabilized by a tunnel of type A. (Right) Moreover $S[i] = t_a$.

Lemma 3

Let $\varXi$ be a deterministic unary oritatami system of delay $\delta = 1$ and arity $\alpha = 2$. If $S[i+2] = t_a$, the following statements hold.

• 1. If w[i] forms at least one bond, $\#bc(C_{i-1}) > \#bc(C_{i+2})$.

• 2. If w[i] does not consume any bond and $S[i] \in \{t_s, t_o \}$, $\#bc(C_{i-2}) > \#bc(C_{i+2})$.

• 3. If w[i] does not consume any bond and $S[i] = t_a$, $\#bc(C_{i-3}) - 2 \ge \#bc(C_{i+2})$.

Proof

We consider each statement. First we prove Statement 1. The bead $w[i+1]$ consumes one hand and provides nothing. If w[i] forms two bonds, then even if $w[i+2]$ provides two free hands, $\#bc(C_{i-1}) > \#bc(C_{i+2})$. On the other hand, if it leaves a free hand, it will be used by $w[i+2]$, and hence, $w[i+2]$ does not increase the binding capability. Thus, $\#bc(C_{i-1}) > \#bc(C_{i+2})$. This argument actually work also for the case when w[i] is stabilized rather by binding.

Let us proceed to Statement 2. See Fig. 10. Consider the case when w[i] is stabilized by a tunnel section of type S or O. As prove in Lemma 2, $\#bc(C_{i-2}) \ge \#bc(C_{i})$. The bead w[i] leaves two free hand, it will be used by $w[i+2]$, and hence, $w[i+2]$ does not increase the binding capability. Thus, $\#bc(C_{i-2}) > \#bc(C_{i+2})$. This argument actually work also for the case when w[i] is stabilized rather by binding.

We finalize this proof by showing Statement 3. In order for w[i] not to bind, $w[i-2]$ must have already used up its hands. The bead $w[i-1]$ consumes one hand and provides nothing. Thus, $\#bc(C_{i-3}) - 1 \ge \#bc(C_{i})$. The bead $w[i+1]$ consumes one hand and provides nothing. Finally, $w[i+2]$ uses one hand of w[i], and hence, does not increase the binding capability. Therefore, $\#bc(C_{i-3}) -2 \ge \#bc(C_{i+2})$. This argument actually works also for the case when w[i] is stabilized rather by binding.    $\square$

Now we are ready to prove the Tunnel Troll Theorem.

Proof

Let us first consider cases of $\delta \ge 3, \alpha = 1$. See Fig. 9. Consider the stabilization of w[i]. This bead w[i], once stabilized, shares two neighbors with its predecessor $w[i-1]$, which are denoted by $n_3, n_4$. Both of them have been already occupied because $S[i] = t$.

Since $S[i+1] \ne \blacksquare$, at least one of the other three neighbors, denoted by $n_0, n_1, n_2$, must be free. Assume that in the neighborhood of w[i], there are two beads with one free neighbor even after w[i] is stabilized. Before the stabilization of w[i], such a bead had two free neighbors, and hence, is provided with at least one free bond. Thus, w[i] is to be bonded to these two beads, and it decreases the binding capability by at least 1. It now suffices to check that this assumption holds no matter how $n_0, n_1, n_2$ are occupied as long as at least one of them is left free.

Next, we consider the case of $\delta = 2, \alpha = 1$. We assume there are indices i, j such that $S[i\,+\,1..j\,+\,1] = bt^{(j-i-1)}b$. If $S[i+2]$ is $t_s$ or $t_o$, then Lemma 1 implies $\#bc(C_{i-1}) > \#bc(C_{i})$ and Lemma 2 implies $\#bc(C_{i}) \ge \#bc(C_{j})$. Thus, binding capability decreases by 1 per a factor $bt_s$ or $bt_o$.

Now, we assume $S[i+2] = t_a$. Then, we have to make sure that one troll is not double-counted. If w[i] forms a bond, Lemmas 2 and 3 imply that binding capability decreases through this tunnel.

Assume w[i] forms no bond. If $S[i] \in \{t_s, t_o\}$, Lemmas 2 and 3 imply $\#bc(C_{i-2}) > \#bc(C_{i+2})$. Observe that the bead $w[i-1]$ is at the entrance of the previous tunnel or inside. It is when a bead is stabilized at the entrance of a tunnel that the troll of the tunnel decreases binding capability. Thus, the inequality does not rely on the troll of previous tunnel. If $S[i] = t_a$, Lemma 3 implies $\#bc(C_{i-3}) - 2 \ge \#bc(C_{i+2})$. This inequality involves two tunnels but its difference 2 enables us to consider that binding capability decreases by 1 through this tunnel.    $\square$

4.1 Upper Bounds on the Length of Conformation Foldable Deterministically at Delay $\delta = 1$

Theorem 3

($\delta = 1, \alpha = 4$). The terminal conformation of a deterministic unary oritatami system of $\delta = 1, \alpha = 4$ is of length at most $3n^2 + 3n + 1$.

Proof

Consider the moment when a bead, say b, is stabilized outside for the first time. The bead must be bound a bead at the periphery of as depicted in Fig. 11. In order to avoid nondeterminism, the bead b must not be attracted anyhow else by beads around.

The point $p_1$ must be empty because a bead there would have at least two free neighbors and hence is provided with a free hand. If there is a bead at $p_2$, n must be at least 2 so that the bead is not singular. Since $p_1$ is empty, this bead has at least one free hand, a contradiction. Thus, $p_2$ must be also empty. In the same way, we can easily show that the point $p_3$ must not be occupied by a non-singular bead. Suppose $p_3 = O$. The point $p_4$ must not be empty; otherwise the singular bead, at O, would have a free hand. However, then a bead at $p_4$ would be provided with a free hand, a contradiction.    $\square$

Fig. 11.

The first bead out of

Theorem 4

($\delta = 1, \alpha = 3$). The terminal conformation of a deterministic unary oritatami system of $\delta = 1, \alpha = 3$ is of length at most $4n + 14$.

Proof

In this proof, we shall verify the claim that when the bead w[i] is stabilized with $S[i] = b$ and $S[i+1] \ne \blacksquare$, if the circle of radius 2 centered at its predecessor $w[i-1]$ is free from the singular point, then w[i] must form at least 2 bonds. Recall that the circle of radius 2 centered at the origin O, where the only candidate of singularity is, consists of 19 points including O. In order for the bead at O to be singular, its $\alpha +1 = 4$ neighbors must be occupied. This means that there are at most 14 points where a bead find a singular bead within 2 points. Therefore, the claim, once proved, and the Tunnel Troll Theorem imply that all but at most 14 beads strictly decrease the binding capability. The binding capability of the seed is at most 3n. Consequently, this theorem holds.

Now let us verify the claim. Suppose w[i] were stabilized by just one bond. There are three cases to be considered as depicted in Fig. 12, depending on the relative position of w[i] to $w[i-2]$ and $w[i-1]$. Since $S[i] = b$, at least one of the four neighbors of $w[i-1]$ must be empty. If $n_3$ is free, then $w[i-2]$ must have used up all of its hands; otherwise, w[i] would be stabilized also at $n_3$ nondeterministically, a contradiction. Thus, $\alpha + 2 = 5$ neighbors of $w[i-2]$, that is, all of its neighbors, must be occupied. Hence, $n_5$ is occupied. (All the remaining arguments are based on this “merry-go-round” occupation. This works only if the circle of radius 2 around $w[i-1]$ is free from the singular bead). In the same way, all the neighbors of $n_3$ turned out to be occupied in the clockwise order, but eventually, we would encounter a neighbor that is adjacent to also the point where w[i] is supposed to go. Thus, $n_3$ must be occupied (in the left and middle cases). In the left case, $n_4$ is symmetric to $n_3$, and hence, it must be occupied, too. Since $S[i] = b$, $n_1$ or $n_2$ must be free; assume $n_1$ is. Going clockwise around $n_1$ implies that $n_{-1}$ is occupied, but the bead at $n_1$ has a free hand and would cause a nondeterminism.

Let us focus on the remaining cases: middle and right. Suppose that among the 5 neighbors of w[i] at which $w[i-1]$ is not, only one can be occupied. Otherwise, a bead without any hand is found at one of them, and staring from the point, merry-go-round occupies all the neighbors, but then $w[i+1]$ would lose its way to go. In the middle case, this means $n_0$ is free. Since $n_{-1}$ is free, so must be $n_2$. Repeating this, we get that both $n_4$ and $n_5$ are free, but then $w[i-2]$ would have a free hand and a free neighbor, attract w[i], and cause a nondeterminism. Even in the right case, the points $n_1, n_0, n_2, n_4$ turn out to be free one after another likewise, but then $w[i-2]$ would have a free hand and neighbor, a contradiction.    $\square$

Fig. 12.

All possible directions of w[i]: straight, obtuse, acute.

Fig. 13.

The moment when the transcript steps outside .

Theorem 5

($\delta = 1, \alpha =2$). A deterministic unary oritatami system of $\delta = 1, \alpha = 2$ can fold into an infinite conformation, but its transcript folds into the zig-zag conformation (Fig. 2) after its $(27n^2 + 9n +1)$-th bead.

Proof

We assume w[i] is the first bead stabilized outside . See Fig. 13. The next bead $w[i+1]$ is to be bound for stabilization. Hence, it goes to the west or to the east (Fig. 13). Once $w[i+2]$ is stabilized at p, the remaining transcript folds into the zig-zag conformation. In order to avoid this or nondeterminism, $w[i+2]$ must form two bonds; it thus decreases binding capability by 1. Until when a bead is stabilized outside , binding capability never increases because of arity being 2 and of the Tunnel Troll Theorem. This means that, only at most $\#bc(C_0) \le 2n$ times we can thus expand that hexagonal region. In other words, outside the transcript cannot help but fold zig-zag.    $\square$

4.2 Quadratic Upper Bounds for Arity 1 and Delay 2 or 3

In this section we will argue that unary systems at arity 1 and delay 2 and 3, respectively, cannot fold infinite transcripts deterministically. As we will see, in fact, the length of transcripts deterministically foldable by these systems has an upper bound quadratic in the length n of the seed. The main result is the following theorem, which is a direct consequence of Lemmas 4 and 5 which follow.

Theorem 6

($\delta \in \{ 2,3\}, \alpha = 1$). The terminal conformation of a deterministic unary oritatami system at arity $\alpha = 1$ and delay $\delta \in \{2,3\}$ is of length at most $3n^2+4n+2$.

Fig. 14.

and the position (1, 1) of the first bead fixed outside of it.

Let us fix some common starting points for Lemmas 4 and 5. Let the point where the first transcript bead was fixed be p. We will argue about the situation when the first bead is stabilized outside (a hexagon of radius n). Let this be the ith bead of the transcript. Without loss of generality, we can translate the origin (0, 0) to the coordinates of bead $i-1$ (which is still in ), and we can assume that bead i is fixed at (1, 1) (see Fig. 14).

Lemma 4

($\delta =2, \alpha =1$). The terminal conformation of a deterministic unary oritatami system of $\delta =2$ and $\alpha = 1$ is of length at most $3n^2+4n+2$.

Proof

In the elongation that places bead i at (1, 1) there are two possibilities.

• i forms a bond with a bead at (1, 0).

• i does not bond to anything and $i+1$ is at (2, 1) bonding with a bead at (2, 0). If there is no bead at (1, 0), then placing i at (1, 0) instead of (1, 1) results in the same number of bonds, leading to nondeterminism. Therefore, there has to be a bead at (1, 0) and it is inactive, otherwise it would bond to i. This is analogous to case 1. below, with the only difference being that the bond between (1, 1) and (1, 0) is missing.

  

Because of the above, we need only consider the case when i binds to a bead at (1, 0). The next bead, $i+1$, can be fixed at (2, 1) or at (0, 1) as all other possibilities result in nondeterministic behavior immediately, so we have two cases.

Case 1. bead $i+1$ is fixed at (2, 1) and can bond with a bead at (2, 0) (see Fig. 15). Now consider bead $i+2$. For $i+1$ to be fixed at (2, 1), $i+2$ needs to form a bond somewhere, otherwise $i+2$ could go to (2, 1) forming the bond with the bead at (2, 0) and there would be two conformations with the maximal 1 bond. The only possibility is that there is a bead at (3, 0) and $i+2$ can bond with it when placed at (3, 1). We can apply the same argument inductively: there is some $m\ge 0$ such that grid points $(\ell ,0)$ are occupied by beads with free hands, for all $\ell \in \{2,\dots ,2+m\}$, and there is no bead at $(3+m,0)$. Such an m exists, and it is not greater than n, because those beads are all stabilized along the same side of . Then, bead $i+\ell$ is fixed at $(\ell +1,1)$ and bonds with $(\ell +1,0)$. However, bead $i+2+m$ cannot be fixed anywhere, because $i+2+m$ and $i+3+m$ can only add one bond to the conformation, and that is possible either with $i+2+m \rightarrow (2+m,1)$, $i+3+m \rightarrow (3+m,1)$ or with $i+2+m \rightarrow (2+m,2)$, $i+3+m \rightarrow (2+m,1)$. Intuitively, when we reach a corner of the hexagon , the next bead of the transcript cannot deterministically stabilize, as depicted in Fig. 15. In this case, the size of the transcript which was deterministically stabilized is bounded by the size of plus the length of one side of , so by $(3n^2+3n+1)+(n+1)=3n^2+4n+2$.

Fig. 15.

When bead $i+2+m$ is fixed

Case 2. bead $i+1$ is fixed at (0, 1). This is only possible if

(a) there is an inactive bead at $(-1,0)$ and one with a free hand one at $(-2,0)$. This case is symmetrical to (1). there is no bead at $(-1,0)$, bead $i+1$ can bond with bead $i-1$ at (0, 0) and the bead $i+2$ can be placed at $(-1,0)$ where it can bond with $(-2,0)$, $(-2,-1)$ or $(-1,-1)$. This leads to nondeterminism, because placing bead i at $(-1,0)$ and bead $i+1$ at (0, 1) would yield two bonds, just as the original conformation.

(b) there is a bead at $(-1,0)$ and bead $i+1$ can bond with that or with bead $i-1$ at (0, 0). However, this means that placing bead i at (0, 1) at bead $i+1$ at (1, 1) creates the same number of hydrogen bonds, thus resulting in bead i not being placed deterministically.

Fig. 16.

When bead $i+1$ is fixed at (0,1)

Case 2.(a) gives the same upper bound as case 1. Cases 2.(b)-(c) give the smaller upper bound , thereby concluding the proof.    $\square$

Lemma 5

($\delta =3, \alpha =1$). The terminal conformation of a deterministic unary oritatami system of $\delta =3$ and $\alpha = 1$ is of length at most $3n^2+4n+2$.

Proof

We will argue similarly to the $\delta =2$ case: when we stabilize beads outside , we can only do so at points right next to one of the sides and even there only until we reach a corner. This yields the upper bound immediately.

As before, let us assume that the last bead stabilized within is at point (0, 0) and the next bead is the first to be stabilized outside at point (1, 1). Depending on whether bead $i-1$ at point (0, 0) has a free hand to form a bond or not, we distinguish two cases (similarly to Fig. 16).

Case 1. Bead $i-1$ at (0, 0) has a free hand. If the most stable conformation formed by beads $i, i+1, i+2$ adds only two bonds, it will be nondeterministic because there are at least two possibilities (see Fig. 19, except it starts from (0, 0) not (1, 1)). Therefore, it needs to make three new bonds to deterministically stabilize i. There are five possible cases in which beads $i, i\,+\,1, i\,+\,2$ can add three bonds, see Fig. 17. In the cases (b) and (e) in Fig. 17, there are beads having a free hand at (1, 0) and $(-1,0)$ already stabilized before bead $i-1$ is fixed at (0, 0). One of these two beads may be a predecessor of bead $i-1$, but at least one of them is not. When bead $i-1$ is fixed at (0, 0), it makes a bond with the one of these two beads which is not its predecessor. This means that it is impossible to have three beads at $(-1,0)$, (0, 0) and (1, 0), each with a free hand, when bead i is fixed, and consequently, cases (b) and (e) in Fig. 17 cannot occur. Case (d) in Fig. 17 becomes nondeterministic when bead i is fixed because bead i can be fixed at $(-1,0)$ and bond with $(-2,0)$, bead $i+1$ can be placed (0, 1) and bond with (0, 0) and bead $i+2$ can be placed (1, 1) and bond with (0, 1). If it makes three bonds once, such as (a) and (c) in Fig. 17, it will need to make three bonds forever to be deterministic. Similarly to case 1. in the previous section, cases (a) and (c) in Fig. 17 lead to nondeterministism eventually, when the transcript reaches a first corner of .

Fig. 17.

When beads $i, i+1, i+2$ make three hydrogen bonds (c) there is an inactive bead at $(-1,0)$. (d) there is no bead at $(-1,0)$.

Case 2. Bead $i-1$ at (0, 0) does not have a free hand.

• (i) First, let us assume that there is a bead at (1, 0) which has a free hand. If there is a bead at (1, 0) and beads $i, i+1, i+2$ add only two bonds, we instantly get nondeterministism as in Fig. 18. Hence, beads $i, i+1, i+2$ need to make three bonds to stabilize i, but if they make three hydrogen bonds, the situation is analogous to (a) and (c) in Fig. 17.

• (ii) Now consider when there is no bead at (1, 0) or there is one, but with no free hand. Let us discuss the moment after bead i is fixed outside . Now bead i has a free hand because it cannot bind to (1, 0). If beads $i+1, i+2, i+3$ can form only two bonds, it will be nondeterministic because there are at least two possible such conformations, as in Fig. 19. Hence, they need to form three bonds to deterministically stabilize, such as in Fig. 20. Case (a) in Fig. 20 becomes the same as case (a) in Fig. 17. Case (b) in Fig. 20 becomes nondeterministic already when bead i is fixed because bead i could also be fixed at (1, 0).

Fig. 18.

Two conformations when a bead at (1, 0) has a free hand.

Fig. 19.

Two conformations when a bead i at (1, 1) has a free hand

Fig. 20.

When beads $i+1, i+2, i+3$ make three hydrogen bonds (a) there is an inactive bead at (1, 0). (b) there is no bead at (1, 0).

We have shown that at $\alpha =1$ and $\delta \in \{2,3\}$, unary oritatami systems can only fold finite length transcripts deterministically, and the length of that transcript is bounded by the size of the regular hexagon of radius n plus the length of one side of the surrounding hexagon. This gives us the upper bound , where n is the length of the seed, concluding the proof of Theorem 6.

5 Conclusion

In this work, we have considered unary oritatami systems at $\delta = 1$ or $\alpha = 1$. As a result, we found that a unary oritatami system does not have Turing universality at $\delta = 1$ and at $\delta \le 3$, $\alpha = 1$. This non-Turing universality was obtained by the following results. One is that unary oritatami systems are not able to make any infinite structures at $\delta = 2,3$, $\alpha = 1$ and at $\delta = 1$, $\alpha = 1,3,4$ (Theorems 3, 4, 6 and due to [3]). The other is that a unary oritatami system can only produce a single type of simple infinite structures, which is zigzag at $\delta = 1$, $\alpha = 2$ (Theorem 5).

The case of $\delta \ge 4$ and $\alpha = 1$ remains an open problem. Our results should be extended to non-unary oritatami systems, that is, characterization Turing universality of oritatami systems with respect to delay, arity or some other parameters such as the number of bead types.