Networks of Uniform Splicing Processors: Computational Power and Simulation

Abstract

We investigated the computational power of a new variant of network of splicing processors, which simplifies the general model such that filters remain associated with nodes but the input and output filters of every node coincide. This variant, called network of uniform splicing processors, might be implemented more easily. Although the communication in the new variant seems less powerful, the new variant is sufficiently powerful to be computationally complete. Thus, nondeterministic Turing machines were simulated by networks of uniform splicing processors whose size depends linearly on the alphabet of the Turing machine. Furthermore, the simulation was time efficient. We argue that the network size can be decreased to a constant, namely six nodes. We further show that networks with only two nodes are able to simulate 2-tag systems. After these theoretical results, we discuss a possible software implementation of this model by proposing a conceptual architecture and describe all its components.

1. Introduction

In the last two decades, computational models inspired by different phenomena that appear in nature have been vividly researched from a formal perspective. Several theoretical studies of these models have shown that they could solve intractable problems in an efficient way. Several classes of bio-inspired computational models have been surveyed in [1].

We place now our contribution into the general framework of bio-inspired and other parallel and distributed computing models. In this context, networks of bio-inspired processors constitute a group of parallel and distributed computational models having two characteristics: they are abstracted from biological phenomena and their parallelism is extremely high (theoretically unbounded). There is a huge degree of similarity between these networks and other models of computation with related or different origins: tissue-like P systems ([2]) in the membrane computing area ([3]), evolutionary systems abstracted from the evolution of various cell populations ([4]), networks of parallel language processors, which has been introduced as a parallel language-theoretic model ([5]), flow-based programming, which is a programming paradigm widely known ([6]), connection machine, which may be viewed as a network, in the shape of a hypercube, consisting of microprocessors that process one bit per unit time ([7]), distributed computing using mobile programs ([8]), etc.

Roughly speaking, networks of bio-inspired processors can be depicted as graphs whose vertices host processors running operations on data organized in different ways: strings, pictures, graphs, multisets, etc. In the particular area of networks of bio-inspired processors, two main types of networks of bio-inspired processors, where the processed data is structured as strings, have been studied so far: evolutionary processors and splicing processors. A splicing processor ([9]) performs a formal operation, which is abstracted from the splicing of DNA molecules controlled by diverse types of enzymes ([10]). The name of the formal operation is splicing. DNA splicing makes it possible to genetically modify a biological cell for different aims like: plants with a higher resistance to infestation, organisms that are better adapted to environment changes, production of various hormones, etc. This type of DNA recombination is controlled by two types of enzymes: restriction enzymes and ligases. The role of restriction enzymes is to cut the DNA sequences at some recognition sites yielding two DNA sequences having the so-called “sticky ends”, while the role of ligase is to rejoin the sequences produced by the restriction enzymes. In [11], a computational model was introduced, called splicing system, that generates sets of strings by using an operation abstracted from the DNA splicing. Roughly speaking, two strings are used to symbolize the two DNA molecules while quadruples of strings, called splicing rules, symbolize the functions of restriction enzymes indicating where the two previous strings could be cut. The fragments obtained by cutting the strings can be rejoined provided that they were acquired by using the same splicing rule.

Networks of splicing processors were proposed in [9]. This model resembles some aspects of the test tube distributed splicing systems introduced in [12] and investigated in [13] later on. The discrepancies between the models contemplated in [9,12] are accurately detailed in [9]. In [9] one also mentions the disparities between the networks of splicing processors and another distributed system based on splicing, namely the time-varying distributed H systems introduced in [14].

The computation in a network of splicing processors is a sequence of alternative steps: splicing and communication ones. This computation halts when a predefined condition is met. In every splicing step, all processors run simultaneously all splicing rules that could be applied on different copies of the strings that exist in the nodes hosting the respective processor. Therefore, the data in each node is actually a multiset of strings, which means that each string may have sufficiently many copies such that when several rules can be applied to the same string, they are all actually applied in a maximal parallel way to copies of that string. In each communication step, two actions are done according to different strategies:

(i)

simultaneously, in all the nodes of the networks, the data that are able to pass the filter of its node leaves that node and tries to enter all adjacent nodes;

(ii)

simultaneously, all the nodes handle the arriving data.

The communication strategies examined so far are based on filters that allow or forbid strings to enter nodes or go out from them. The filters considered so far are defined by two types of conditions: semantic and syntactical ones. In the case of filters based on syntactical conditions in networks of splicing processors, there are two variants: (i) each node has two filters that could be different, namely an input and an output filter ([9]) and (ii) filters are moved from the nodes to the edges ([15]). This variant may be understood as of the four filters of every pair of adjacent nodes collapse into just two filters that are placed on the edge between them.

We discuss here the main two contributions of this work. We consider here a new variant, somehow “in between” the two aforementioned variants. More precisely, the two filters associated with nodes collapse to only one such that the input and the output filters coincide. This variant, which has been considered for networks of evolutionary processors [16], has never been considered for networks of splicing processors.

We consider here the computational power of this variant. Although the new variants seems less powerful than the other two aforementioned ones, we prove that they have the same computational power. To this aim, we compared the computational power of this variant with that of other two abstract computational models: Turing machine and 2-tag system. The results we obtained are as follows. We first performed a simulation of nondeterministic Turing machines that preserves the time complexity of the machine but the number of nodes depends linearly on the number of symbols in the alphabet of the machine. Further on, we argue that the construction might be used to reduce the number of nodes to a constant, namely 6. We then investigated the possibility to simulate another computationally complete model, namely the 2-tag system with these networks. We performed such a simulation having two important properties: each application of a tag operation is simulated in 8 computational steps (4 splicing steps and 4 communication steps) by the network and the size of the simulating network is optimal, that has 2 nodes only. The methods and techniques used in these simulations were the standard ones in such types of investigations: we explain how each computational step of a Turing machine or a 2-tag system can be simulated by a number of steps in a network of uniform splicing processors. It is worth mentioning that similar results have not been reported for the variant introduced in [16].

After these theoretical results, we discuss a possible software implementation of this model. This is the second main contribution of the paper. To this aim, we propose a conceptual architecture, which means the development of an NSUP engine using the GraphX component within the Spark framework. All the components of this architecture together with the way in which they are interconnected are amply described.

The paper is structured as follows. In the next section we recall the main definitions and concepts necessary to understand the paper. In the same section, we introduce the main concept, namely the network of uniform splicing processors. The third section discusses an efficient simulation of the Turing machine, which can eventually be accomplished by networks with only six uniform splicing processors. The fourth section presents an efficient simulation of another computationally complete model, that of a 2-tag system. In this case, the simulation can be accomplished by a network with only two uniform splicing processors, hence the simulation is an optimal one.

2. Basic Definitions

In the sequel, we define the basic concepts and notations that are to be used in this work; for all unexplained notions the reader is referred to [17].

A finite and non-empty set whose elements are called symbols is said to be an alphabet. Given a finite set A we denote its cardinality by $card(A)$. A string over an alphabet V is defined as a finite sequence of symbols from an alphabet V. We denote by $V^{*}$ the set of all strings over V, the empty string is denoted by $\lambda$, and the length of the string x is denoted by $\left|x\right|$. Furthermore, $alph(x)$ is the minimal alphabet U such that $x\in U^{*}$ holds.

We now formally define the splicing operation following [10]. A splicing rule over the alphabet V is a quadruple of strings of the form $[(v_1,v_2);(v_3,v_4)]$, where $v_1$, $v_2$, $v_3$, and $v_4$ are strings in $V^{*}$. Given a splicing rule $r=[(v_1,v_2);(v_3,v_4)]$ as above and the strings $x,y,z\in V^{*}$, we say that z is the result applying r to x and y (and denote this by $(x,y){⊢}_{r}z$) if x and y can be written as $x=x_1{v}_1{v}_2{x}_2$, and $y=y_1{v}_3{v}_4{y}_2$, for some $x_1,x_2,y_1,y_2\in V^{*}$, and $z=x_1{v}_1{v}_4{y}_2$. If L is a language over V and R is a set of splicing rules, we define

$${\sigma }_R(L)=\{z\in V^{*}\mid \exists x,y\in L,\exists r\in R\mathrm{such}\hspace{0.17em}\mathrm{that}(x,y){⊢}_{r}z\}.$$

We first note that a string of L belongs to ${\sigma }_R(L)$ if and only if it can be obtained by applying a splicing rule to two (possibly the same) strings in L. Second, we note that the definition of a splicing rule from above is actually a 1-splicing rule as defined in [10]. In what follows, we actually use 2-splicing rules as we do not distinguish between the two strings that can arise form the application of a splicing rule.

Let V be an alphabet; we now define two predicates for a string $z\in V^{+}$ and two disjoint subsets $P,F$ of V as follows:

$$\begin{array}{ccc}{\phi }^{(s)}(z;P,F)\hfill & \equiv & P\subseteq alph(z)\wedge F\cap alph(z)=\varnothing \hfill \\ {\phi }^{(w)}(z;P,F)\hfill & \equiv & alph(z)\cap P\ne \varnothing \wedge F\cap alph(z)=\varnothing .\hfill \end{array}$$

In the definition of these predicates, the set P is a set of permitting symbols while the set F is a set of forbidding symbols. Informally, both conditions require that no forbidding symbol occurs in z. As one can see, the former condition is stronger than the second one since it requires that all permitting symbols are present in z, while the latter requires that at least one permitting symbol appears in z.

These predicates are extended to a language $L\subseteq V^{*}$ by

$${\phi }^{\beta }(L,P,F)=\{w\in L\mid {\phi }^{\beta }(w;P,F)\},$$

with $\beta \in \{(s),(w)\}$.

A splicing processor over an alphabet V is a 6-tuple $(S,A,PI,FI,PO,FO)$, where:

–

S is a finite set of splicing rules over V.

–

A is a finite set of auxiliary strings over V. These auxiliary strings are to be used, together with the existing strings, in the splicing steps of the processors. Auxiliary strings are available at any moment.

–

$PI,FI\subseteq V$ are the sets of permitting and forbidding symbols, respectively, which form the input filter of the processor.

–

$PO,FO\subseteq V$ are the sets of permitting and forbidding symbols, respectively, which form the output filter of the processor.

A splicing processor as above is said to be uniform if $PI=PO=P$ and $FI=FO=F$. For the rest of this note we deal with uniform splicing processors only. The set of uniform splicing processors over V is denoted by $US{P}_V$.

A network of uniform splicing processors (NUSP) is a 9-tuple $\mathsf{\Gamma }=(V,U,\langle ,\rangle ,G,\mathcal{N},\alpha ,\underline{In}$, $\underline{Halt})$, where:

• V and U are the input and network alphabet, respectively, $V\subseteq U$, and $\langle ,\rangle \in U\backslash V$ are two special symbols.
• $G=(X_G,E_G)$ is an undirected graph without loops with the set of nodes $X_G$ and the set of edges $E_G$. Each edge is given in the form of a binary set. G is called the underlying graph of the network. In almost all works on networks of splicing processors (see, e.g., the survey [18]), the underlying graph is a complete graph.
• $\mathcal{N}:X_G\to US{P}_U$ is a mapping, which associates with each node $x\in X_G$ the splicing processor $\mathcal{N}(x)=(S_x,A_x,P_x,F_x)$.
• $\alpha :X_G\to \{(s),(w)\}$ defines the type of the filters of a node.
• $\underline{In},\underline{Halt}\in X_G$ are the input and the halting node of $\mathsf{\Gamma }$, respectively.

The size of an NUSP $\mathsf{\Gamma }$ is defined as the number of nodes of the graph, i.e., $card(X_G)$. A configuration of an NUSP $\mathsf{\Gamma }$ is a mapping $C:X_G\to 2^{U^{*}}$, which associates a set of strings with every node of the graph. Although a configuration is a multiset of strings, each one appearing in an arbitrary number of copies, for the sake of simplicity, we work with the support of this multiset. A configuration can be seen as the sets of strings, except the auxiliary ones, which are present in the nodes at some moment. For a string $w\in V^{*}$, we define the initial configuration of $\mathsf{\Gamma }$ on w by $C_0^{(w)}(\underline{In})=\{\langle w\rangle \}$ and $C_0^{(w)}(x)=\varnothing$ for all other $x\in X_G$.

A configuration is followed by another configuration either by a splicing step or by a communication step. A configuration $C^{\prime }$ follows a configuration C by a splicing step if each component $C^{\prime }(x)$, for some node x, is the result of applying all the splicing rules in the set $S_x$ that can be applied to the strings in the set in $C(x)$ together with those in $A_x$. Formally, configuration $C^{\prime }$ follows the configuration C by a splicing step, written as $C\Rightarrow C^{\prime }$, iff for all $x\in X_G$, the following holds:

$$C^{\prime }(x)={\sigma }_{S_x}(C(x)\cup A_x).$$

In a communication step, the following actions take place simultaneously for every node x:

(i)

all the strings that can pass the output filter of a node are sent out of that node;

(ii)

all the strings that left their nodes enter all the nodes connected to their original ones, provided that they can pass the input filter of the receiving nodes.

Note that, according to this definition, those strings that are sent out of a node and cannot pass the input filter of any node are lost. Formally, a configuration $C^{\prime }$ follows a configuration C by a communication step (we write $C^{\prime }\vDash C)$ iff for all $x\in X_G$

$$\begin{array}{c}\hfill C^{\prime }(x)=(C(x)-{\phi }^{\beta (x)}(C(x),P_x,F_x))\cup \\ \hfill {\displaystyle \bigcup _{\{x,y\}\in E_G}({\phi }^{\beta (y)}(C(y),P_y,F_y)\cap {\phi }^{\beta (x)}(C(y),P_x,F_x))}\end{array}$$

holds. For an NUSP $\mathsf{\Gamma }$, a computation on an input string w is defined as a sequence of configurations $C_0^{(w)}$, $C_1^{(w)}$, $C_2^{(w)},\dots$, where $C_0^{(w)}$ is the initial configuration of $\mathsf{\Gamma }$ on w, $C_{2i}^{(w)}\Rightarrow C_{2i+1}^{(w)}$ and $C_{2i+1}^{(w)}\vDash C_{2i+2}^{(w)}$, for all $i\ge 0$. A computation on an input string w halts if there exists $k\ge 1$ such that $C_k^{(w)}(\underline{Halt})$ is non-empty. Such a computation is called an accepting computation.

The language accepted by $\mathsf{\Gamma }$ is defined as

$$L(\mathsf{\Gamma })=\{z\in V^{*}\mid \mathrm{the}\mathrm{computation}\mathrm{of}\mathsf{\Gamma }\mathrm{on}z\mathrm{is}\mathrm{an}\mathrm{accepting}\mathrm{computation}\}.$$

Given an NUSP $\mathsf{\Gamma }$ with the input alphabet V, we define the following computational complexity measure. The time complexity of the finite computation $C_0^{(x)}$, $C_1^{(x)}$, $C_2^{(x)}$, $\cdots C_m^{(x)}$ of $\mathsf{\Gamma }$ on $x\in V^{*}$ is denoted by $Tim{e}_{\mathsf{\Gamma }}(x)$ and equals m. The time complexity of $\mathsf{\Gamma }$ is the partial function from N to N,

$$Tim{e}_{\mathsf{\Gamma }}(n)=\max \{Tim{e}_{\mathsf{\Gamma }}(x)\mid x\in L(\mathsf{\Gamma }),\left|x\right|=n\}.$$

3. Efficient Simulations of Turing Machines

The main result of this note is a time efficient simulation of Turing machines by NUSP. As there are many variants of Turing machines, we start by giving the definition of the Turing machine we are working with. Formally, a Turing machine is a 7-tuple $M=(Q,$ $V,$ $U,$ $\delta ,$ $q_0,$ $B,$ $F)$, where Q is a finite set of states, V is the input alphabet, U is the tape alphabet, $V\subset U$, $q_0$ is the initial state, $B\in U\backslash V$ is the “blank” symbol, $F\subseteq Q$ is the set of final states, and $\delta$ is the transition function, $\delta :(Q\backslash F)\times U\to 2^{Q\times (U\backslash \{B\})\times \{R,L\}}$.

Our variant is a machine with one semi-infinite tape bounded to the left. This tape can store strings over the alphabet $U\backslash \{B\}$; initially it contains the input string which is a string over the alphabet V. The machine has a tape head that can scan just one symbol of the input string at any moment, and a control unit that can be in a state from Q. An operation of M is defined as follows: the tape head scans a symbol from the input string and, depending on the current state of the control unit and the symbol scanned, writes a symbol different from B over the scanned symbol, moves to the right or to the left, provided that the scanned cell is not the leftmost one of the tape, while the control unit may change its state.

A computation of M on an input string is a finite or infinite sequence of operations as above. When the control unit enters a final state, the computation halts and the input string is accepted, hence the language accepted by M consists of all accepted strings. A Turing machine is deterministic if for every state and symbol, the machine can make at most one operation.

The proof of Theorem 1 from [19] can be used to prove that deterministic Turing machines can be efficiently simulated by NUSP. More precisely,

Theorem 1.

If a language is accepted by a deterministic Turing machine in $\mathcal{O}(f(n))$ time, for some function from $\mathbb{N}$ to $\mathbb{N}$, then it is accepted by an NUSP of size 2 in $\mathcal{O}(f(n))$ time.

Consequently,

Corollary 1.

The class of polynomially recognizable languages is included in the class of languages accepted by NUSPs of size 2 in polynomial time.

A natural problem arises: Are NUSPs able to efficiently simulate a nondeterministic Turing machine? In the affirmative, does the size remain constant? It is known that every nondeterministic Turing machine can be simulated by a deterministic one, which in its turn can be efficiently simulated by NUSPs of size 2. However, it is also known that the former simulation increases the time complexity of the deterministic machine. We prove now that a nondeterministic Turing machine can be efficiently simulated (preserving the same time complexity) by an NUSP, but the size of the network depends linearly on the cardinality of the Turing machine alphabet.

Theorem 2.

If a language is accepted by a nondeterministic Turing machine with an alphabet U in $\mathcal{O}(f(n))$ time, then it is accepted by an NUSP of size $2·card(U)+2$ in time $\mathcal{O}(f(n))$.

Proof. 

The network contains along the input and halting node, two nodes for each symbol of the working alphabet of the Turing machine, and two further nodes $\underline{Sim}$ and $\underline{Res}$. We shall now give the formal description of all the nodes (set of rules, axioms, permitting and forbidding symbols, respectively).

Let $M=(Q,$ $V,$ $U,$ $\delta ,$ $q_0,$ $B,$ $F)$ be a nondeterministic Turing machine; we now define the NUSP $\mathsf{\Gamma }=(V,U^{\prime },\langle ,\rangle ,G,\mathcal{N},\alpha ,\underline{In}$, $\underline{Halt})$, where

$$\begin{array}{ccc}{U}^{\prime }\hfill & =& (U\backslash \{B\})\cup \{{\langle }^q\mid q\in Q\backslash F\}\cup \hfill \\ \hfill & & \{{\langle }^{q,b,R}\mid q\in Q,b\in U\backslash \{B\}\}\cup \hfill \\ \hfill & & \{{\langle }^{q^{\prime }}\mid q\in Q\}\cup \{{\langle }^{q,L}\mid q\in Q\}\cup {\{\$,\#,\rangle }^{\prime },\&,‡\},\hfill \end{array}$$

G is a complete graph, while the nodes of $\mathsf{\Gamma }$ are defined as follows:

• $\underline{\mathbf{In}}$

  –

  $S_{\underline{In}}=\{[(\langle ,\lambda );({\langle }^{q_0},\#)],[(\lambda ,\rangle );{(\#,\$\rangle }^{\prime })]\}.$

  –

  $A_{\underline{In}}=\{{{\langle }^{q_0}\#,\#\$\rangle }^{\prime }\}.$

  –

  $P_{\underline{In}}={\{\rangle }^{\prime }\}.$

  –

  $F_{\underline{In}}=\varnothing .$

  –

  $\alpha (\underline{In})=w.$

• $\underline{\mathbf{Sim}}$

  –

  $\begin{array}{l}{S}_{\underline{Sim}}=\{[({\langle }^{q}a,\lambda );({\langle }^{s,b,R},\#)]\mid a\in U\backslash \{B\},q\in Q\backslash F,(s,b,R)\in \delta (q,a)\}\cup \\ \{[({\langle }^q\$,\lambda );({\langle }^{s,b,R}\$,\#)]\mid q\in Q\backslash F,(s,b,R)\in \delta (q,B)\}\cup \\ \{[({\langle }^{q}a,\lambda );({\langle }^{s,L}b,\#)]\mid a,b\in U\backslash \{B\},q\in Q\backslash F,(s,b,L)\in \delta (q,a)\}\cup \\ \{[({\langle }^q\$,\lambda );({\langle }^{s,L}b\$,\#)]\mid b\in U\backslash \{B\},q\in Q\backslash F,(s,L)\in \delta (q,B)\}.\end{array}$

  –

  $\begin{array}{l}{A}_{\underline{Sim}}={\{\langle }^{q,b,R}\#,{\langle }^{q,b,R}\$\#\mid q\in Q,b\in U\backslash \{B\}\}\cup \\ {\{\langle }^{q,L}b\#,{\langle }^{q,L}b\$\#\mid q\in Q,b\in U\backslash \{B\}\}.\end{array}$

  –

  $P_{\underline{Sim}}=\{{\langle }^q\mid q\in Q\backslash F\}\cup \{{\langle }^{q,b,R}\mid q\in Q,b\in U\backslash \{B\}\}\cup \{{\langle }^{q,L}\mid q\in Q\}.$

  –

  $F_{\underline{Sim}}=\{\&,\#‡\}.$

  –

  $\alpha (\underline{Sim})=w.$

• $\underline{{\mathbf{Rins}}_{\mathbf{b}}},b\in U\backslash \{B\}$

  –

  $S_{\underline{Rin{s}_b}}=\{[{(X,\rangle }^{\prime });(\#,b\&)]\mid X\in (U\backslash \{B\})\cup \{\$\}\}\cup \{[({\langle }^{q,b,R},X);({\langle }^{q^{\prime }},\#)]\mid q\in Q,X\in (U\backslash \{B\})\cup \{\$\}\}.$

  –

  $A_{\underline{Rin{s}_b}}=\{(\#b\&\}\cup \{{\langle }^{q^{\prime }}\#\mid q\in Q\}.$

  –

  $P_{\underline{Rin{s}_b}}=\{{\langle }^{q,b,R}\mid q\in Q\}\cup \{\&\}.$

  –

  $F_{\underline{Rin{s}_b}}=\{\#,‡\}.$

  –

  $\alpha (\underline{Rin{s}_b})=w.$

• $\underline{{\mathbf{Lins}}_{\mathbf{b}}},b\in U\backslash \{B\}$

  –

  $S_{\underline{Lin{s}_b}}=\{[{(X,b\rangle }^{\prime });(\#,‡)]\mid X\in (U\backslash \{B\})\cup \{\$\}\}\cup \{[({\langle }^{q,L},X);({\langle }^{q^{\prime }}b,‡)]\mid q\in Q,X\in (U\backslash \{B\})\cup \{\$\}\}.$

  –

  $A_{\underline{Lin{s}_b}}=\{(\#‡\}\cup \{{\langle }^{q^{\prime }}b‡\mid q\in Q\}.$

  –

  $P_{\underline{Lin{s}_b}}=\{{\langle }^{q,L}\mid q\in Q\}\cup \{‡\}.$

  –

  $F_{\underline{Lin{s}_b}}=\{\#,\&\}.$

  –

  $\alpha (\underline{Lin{s}_b})=w.$

• $\underline{\mathbf{Res}}$

  –

  $S_{\underline{Res}}=\{[(X,Y);{(\#,\rangle }^{\prime })]\mid X\in (U\backslash \{B\})\cup \{\$\},Y\in \{\&,‡\}\cup \{[({\langle }^{q^{\prime }},X);({\langle }^q,\#)]\mid q\in Q,X\in (U\backslash \{B\})\cup \{\$\}\}.$

  –

  $A_{\underline{Res}}=\{(\#\&,\#‡\}\cup \{{\langle }^{q^{\prime }}\#\mid q\in Q\}.$

  –

  $P_{\underline{Res}}={\{\&,‡,\rangle }^{\prime }\}.$

  –

  $F_{\underline{Res}}=\{{\langle }^{q,b,R}\mid q\in Q,b\in U\backslash \{B\}\}\cup \{{\langle }^{q,L}\mid q\in Q\}\{\#,\langle \}.$

  –

  $\alpha (\underline{Res})=w.$

• $\underline{\mathbf{Out}}$

  –

  $S_{\underline{Halt}}=A_{\underline{Out}}=F_{\underline{Halt}}=\varnothing .$

  –

  $P_{\underline{Halt}}=\{{\langle }^q\mid q\in F\}.$

  –

  $\alpha (\underline{Halt})=w.$

The input string $\langle w\rangle$ is transformed into ${{\langle }^{q_0}w\$\rangle }^{\prime }$ by two splicing steps in $\underline{In}$, where $q_0$ is the initial state of the Turing machine. Now the string goes out from $\underline{In}$ and one copy enters $\underline{Sim}$. If only one of the splicing step were done in $\underline{In}$, two strings would be obtained, namely ${\langle }^{q_0}w\rangle$ and ${\langle w\$\rangle }^{\prime }$. We analyze what could happen with the two strings. The first cannot leave $\underline{In}$, while the second one goes out from $\underline{In}$ but it cannot enter any node, hence it is lost. Now the network performs a “rotate-and-simulate” strategy. In $\underline{Sim}$, the string ${{\langle }^{q_0}w\$\rangle }^{\prime }$ is processed as follows. Its first symbol ${\langle }^{q_0}$ (inductively, ${\langle }^q$) is simultaneously replaced by ${\langle }^{s,b,R}$ or ${\langle }^{s,L}$, where $(s,b,R)\in \delta (q_0,a)$ and $(s,b,L)\in \delta (q_0,a)$, in different copies of ${{\langle }^{q_0}w\$\rangle }^{\prime }$, where a is the first symbol of w. Now, the new strings enter the nodes associated with the corresponding transitions where those transitions are to be simulated. More precisely, they simultaneously enter $\underline{Rin{s}_b}$ and/or $\underline{Lin{s}_b}$. Each node $\underline{Rin{s}_b}$ and $\underline{Lin{s}_b}$, $b\in U\backslash \{B\}$, performs two splicing steps over the strings it receives. Note that the strings generated by only one splicing step cannot affect the computation. Indeed, they either cannot leave their nodes or can leave their nodes but there is no node that can accept them.

Let us follow the computation on the strings of the form ${{\langle }^{s,b,R}x\$y\rangle }^{\prime }$, $s\in Q$, $b\in U\backslash \{B\}$, $x,y\in {(U\backslash \{B\})}^{*}$, arriving in $\underline{Rin{s}_b}$. After one splicing step, the node yields ${\langle }^{s,b,R}x\$yb\&$, ${\#\rangle }^{\prime }$, ${\langle }^{s,b,R}\#$ and ${{\langle }^{s^{\prime }}x\$y\rangle }^{\prime }$. All these strings, except the first one, are unable to exit the node, hence they will remain there for a further splicing step. The first string goes out but it cannot enter any node, therefore it is lost. After the next splicing step, the strings ${\#\rangle }^{\prime }$, ${\langle }^{s,b,R}\#$ disappear, while a new string is produced, namely ${\langle }^{s^{\prime }}x\$yb\&$, which goes out and enters $\underline{Res}$ only. In this way, $\mathsf{\Gamma }$ simulates a transition of the form $(s,b,R)\in \delta (q_0,a)$ and rotates the string to the right.

The process is similar for $\underline{Lin{s}_b}$. A string ${{\langle }^{s,L}x\$y\rangle }^{\prime }$ enters $\underline{Lin{s}_b}$. The role of this node is threefold: delete a b from the end of y (if any), insert a b to the left hand end of x, replace ${\langle }^{s,L}$ by ${\langle }^{s^{\prime }}$. We describe below how this can be done. If $y=y^{\prime }b$, a string ${\langle }^{s,L}x\$y^{\prime }‡$ is obtained in one splicing step. In the same splicing step, the string ${{\langle }^{s^{\prime }}bx\$y\rangle }^{\prime }$ is also obtained. The string ${\langle }^{s,L}x\$y^{\prime }‡$ leaves $\underline{Lin{s}_b}$, but it is lost because it cannot enter any node. The string ${{\langle }^{s^{\prime }}bx\$y\rangle }^{\prime }$ cannot leave $\underline{Lin{s}_b}$, hence it remains there for a further splicing step in which y is replaced by $y^{\prime }$. Now the new strings go out and enter $\underline{Res}$. Note that if a string ${{\langle }^{s,L}x\$y\rangle }^{\prime }$, such that y does not end by b, enters $\underline{Lin{s}_b}$, it cannot produce any string that is able to go out from $\underline{Lin{s}_b}$ and enter $\underline{Res}$ only. However, the string ${{\langle }^{s,L}x\$y\rangle }^{\prime }$ is simultaneously processed successfully in a node $\underline{Lin{s}_c}$, where c is the last symbol of y. In this way, $\mathsf{\Gamma }$ simulates a transition of the form $(s,c,L)\in \delta (q_0,a)$ and rotate the string to the left, if this is possible.

All the strings successfully processed in the nodes $\underline{Rin{s}_b}$ and $\underline{Lin{s}_b}$, $b\in U\backslash \{B\}$, can enter $\underline{Res}$ only. These strings are of the form ${\langle }^{q^{\prime }}x\$y‡$ or ${\langle }^{q^{\prime }}x\$y\&$, with $q\in Q$, $x,y\in {(U\backslash \{B\})}^{*}$. In $\underline{Rin{s}_b}$, by a sequence of two splicing steps as above, ${\langle }^{q^{\prime }}$ is replaced by ${\langle }^q$, while ‡ and & are replaced by ${\rangle }^{\prime }$. All these new strings go out from $\underline{Res}$ and enter either $\underline{Sim}$, provided that $q\in Q\backslash F$, or $\underline{Halt}$, provided that $q\in F$. In the last case, the simulation is stopped because the computation of M (whose transitions have been simulated by $\mathsf{\Gamma }$) reached a final state.

As one can see, each transition of M is simulated by $\mathsf{\Gamma }$ with a constant number of splicing and communicating steps. Therefore, if M accepts in $\mathcal{O}(f(n))$, then $Tim{e}_{\mathsf{\Gamma }}(n)\in \mathcal{O}(f(n))$. Furthermore, the size of $\mathsf{\Gamma }$ is $2·(card(U)-1)+4=2·(card(U))+2$, which concludes the proof. □

Actually, in the previous proof the symbol b could be considered in $U\backslash (V\cup \{B\})$ only. As it is known that this set can be reduced to the binary alphabet, we may state:

Theorem 3.

Every recursively enumerable language can be accepted by an NUSP of size 6.

Furthermore, a closer look at the communication in the network constructed in the previous proof, leads to the fact that the underlying graph G could be replaced by a “double interconnected star” graph as shown in the Figure 1, where $U\backslash \{B\}=\{a_1,a_2,\cdots ,a_t\}$, for some $t\ge 1$.

4. Efficient Simulations of 2-Tag Systems

We define a 2-tag system following a slightly modified version of the definition that appears in Section 8 of [20]. It is worth mentioning that this definition of a 2-tag-system is slightly different from those proposed in [21,22], but they are equivalent. Formally, a 2-tag system is a pair $T=(V,\mu )$, where V is a finite alphabet containing a special symbol $\pi$, called the halting symbol (denoted by $STOP$ in [20]), and a finite set of rules $\mu :V\backslash \{\pi \}{V}^{+}$ such that $|\mu (x)|\ge 1$ or $\mu (x)=\pi$. Furthermore, $\mu (x)=\pi$ for just one $x\in V\backslash \{\pi \}$. A string that contains the halting symbol or is of length less than 2 is called a halting string.

We now define the mapping $t_T$ (called the tag operation) on the set of non-halting strings. For a non-halting string w, $t_T(w)$ is the string produced as follows: the first two symbols of w are deleted and $\mu (a)$ is appended, provided that a is the first symbol of w. As one can see, this operation deletes two symbols from the beginning of the string and appends to the end a string that depends solely on the first symbol read. A computation by a 2-tag system as above on the initial non-halting string w is a sequence of strings produced by applying iteratively the operation $t_T$ starting with w. A computation as above halts on w if a halting string is produced in some iteration. The halting strings of a length of at least two are defined in [20] in a different way, namely such a string is halting if it starts with a symbol a such that $\mu (a)=\pi$. It is a trivial exercise to show that there exists a bijection between the finite computations obtained in each of the two cases. As shown in [20], such 2-tag systems are computationally complete.

The time complexity of the finite computation of T on $w\in V^{*}$: $w_0=w,w_1=t_T(w_0)$, $w_2=t_T(w_1),\dots ,w_p=t_T(w_{p-1})=\alpha \pi$, with $w_i\in {(V\backslash \{\pi \})}^{+},\left|w_i\right|\ge 2$ for all $0\le i\le p-1$, and $\alpha \in {(V\backslash \{\pi \})}^{*}$, is denoted by $Tim{e}_T(w)$ and equals p. In other words, the time complexity of a finite computation of T on a string is the number of applications of the tag operations necessary for the 2-tag system to produce a halting string. The time complexity of T is the partial function from $\mathbb{N}$ to $\mathbb{N}$, $Tim{e}_T(n)=max\{Tim{e}_T(w)|w\in V^{*},\left|w\right|=n\}$.

We recall here that many small universal Turing machines proposed in the literature have been obtained by simulations of 2-tag systems, see, e.g., [20], and more recently [23] together with the references therein.

It is known that 2-tag systems can simulate Turing machines but this simulation is exponentially slow [24]. An efficient simulation of Turing machines via a simulation of cyclic tag systems is presented in [23]. The main result in [23] states that given a single tape deterministic Turing machine M that computes in time t then there is a 2-tag system $T_M$ that simulates the computation of M in time $\mathcal{O}(t^4{(logt)}^2)$. By the previous simulation it follows that given a single tape deterministic Turing machine M that computes in time t, there is an NUSP ${\mathsf{\Gamma }}_M$ that simulates the computation of M in time $\mathcal{O}(t^4{(logt)}^2)$. The direct simulation presented in the next theorem is more efficient at the price of a larger network size.

Theorem 4.

Given a 2-tag system $T=(V,\mu )$ there exists an NUSP Γ such that every $w\in V^{*}$ is accepted by Γ if and only if T halts on w. Moreover, if $Tim{e}_T(w)=f(|w|)$, then $Tim{e}_{\mathsf{\Gamma }}(w)\in \mathcal{O}(f(\left|w\right|))$.

Proof. 

Let $V^{\prime }=V\backslash \{\pi \}$; we construct the NUSP $\mathsf{\Gamma }=(V^{\prime },U,\langle ,\rangle ,G,\mathcal{N},\alpha ,\underline{In}$, $\underline{Halt})$, where $U=V\cup \{{{\langle }^{\prime },\#,\$,\rangle }^{\prime },\&\}$, and the nodes $x\in X_G$ are defined as follows:

• $\underline{\mathbf{In}}$

  –

  $S_{\underline{In}}$ is the union of the following sets:

  (i)

  $\{[(\langle ,Y);(\$,\#)]\mid Y\in V^{\prime }\cup \{\rangle \}\},$

  (ii)

  $\{[(\$aX,Y);({{\langle }^{\prime },\#\mu (a)\#\rangle }^{\prime })]\mid a\in V^{\prime }\mathrm{such}\mathrm{that}\mu (a)\ne \pi ,\mathrm{and}X\in V^{\prime },Y\in V^{\prime }\cup \{\rangle \}\},$

  (iii)

  $\{[(Y,\rangle );{(\$aX\#,\mu (a)\#\rangle }^{\prime })]\mid a\in V^{\prime }\mathrm{such}\mathrm{that}\mu (a)\ne \pi ,\mathrm{and}X,Y\in V^{\prime }\},$

  (iv)

  $\{[{(X\mu (a),\#\rangle }^{\prime });(\$aY\#,\rangle )]\mid a\in V^{\prime },\mathrm{such}\mathrm{that}\mu (a)\ne \pi ,\mathrm{and}Y\in V^{\prime },X\in V^{\prime }\cup \{{\langle }^{\prime }\}\},$

  (v)

  $\{[({\langle }^{\prime },a);{(\$,aY\#\#\rangle }^{\prime })]\mid a\in V^{\prime }\mathrm{such}\mathrm{that}\mu (a)\ne \pi ,\mathrm{and}Y\in V^{\prime }\},$

  (vi)

  $\{[(\$aX,Y);(\&,\$)]\mid a\in V^{\prime }\mathrm{such}\mathrm{that}\mu (a)=\pi ,X\in V^{\prime },Y\in V^{\prime }\cup \{\rangle \}\},$

  (vii)

  $\{[(Xa,\rangle );(\&,\&)]\mid X\in \{\langle ,\$\}\}.$

  –

  $A_{\underline{In}}=\{{{\langle }^{\prime }\#\mu (a)\#\rangle }^{\prime }\mid a\in V^{\prime }\mathrm{and}\mu (a)\ne \pi \}\cup \{\$\#,\langle \#,\&\$\}.$

  –

  $P_{\underline{In}}=\{\langle ,\&\}$

  –

  $F_{\underline{In}}=\{\$\}.$

  –

  $\alpha (\underline{In})=(w).$

• $\underline{\mathbf{Halt}}$

  –

  $S_{\underline{Halt}}=A_{\underline{Halt}}=\varnothing .$

  –

  $P_{\underline{Halt}}=\{\&\}.$

  –

  $F_{\underline{Halt}}=\{\#\}.$

  –

  $\alpha (\underline{Halt})=w.$

We show that $\mathsf{\Gamma }$ accepts a string w that does not contain $\pi$ if and only if T eventually halts on w. Let $w=aby,a,b\in V,y\in V^{*}$ be a string that does not contain $\pi$ such that T eventually halts on w. We show how w can be accepted by $\mathsf{\Gamma }$. To this aim we show how a tag operation in T is simulated by $\mathsf{\Gamma }$. We first assume that $\mu (a)\ne \pi$. At the beginning of the computation of $\mathsf{\Gamma }$, in the node $\underline{In}$, a splicing rule in the set (i) is applied to the input string $\langle aby\rangle$ and the axiom $\$\#$. This operation yields two strings: $\$aby\rangle$ and $\langle \#$. The second string gets through the filters of $\underline{In}$ and leaves it. However, it is lost because it cannot be accepted by the other node in the network, namely $\underline{Halt}$, as a result of the forbidden character #. On the other hand, the first string $\$aby\rangle$ cannot pass the forbidding filter of $\underline{I}n$ and remains in this node for further operations.

In the next splicing step in $\underline{In}$ a rule from (ii) is applied to the previously obtained string $\$aby\rangle$ and to the axiom ${{\langle }^{\prime }\#\mu (a)\#\rangle }^{\prime }$. The result of this splicing step is the pair of strings ${\langle }^{\prime }y\rangle$ and ${\$ab\#\mu (a)\#\rangle }^{\prime }$. Since these new strings cannot pass the filter of $\underline{In}$, they remain there for the next splicing step. At this moment, only one action is possible, namely to apply a rule in set (iii) to the pair of strings just obtained. This splicing step yields a new pair of strings, namely ${{\langle }^{\prime }y\mu (a)\#\rangle }^{\prime }$ and $\$ab\#\rangle$. These two strings, which cannot leave $\underline{In}$, are to be further involved into a splicing step by using a rule in set (iv) producing the new pair of strings ${\langle }^{\prime }y\mu (a)\rangle$ and ${\$ab\#\#\rangle }^{\prime }$. Again, the next splicing step is uniquely determined. Indeed, only a rule from (v) can be applied to the pair of strings ${\langle }^{\prime }y\mu (a)\rangle$ and ${\$ab\#\#\rangle }^{\prime }$ yielding $\$y\mu (a)\rangle$ and ${{\langle }^{\prime }ab\#\#\rangle }^{\prime }$. This splicing step finishes the simulation of the tag operation $\mu (a)$ applied to w in T.

More precisely, $\$y\mu (a)\rangle$ corresponds exactly to the transformation of $aby$ in T by applying $\mu (a)\ne \pi$, while the second string is to be lost in the next splicing step because there is no string that can be paired up with it in a splicing step. The process is resumed with the new string $\$y\mu (a)\rangle$ until a string $\$bz\rangle$, with $\mu (b)=\pi$ is obtained. When such a string is obtained, say $\$bcz\rangle$, by using a rule in set (vi) and the axiom $\&\$$ the string $\&z\rangle$ is obtained which leaves $\underline{In}$ and enters $\underline{Halt}$ and the computation of $\mathsf{\Gamma }$ on w halts.

Finally, let us consider the special halting cases of a string of length 1. There are two cases: the current string is either an input string $\langle a\rangle$, for some $a\in V$, or a string obtained via a series of computations as above $\$a\rangle$, $a\in V$. A rule in (vii) can be applied to such a string and the axiom $\&\&$ producing two strings such that at least one of them goes out from $\underline{In}$ and enters $\underline{Halt}$. Note that the axiom $\&\&$ disappears after every splicing step when there is no string as above in $\underline{In}$. In this way, it cannot halts the computation illegally.

Conversely, it is clear that a computation of $\mathsf{\Gamma }$ on an input string halts if and only if the input string is of length one or it eventually leads to the string containing &. This means that T halts on that input string.

It is easy to note that $\mathsf{\Gamma }$ emulates one transformation of T in four steps. Consequently, $Tim{e}_{\mathsf{\Gamma }}(w)\in \mathcal{O}(f(\left|w\right|))$ holds, and the proof is complete.

5. Towards a Computational Simulation of NUSP

Over the last decade, several implementations of Networks of Bio-inspired Processors (NBP for short) on software computational platforms have been reported in the literature. Various architectures, technologies, and strategies have been used in order to handle the large data generated by NBP algorithms within a massively parallel and distributed environment. With the advent of ultra-scalable computational platforms in Big Data scenarios, a new line for software development of NBP simulators was opened. In particular, a highly scalable engine developed with Apache Giraph on top of the Hadoop platform was proposed in [25]. This engine, NPEPE, is able to run Networks of Polarized Evolutionary Processors (NPEP) algorithms and some other NBP variants’ algorithms ([26]). Apache Giraph ([27]) is an iterative graph processing system built for highly scalable and fault tolerant distributed computations. Giraph was developed as the open-source counterpart to Pregel, which was proposed by Google. Its architecture for parallel computation is based on the well-known “Bulk Synchronous Parallel” (BSP) model defined in [28]. BSP was introduced for guiding the design and implementation of parallel algorithms for large-graph processing. Basically, the BSP model implemented by Pregel and Giraph defines two step processes, which are performed iteratively and synchronously: (1) one process performing computations on local data and (2) one process communicating the results. Each iteration (computation or communication) is called a superstep and represents atomic units of the parallel computation.

The Apache Hadoop software library is a framework able to execute distributed processing of large data sets across clusters of computers using a simple programming model based on Map and Reduce operations.

Apache Spark has emerged as a fast and general-purpose cluster computing framework able to execute high performance parallel computations in an efficient way. Spark was proposed to resolve some drawbacks found in existing Map Reduce implementations (bottlenecks in the cluster communication process, inefficiencies in accessing data, among others). In particular, Spark resolves these drawbacks proposing a new programming model that uses a distributed, immutable and fault-tolerant memory abstraction named Resilient Distributed Datasets (RDDs). RDDs are able to maintain data in memory, disk, or in combination of both rather than only in disk (such as previous Map Reduce implementations). Some experiments demonstrated that Spark outperforms, by up to two orders of magnitude, conventional Map Reduce jobs in terms of speed, see, e.g., [29,30].

For specific graph-parallel processing, Spark offers the GraphX library. GraphX uses the concept of Property Graph (directed multigraph) in combination with RDDs to execute graph algorithms through partitioning and distributing techniques. GraphX reduces the excessive data movement and processing inefficiencies exhibited by their predecessors by proposing the unification of data-parallel and graph-parallel methods into one unified library working on Spark framework.

As Giraph became a natural architecture to implement NPEP models through the NPEPE engine [25], we consider Spark GraphX to be a suitable framework to offer high performance and efficiency in the computations (by improving the data movement in the communication processes) in some NBP models requiring these capabilities.

Therefore, we consider that Spark GraphX is an adequate framework to fit the specific and novel nature of NUSP model. In particular, splicing rules are more complex than evolutionary rules (used in different variants of networks of evolutionary processors) due to, among other reasons, the fact that these operations involve two strings and several suboperations: identify the splicing sites in each string to which the splicing rule is to be applied, cut these strings and finally, rejoin the obtained substrings in accordance with their order in the original strings. It is clear that simulating splicing rules requires more computational resources, such as memory, therefore an efficient use of all the computational resources of the model.

To our best knowledge, there is no hardware or software implementations of NBP models using splicing steps. In this section we introduce a conceptual and informal discussion proposing the main guidelines to address the development of an NUSP engine on Spark GraphX which seems more suitable to address the complexity of this bio-inspired computational model due to its splicing rules.

We start with an informal discussion, hence we consider an architecture for general purpose which is shown in Figure 2.

Following this architecture, our suggestion is to develop the NSUP engine using GraphX component within the Spark framework working in collaboration with two additional components, namely: an Input component or NSUP editor and an Output component or NSUP collector.

The NSUP editor should be developed in order to provide functionalities that allow the final users to define and describe the NSUP algorithm in a friendly way. This component must facilitate a more expressive manner to design an NSUP algorithm avoiding mistakes in the notation when defining splicing rules in text editors. Following the same idea, the NSUP collector should be able to obtain the output of an NSUP network computation from the halting node and show it in a friendly manner such that it can be comprehensible to the final user.

On the other hand, the NSUP engine should be able to extend the class utilities offered by GraphX in order to execute the splicing and communication steps defined in the NSUP model dynamics. These three modules and the way in which they are either connected or mapped into the GraphX framework are described as follows:

• NSUP editor: this component will be the input connection with the NSUP engine and GraphX. Given that GraphX supports large scale graphs, this component should be able to handle several input file formats such as text and JSON, in order to encode underlying NSUP graph definitions. In particular, these formats are suitable for loading graph configurations using the utility class of GraphX called GraphLoader. Therefore, this component should generate a NSUP network configuration from final user’s definition using these input file formats. We consider that JSON format is more suitable to define the structure of NSUP algorithms and the configuration of its components: splicing rules, axioms, alphabets, nodes, etc. The details of these components should be introduced by final user through a graphical user interface. Then, NSUP editor should generate two configuration files: (1) “configFile.json” representing the definition for NSUP graph components and (2) “configFile.txt” containing the definition of the input word encoding the problem instance which is to be solve by this NSUP configuration.
• NSUP engine: the first component to be implemented within the NSUP engine is the Input module. This module reads the JSON file generated by NSUP editor and uses the GraphLoader class utility (GL) to instantiate the specific Property Graph and Vertex classes from GraphX. The interaction between NSUP editor and the Input module is illustrated in Figure 3.

The second component, named the NSUP Computation Module, should use the Property Graph instance created by the Input module to define the Spark Context and the main GraphX components: Vertex Table and Edge Table. Our NSUP Computation Module will require other additional elements: alphabets (V and U), filters (the sets P and F), axioms, and rules. Specifically, axioms and rules will be instanced using the stored information into each JSON object defining a splicing node processor. They should be associated with their respective vertex (a row in the Vertex Table) by means an unique identifier (ID) into Axiom and Rule Tables. Similarly, the filters (P and F sets) will be instanced into PContext and FContext Tables using their corresponding ID from the Edge Table, as it is illustrated in Figure 4. On the other hand, the definitions of the two alphabets should be associated with the respective attributes of the Spark GraphContext instance. Note that NSUP elements, such as axioms, rules, and filters, will be converted into GraphX RDD structures. Especial vertices such as the input or halting splicing processor nodes, will be defined as extended Vertex Property instances. Particularly, the NSUP Computation Module should read the “configFile.txt” file in order to extract the encoded input word and store it as the only message into the Message Table (Msg Table) of the vertex representing the input node. Each vertex will have associated a Message Table in which it can store its received or processed words. Initially, all vertices except the input one, will have their Message Table empty. We remark that, the NSUP notation is conserved into the GraphX mapping.

In order to simulate the NSUP model dynamics, the NSUP Computation Module should define an execution method to start the computation. This method should activate all vertices but only the input vertex is able to apply its splicing rules over its Message Table content (which contains the message encoding the input word). The splicing operations defined by the splicing rules, will be implemented into the Vertex class utility. After the starting step, each vertex should apply its rules (defined into the Rules Table) over incoming messages from input vertex and stores them into its Message Table. At this moment, the NSUP Computation Module will run a splicing step. When all rules have been applied, the NSUP Computation Module will invoke the GraphX methods from Pregel API such that every vertex of a superstep will receive and/or send processed messages according to the associated vertices from the Edge Table. Then, a communication step will be executed. After that, the NSUP Computation Module should invoke other superstep. Finally, we note that in a communication step each vertex can discard the processed messages, store them (in its Msg RDD Table) or send them to all associated vertices depending on the results obtained by the filter application.

• NSUP Collector represents a component which will be responsible for dumping the data content of the $\underline{Halt}$ vertex on an external file, which can be easily interpreted by the final users. In addition, this component could dump the messages that each vertex keeps in their respective Msg Tables when the computation halts creating a file for final computation log.

Summarizing, at the beginning of the NSUP algorithm computation, only the vertex dynamics representing the input node is executed and then this node sends out the obtained messages after applying its splicing rules to the initial message. Afterwards, during each superstep, the NSUP engine through the GraphX invokes all vertices in parallel so that they can process the received messages and can send out those messages able to pass their respective filters. This process runs until the scanning process for the halting vertex returns that the Msg Table for this node is non-empty. This process could be be implemented using the dynamic PageRank algorithm by configuring the ranks converge property. At the end, all words in the Msg Table of the halting vertex should be sent to an NSUP Collector.

Finally, we consider that the guidelines introduced in this section are an useful starting point that might contribute to the development of software frameworks to simulate NBP models using splicing rules.

6. Conclusions and Further Work

In this paper, we proved that uniform networks of splicing processors are computationally complete by displaying efficient simulations of two known models with this property: 2-tag systems and Turing machines. While a Turing machine simulation is enough to provide definitive proof, the required number of nodes for the corresponding NUSP depends on the size of the tape alphabet U. This number can be decreased to six. On the other hand, a NUSP simulating 2-tag systems can be implemented with the minimal number of nodes, two: $In$ and $Halt$. Additionally, it is known that direct simulations between Turing machines and 2-tag systems are not time efficient, while our simulations avoid this problem by preserving the time complexity of the simulated models.

An attractive problem of theoretical interest is to investigate whether or not the size of NUSP efficiently simulating Turing machines can be still decreased. Along the same theoretical lines, another problem is to design computationally complete NUSP having an underlying graph common in the network area: bus, star, grid, etc.

Another interesting theoretical problem is the following one. As we have mentioned above, there are three variants of NSP which differ from each other by the filtering process. Together with the results reported in this paper, we infer that all these variants are equivalent from the computational power point of view, but this equivalence has been obtained by simulations of other models. It is very natural to investigate the possibility of designing direct simulations between all these variants.

As far as our suggestion for a possible software simulation of NUSP is concerned, we will try to implement the architecture discussed here and make experiments with some algorithms based on NUSP. Depending on the results of these experiments we may improve the simulation or make some changes in the proposed architecture. Having implemented this software, we intend to use it for different algorithms especially in computational geometry like, for instance, [31,32].