The main idea of the proofs

In this section we present the idea on which both main proofs of the chapter are based. First we recall a definition from [GeffertGeffert1988].

Definition 6.2  
Let ${\Delta}=\{a_1,a_2,\ldots, a_{\ell}\}$ be an alphabet, $1\leq {\ell}$. An Extended Post Correspondence (an EPC) is a set

$$P= (\{(u_1,v_1),\ldots, (u_m,v_m)\}, (z_{a_1},\ldots,z_{a_{\ell}})),$$

where $1\leq m$, and $u_i,v_i,z_{a_j}\in \{0,1\}^*$ for $1\leq i\leq m$ and $1\leq j\leq {\ell}$.
The language represented by $P$ in $\Delta$, written as $L(P)$, is the following set of words:

$$L(P)= \left\{x_1\cdots x_n\in {\Delta}^*\;\vert\; \exists s_1, s_2, \ldots, s_r \in {\{1,2,\ldots, m\}}, \;\;\;such\;\; that \right.$$

$$\left.\;\;\;1\leq r \;\;\; and \;\;\; u_{s_1}u_{s_2}\cdots u_{s_r}=v_{s_1}v_{s_2}\cdots v_{s_r}z_{x_1}z_{x_2}\cdots z_{x_n} \right\}$$

We want to show that for any recursively enumerable language $L$ we can construct a standard Watson-Crick EDT0L system, a standard Watson-Crick E0L system, and also a standard Watson-Crick eco-grammar system, such that the generated language of the systems is $L$. The constructions have the same idea, which is based on the following theorem presented in [GeffertGeffert1988]:

Theorem 6.3  
For any recursively enumerable language $L$ there exists an Extended Post Correspondence $P$, such that $L(P)=L$.

We note here that Definition 6.2 remains correct and Theorem 6.3 remains true if we suppose that the words $u_i,v_i,$ and $z_{a_j}$ are over $\{1,2\}$ instead of $\{0,1\}$ for $1\leq i\leq m$ and $1\leq j\leq {\ell}$. This modification is important from our point of view because it makes our construction simpler, so we will use this version of the EPC and Theorem 6.3.

We can consider the words $u_{s_1}u_{s_2}\cdots u_{s_r}$ and $v_{s_1}v_{s_2}\cdots v_{s_r}z_{x_1}z_{x_2}\cdots z_{x_n}$ as numbers in base three notation and therefore we can speak about their values. From this point of view, Theorem 6.3 says that a word $w=x_1\cdots x_n$ is in $L$ if and only if there exist indices $s_1,\ldots, s_r\in {\{1,2,\ldots, m\}}$, such that $1\leq r$ and the values of the two words $u_{s_1}u_{s_2}\cdots u_{s_r}$ and $v_{s_1}v_{s_2}\cdots v_{s_r}z_{x_1}z_{x_2}\cdots z_{x_n}$ are equal.

Using this fact, we will generate words of a recursively enumerable language $L$ in three phases in the following way. By the end of the first phase we generate a sentential form representing the values of the words $u_{s_1}u_{s_2}\cdots u_{s_r}$ and $v_{s_1}v_{s_2}\cdots v_{s_r}$. By the end of the second phase we will have a sentential form which represents the word $w=x_1\cdots x_n$ and the values of the words $u_{s_1}u_{s_2}\cdots u_{s_r}$ and $v_{s_1}v_{s_2}\cdots v_{s_r}z_{x_1}z_{x_2}\cdots z_{x_n}$.

The construction used in these phases guarantees that all sentential forms representing the values of a pair in the form of $(u_{s_1}u_{s_2}\cdots u_{s_r}, v_{s_1}v_{s_2}\cdots v_{s_r}z_{x_1}z_{x_2}$ $\cdots z_{x_n})$ and the corresponding word $w=x_1\cdots x_n$ can be generated in this way.

In the third phase we check the condition presented above: the equality of the values of the two words $u_{s_1}u_{s_2}\cdots u_{s_r}$ and $v_{s_1}v_{s_2}\cdots v_{s_r}z_{x_1}z_{x_2}\cdots z_{x_n}$. The corresponding word $w=x_1\cdots x_n$ is accepted if and only if this checking is successful. Therefore only those words can be generated for which there exist indices $(s_1,\ldots, s_r)\in {\{1,2,\ldots, m\}}$, such that $1\leq r$ and $u_{s_1}u_{s_2}\cdots u_{s_r}=v_{s_1}v_{s_2}\cdots v_{s_r}z_{x_1}z_{x_2}\cdots z_{x_n}$.

Now we describe how we can represent values of words in the sentential form. Besides the letters from alph$(L)$, we have additional letters in the sentential form: $A$ and $B$; the number of $A$'s represents the value of the word $u_{s_1}u_{s_2}\cdots u_{s_r}$, the number of $B$'s represents the value of the other word $v_{s_1}\cdots v_{s_r}z_{x_1}z_{x_2}\cdots z_{x_n}$.

The derivation proceeds in the following way. In the first phase we increase the number of $A$'s and $B$'s according to the concatenation of the pairs $(u_j,v_j)$. Hence by the end of this phase the sentential form represents the values of the words $u_{s_1}u_{s_2}\cdots u_{s_r}$ and $v_{s_1}\cdots v_{s_r}$.

In the second phase we put letters $x_i$ into the sentential form and at the same time increase the number of letters $B$ according to the value of the corresponding word $z_{x_i}$. Thus by the end of this phase the sentential form contains a word $w=x_1\cdots x_n$ and represents the two values of the words $u_{s_1}u_{s_2}\cdots u_{s_r}$ and $v_{s_1}\cdots v_{s_r}z_{x_1}z_{x_2}\cdots z_{x_n}$.

In the third phase we check whether the number of $A$'s and $B$'s are equal. If the answer is positive, then all symbols but the ones representing the word $w$ are deleted and the word $w=x_1\cdots x_n$ is generated. Otherwise the derivation is blocked and never results in a terminal word.

We use this same idea in both main constructions of the chapter, the difference between the two proofs lies in the techniques used for coordinating the derivation.