1 Introduction
Based on the biological background of neurons sending electrical impulses along axons to other neurons, several models were developed in the area of neural computation, e.g., see Maass (
2002), Maass and Bishop (
1999), and Gerstner and Kistler (
2002). In the area of P systems, the model of
spiking neural P systems was introduced in Ionescu et al. (
2006). Whereas the basic model of membrane systems, see Păun (
2000), reflects hierarchical membrane structures, the model of tissue P systems considers cells to be placed in the nodes of a graph. This variant was first considered in Păun et al. (
2006) and then further elaborated, for example, in Freund et al. (
2004) and Martín-Vide et al. (
2002). In spiking neural P systems, the cells are arranged as in tissue P systems, but the contents of a cell (neuron) consists of a number of so-called
spikes, i.e., of a multiset over a single object. The rules assigned to a neuron allow us to send information to other neurons in the form of electrical impulses (also called spikes) which are summed up at the target neuron; the application of the rules depends on the contents of the neuron and in the general case is described by regular sets. As inspired from biology, the neuron sending out spikes may be “closed” for a specific time period corresponding to the refraction period of a neuron; during this refraction period, the neuron is closed for new input and cannot get excited (“fire”) for spiking again.
The length of the axon may cause a time delay before a spike arrives at the target. Moreover, the spikes coming along different axons may cause effects of different magnitude. All these biologically motivated features were included in the model of extended spiking neural P systems considered in Alhazov et al. (
2006), the most important theoretical feature being that neurons can send spikes along the axons with different magnitudes at different moments of time. In Wang et al. (
2010), spiking neural P systems with weights on the axons and firing threshold were investigated, where the values of these weights and firing thresholds as well as the potential consumed by each rule could be natural numbers, integer numbers, rational numbers, and even (computable) real numbers.
In this paper, we will further extend the model of extended spiking neural P systems by using so-called “white hole rules”, which allow us to use the whole contents of a neuron and send it to other neurons, yet eventually multiplied by some constant rational number.
In the literature, several variants how to obtain results from the computations of a spiking neural P system have been investigated. For example, in Ionescu et al. (
2006) the output of a spiking neural P system was considered to be the time between two spikes in a designated output neuron. It was shown how spiking neural P systems in that way can generate any recursively enumerable set of natural numbers. Moreover, a characterization of semilinear sets was obtained by spiking neural P system with a bounded number of spikes in the neurons. These results can also be obtained with even more restricted forms of spiking neural P systems, e.g., no time delay (refraction period) is needed, as it was shown in Ibarra et al. (
2006). In Chen et al. (
2006), the generation of strings (over the binary alphabet 0 and 1) by spiking neural P systems was investigated; due to the restrictions of the original model of spiking neural P systems, even specific finite languages cannot be generated, but on the other hand, regular languages can be represented as inverse-morphic images of languages generated by finite spiking neural P systems, and even recursively enumerable languages can be characterized as projections of inverse-morphic images of languages generated by spiking neural P systems. The problems occurring in the proofs are also caused by the quite restricted way the output is obtained from the output neuron as sequence of symbols 0 and 1. The strings of a regular or recursively enumerable language could be obtained directly by collecting the spikes sent by specific output neurons for each symbol.
In the extended model considered in Alhazov et al. (
2006), a specific output neuron was used for each symbol. Computational completeness could be obtained by simulating register machines as in the proofs elaborated in the papers mentioned above, yet in an easier way using only a bounded number of neurons. Moreover, regular languages could be characterized by finite extended spiking neural P systems; again, only a bounded number of neurons was needed.
In this paper, we now extend this model of extended spiking neural P systems by also using so-called “white hole rules”, which may send the whole contents of a neuron along its axons, eventually even multiplied by a (positive) rational number. In that way, the whole contents of a neuron can be multiplied by a rational number, in fact, multiplied with or divided by a natural number. Hence, even one single neuron is able to simulate the computations of an arbitrary register machine.
The idea of consuming the whole contents of a neuron by white hole rules is closely related to the concept of the exhaustive use of rules, i.e., an enabled rule is applied in the maximal way possible in one step; P systems with the exhaustive use of rules can be used in the usual maximally parallel way on the level of the whole system or in the sequential way, for example, see Zhang et al. (
2008,
2012). Yet all the approaches of spiking neural P systems with the exhaustive use of rules are mainly based on the classic definitions of spiking neural P systems, whereas the spiking neural P systems with white hole rules as investigated in Alhazov et al. (
2015a) are based on the extended model as introduced in Alhazov et al. (
2006). In this paper we now use this new model of spiking neural P systems with white hole rules together the idea of considering infinite computations on finite inputs, which will allow us to “go beyond Turing”.
Variants of how to “go beyond Turing” are discussed in van Leeuwen and Wiedermann (
2012), for example, the definitions and results for red–green Turing machines can be found there. In Aman et al. (
2014) the notion of red–green automata for register machines with input strings given on an input tape (often also called
counter automata) was introduced and the concept of
red–green P automata for several specific models of membrane systems was explained. Via red–green counter automata, the results for acceptance and recognizability of finite strings by red–green Turing machines were carried over to red–green P automata. The basic idea of red–green automata is to distinguish between two different sets of states (red and green states) and to consider infinite runs of the automaton on finite input objects (strings, multisets); allowed to change between red and green states more than once, red–green automata can recognize more than the recursively enumerable sets (of strings, multisets), i.e., in that way we can “go beyond Turing”. In the area of P systems, first attempts to do that can be found in Calude and Păun (
2004) and Sosík and Valík (
2006). Computations with infinite words by P automata were investigated in Freund et al. (
2004).
The rest of the paper is organized as follows: In the next section, we recall some preliminary notions and definitions from formal language theory, especially the definition and some well-known results for register machines. Then we define red–green Turing machines and red–green register machines and recall some results from Aman et al. (
2014). In Sect.
4 we recall the definitions of the extended model of spiking neural P systems as considered in Alhazov et al. (
2006) as well as the most important results established there. Moreover, we show that extended spiking neural P systems with only one actor neuron have exactly the same computational power as register machines with only one register that can be decremented.
In Sect.
5, we define the model of extended spiking neural P systems extended by the use of white hole rules as introduced in Alhazov et al. (
2015a). Besides giving some examples, for instance showing how Lindenmayer systems can be simulated by extended spiking neural P systems only using white hole rules, we prove that the computations of an arbitrary register machine can be simulated by only one single neuron equipped with the most powerful variant of white hole rules, i.e., extended spiking neural P systems equipped with white hole rules are even more powerful than extended spiking neural P systems, which need (at least) two neurons to be able to simulate the computations of an arbitrary register machine. Based on this result, we define the
red–green variant of spiking neural P systems with white hole rules and show that their computational power is similar to the computational power of red–green register machines. A short summary of the results we obtained concludes the paper.
2 Preliminaries
In this section we recall the basic elements of formal language theory and especially the definitions and results for register machines; we here mainly follow the corresponding section from Alhazov et al. (
2006,
2015a).
For the basic elements of formal language theory needed in the following, we refer to any monograph in this area, in particular, to Rozenberg and Salomaa (
1997). We just list a few notions and notations:
\(V^*\) is the free monoid generated by the alphabet
V under the operation of concatenation and the empty string, denoted by
\(\lambda\), as unit element; for any
\(w\in V^*\),
\(\left| w\right|\) denotes the number of symbols in
w (the
length of
w).
\({\mathbb{N}}_+\) denotes the set of positive integers (natural numbers),
\({\mathbb{N}}\) is the set of non-negative integers, i.e.,
\({\mathbb{N}}={\mathbb{N}}_+\cup \left\{ 0\right\}\), and
\(\mathbb{Z}\) is the set of integers, i.e.,
\(\mathbb{Z}={\mathbb{N}}_+\cup \left\{ 0\right\} \cup -{\mathbb{N}}_+\). The interval of non-negative integers between
k and
m is denoted by
\(\left[ k..m\right]\), and
\(k\cdot {\mathbb{N}}_+\) denotes the set of positive multiples of
k. Observe that there is a one-to-one correspondence between a set
\(M\subseteq {\mathbb{N}}\) and the one-letter language
\(L\left( M\right) =\left\{ a^n\mid n\in M\right\}\); e.g.,
M is a regular (semilinear) set of non-negative integers if and only if
\(L\left( M\right)\) is a regular language. By
\(FIN\left( {\mathbb{N}}^k\right)\),
\(REG\left( {\mathbb{N}}^k\right)\), and
\(RE\left( {\mathbb{N}}^k\right)\), for any
\(k\in {\mathbb{N}}\), we denote the sets of subsets of
\({\mathbb{N}}^k\) that are finite, regular, and recursively enumerable, respectively.
By REG (\(REG\left( V\right)\)) and RE (\(RE\left( V\right)\)) we denote the family of regular and recursively enumerable languages (over the alphabet V, respectively). By \(\varPsi _{T}\left( L\right)\) we denote the Parikh image of the language \(L\subseteq T^*\), and by PsFL we denote the set of Parikh images of languages from a given family FL. In that sense, \(PsRE\left( V\right)\) for a k-letter alphabet V corresponds with the family of recursively enumerable sets of k-dimensional vectors of non-negative integers.
2.1 Register machines
The proofs of the results establishing computational completeness in the area of P systems often are based on the simulation of register machines; we refer to Minsky (
1967) for original definitions, and to Freund and Oswald (
2002) for the definitions we use in this paper:
An
n-
register machine is a tuple
\(M=\left( n,B,l_0,l_h,P\right)\), where
n is the number of registers,
B is a set of labels,
\(l_0\in B\) is the initial label,
\(l_h\in B\) is the final label, and
P is the set of instructions bijectively labeled by elements of
B. The instructions of
M can be of the following forms:
-
\(l_1:\left( ADD\left( r\right) ,l_2,l_3\right)\), with \(l_1\in B\setminus \left\{ l_h\right\}\), \(l_2,l_3\in B\), \(1\le j\le n\).
Increases the value of register r by one, followed by a non-deterministic jump to instruction \(l_2\) or \(l_3\). This instruction is usually called increment.
-
\(l_1:\left( SUB\left( r\right) ,l_2,l_3\right)\), with \(l_1\in B\setminus \left\{ l_h\right\}\), \(l_2,l_3\in B\), \(1\le j\le n\).
If the value of register r is zero then jump to instruction \(l_3\); otherwise, the value of register r is decreased by one, followed by a jump to instruction \(l_2\). The two cases of this instruction are usually called zero-test and decrement, respectively.
-
\(l_h:halt\) (HALT instruction)
Stop the machine. The final label \(l_h\) is only assigned to this instruction.
A (non-deterministic) register machine
M is said to generate a vector
\(\left( s_1,\ldots ,s_\beta \right)\) of natural numbers if, starting with the instruction with label
\(l_0\) and all registers containing the number 0, the machine stops (it reaches the instruction
\(l_h:halt\)) with the first
\(\beta\) registers containing the numbers
\(s_1,\ldots ,s_\beta\) (and all other registers being empty).
Without loss of generality, in the succeeding proofs we will assume that in each ADD instruction
\(l_1:\left( ADD\left( r\right) ,l_2,l_3\right)\) and in each SUB instruction
\(l_1:\left( SUB\left( r\right) ,l_2,l_3\right)\) the labels
\(l_1,l_2,l_3\) are mutually distinct (for a short proof see Freund et al.
2004).
The register machines are known to be computationally complete, equal in power to (non-deterministic) Turing machines: they generate exactly the sets of vectors of non-negative integers which can be generated by Turing machines, i.e., the family PsRE.
Based on the results established in Minsky (
1967), the results proved in Freund and Oswald (
2002) and Freund and Păun (
2004) immediately lead to the following result:
When considering the generation of languages, we can use the model of a
register machine with output tape, which also uses a tape operation:
-
\(l_1:\left( write\left( a\right) ,l_2\right)\)
Write symbol a on the output tape and go to instruction \(l_2.\)
We then also specify the output alphabet
T in the description of the register machine with output tape, i.e., we write
\(M=\left( m,B,l_0,l_h,P,T\right)\).
The following result is folklore, too, e.g., see Minsky (
1967):
2.2 The arithmetical hierarchy
The Arithmetical Hierarchy—e.g., see Budnik (
2006)—is usually developed with the universal (
\(\forall\)) and existential (
\(\exists\)) quantifiers restricted to the integers. Levels in the Arithmetical Hierarchy are labeled as
\(\varSigma _n\) if they can be defined by expressions beginning with a sequence of
n alternating quantifiers starting with
\(\exists\); levels are labeled as
\(\varPi _n\) if they can be defined by such expressions of
n alternating quantifiers that start with
\(\forall\).
\(\varSigma _0\) and
\(\varPi _0\) are defined as having no quantifiers and are equivalent.
\(\varSigma _1\) and
\(\varPi _1\) only have the single quantifier
\(\exists\) and
\(\forall\), respectively. We only need to consider alternating pairs of the quantifiers
\(\forall\) and
\(\exists\) because two quantifiers of the same type occurring together are equivalent to a single quantifier.
4 Extended spiking neural P systems
The reader is supposed to be familiar with basic elements of membrane computing, e.g., from Păun (
2002) and Păun et al. (
2010); comprehensive information can be found on the P systems web page (
www.ppage.psystems.eu). Moreover, for the motivation and the biological background of spiking neural P systems we refer the reader to Ionescu et al. (
2006). The definition of an
extended spiking neural P system is mainly taken from Alhazov et al. (
2006), with the number of spikes
k still be given in the “classical” way as
\(a^k\); later on, we simple will use the number
k itself only instead of
\(a^k\).
The definitions given in the following are taken from Alhazov et al. (
2006).
In the original model introduced in Ionescu et al. (
2006), in the productions
\(\left( l,w,t\right)\) of a rule
\(\left( i,E/a^k\rightarrow \left\{ \left( l,w,t\right) \right\} ;d\right)\), only
\(w=a\) (for
spiking rules) or
\(w=\lambda\) (for
forgetting rules) as well as
\(t=0\) was allowed (and for forgetting rules, the checking set
E had to be finite and disjoint from all other sets
E in rules assigned to neuron
i). Moreover, reflexive axons, i.e., leading from neuron
i to neuron
i, were not allowed, hence, for
\(\left( l,w,t\right)\) being a production in a rule
\(\left( i,E/a^k\rightarrow P;d\right)\) for neuron
i,
l \(\ne i\) was required. Yet the most important extension is that different rules for neuron
i may affect different axons leaving from it whereas in the original model the structure of the axons (called synapses there) was fixed. In Alhazov et al. (
2006), the sequence of substeps leading from one configuration to the next one together with the interpretation of the rules from
R was taken in such a way that the original model can be interpreted in a consistent way within the extended model introduced in that paper. As mentioned in Alhazov et al. (
2006), from a mathematical point of view, another interpretation would have been even more suitable: whenever a rule
\(\left( i,E/a^k\rightarrow P;d\right)\) is activated, the packages induced by the productions
\(\left( l,w,t\right)\) in the set
P of a rule
\(\left( i,E/a^k\rightarrow P;d\right)\) activated in a computation step are immediately put on the axon from neuron
i to neuron
l, whereas the delay
d only indicates the refraction time for neuron
i itself, i.e., the time period this neuron will be closed. The delay
t in productions
\(\left( l,w,t\right)\) can be used to replace the delay in the neurons themselves in many of the constructions elaborated, for example, in Ionescu et al. (
2006), Păun et al. (
2006), and Chen et al. (
2006). Yet as in (the proofs of computational completeness given in) Alhazov et al. (
2006), we shall not need any of the delay features in this paper, hence we need not go into the details of these variants of interpreting the delays.
Depending on the purpose the ESNP system is to be used, some more features have to be specified: for generating
k-dimensional vectors of non-negative integers, we have to designate
k neurons as
output neurons; the other neurons then will also be called
actor neurons. There are several possibilities to define how the output values are computed; according to Ionescu et al. (
2006), we can take the distance between the first two spikes in an output neuron to define its value. As in Alhazov et al. (
2006), also in this paper, we take the number of spikes at the end of a successful computation in the neuron as the output value. For generating strings, we do not interpret the spike train of a single output neuron as done, for example, in Chen et al. (
2006), but instead consider the sequence of spikes in the output neurons each of them corresponding to a specific terminal symbol; if more than one output neuron spikes, we take any permutation of the corresponding symbols as the next substring of the string to be generated.
4.1 ESNP systems as generating devices
As in Alhazov et al. (
2006), we first consider extended spiking neural P systems as generating devices. The following example gives a characterization of regular sets of non-negative integers:
The following results were already proved in Alhazov et al. (
2006):
Besides these results already established in Alhazov et al. (
2006), we now prove a characterization of languages and sets of (vectors of) natural numbers generated by ESNPS with only one neuron. Roughly speaking, having only one actor neuron corresponds with, besides output registers, having only one register which can be decremented.
Proof
First we notice that the delays would not matter: the overall system is sequential, and therefore it is always possible to pre-compute what happens until the actor neuron re-opens; the weight of all pending packages is also bounded. All the details of storing and managing all these features by the finite control of the register machines are tedious, but very much straightforward. In the following, we therefore assume that the ESNPS is given as:
$$\begin{aligned} \varPi= & {} (n+1,S,R),\\ S= & {} \{(1,m_1),\ldots ,(n,m_n),(n+1,m_{n+1})\},\\ R= & {} \{(n+1,E_r/i_r\rightarrow \{(1,p_{r,1}),\ldots ,(n,p_{r,n}),\\&\ (n+1,p_{r,n+1})\})\mid 1\le r\le q\}. \end{aligned}$$
Thus, given
n,
\(\varPi\) can be specified by the following non-negative integers: the number
q of rules, initial spikes
\(m_1,\ldots ,m_n,m_{n+1}\), and, for every rule
r, the following ingredients: the number
\(i_r\) of consumed spikes, the numbers
\(p_{r,1},\ldots ,p_{r,n+1}\) of produced spikes, and the regular sets
\(E_r\) of numbers. Note that, as it will be obvious later, it is enough to only consider the case
\(m_1=\cdots =m_n=0\), because otherwise placing the initial spikes can be done by a 1-register machine in a preparatory phase, before switching to the instruction corresponding to starting the simulation.
The main challenge of the construction is to remember the actual “status” of the regular checking sets. It is known that every regular set E of numbers is semilinear, and it is possible to write \(E_r=\bigcup _{j=1}^{l_r}(k_r{\mathbb{N}}+d_{r,j})\cup D_r\), i.e., all the linear sets constituting \(E_r\) can be reduced to a common period \(k_r\), and an additional finite set. Then, we can take a common multiple k of periods \(k_r\), and represent each checking set as \(E_r=\left( k{\mathbb{N}}_++\{d'_{r,j}\mid 1\le j\le l'_r\}\right) \cup D'_r\), where \(D'_r\) is finite.
Finally, take a number
M such that
M is a multiple of
k, that
M is larger than any element of
\(D_r\),
\(1\le r\le q\), that
M is larger than any number
\(d'_{r,j}\),
\(1\le j\le l'_r\),
\(1\le r\le q\), that
M is larger than any of
\(i_r\) and
\(p_{r,n+1}\),
\(1\le r\le q\). Then, if neuron
\(n+1\) has
N spikes, the following properties hold:
-
rule r is applicable if and only if \(N\in E_r\) in case when \(i_r\le N<M\), and if and only if \(M+(N\,{\mathrm{mod}}\,M)\in E_r\) in case when \(N\ge M\),
-
the difference between the number of spikes in neuron \(n+1\) in two successive configurations is not larger than M.
For neuron
\(n+1\),
\(Mk+j\) spikes (where
\(0\le j\le M-1\)) will be represented by value
k of register 1 and state
j.
We simulate \(\varPi\) by a register machine R with one register and an output tape of m symbols. Before we proceed, we need to remark that, without restricting the generality, we may have an arbitrary set of “next instructions” instead of \(\{l_2,l_3\}\) in \(l_1:(ADD(r),l_2,l_3)\), and arbitrary sets of “next instructions” instead of \(\{l_2\}\) and \(\{l_3\}\) in \(l_1:(SUB(r),l_2,l_3)\). Indeed, non-determinism between choice of multiple instructions can be implemented by an increment followed by a decrement in each case, as many times as needed for the corresponding set of “next instructions”. Clearly, \(l_1:(ADD(r),\{l_2\})\) is just a shorter form of \(l_1:(ADD(r),l_2,l_2)\).
Finally, besides instructions ADD(r), SUB(r), write(a) and halt, we introduce the notation of NOP, meaning only a switch to a different instruction without modifying the register. This will greatly simplify the construction below, and such a notation can be reduced to either compressing the rules (by substituting the instruction label with the label of the next instruction in all other instructions), or be simulated by an ADD(1) instruction, followed by a SUB(1) instruction.
We take \(b(m_{n+1}\,{\mathrm{mod}}\,M)\) as the starting state of R, and the starting value of register 1 is \(m_{n+1}{\mathrm{div}}\ M\).
For every class modulo
M,
\(0\le j\le M-1\), we define sets
$$\begin{aligned} L_{j,0}= &\, {} \{l_{r,0}\mid 1\le r\le q,\ j\in E_r,\ i_r\ge j\},\\ L_{j,+}= &\, {} \{l_{r,+}\mid 1\le r\le q,\ j+M\in E_r\} \end{aligned}$$
of applicable rules corresponding to remainder
j, subscripts 0 and
\(+\) represent cases of having less than
M spikes, and at least
M spikes, respectively. Let us redefine any of these sets to
\(\{l_h\}\) if the expression above is empty.
We proceed with the actual simulation. A rule
$$\begin{aligned} \left( n+1,E_r/i_r\rightarrow \left\{ (1,p_{r,1}),\ldots ,(n,p_{r,n}), (n+1,p_{r,n+1})\right\} \right) \end{aligned}$$
can be simulated by the following rules of
R:
$$\begin{aligned}&b(j):(S(1),L_{j,+},L_{j,0}),\quad l_r\in L_{j,0};\\&\quad l_{r,\alpha }:\ldots , (\text{a sequence of } \,p_{r_1} \,\text{instructions }\\&\quad \ldots , write(a_1), \ldots , p_{r_n} \,\text{instructions} write(a_n),\\&\quad \ldots l'_{r,\alpha },\text{and} p_{r_{n+1}} \text{instructions } ADD(1)), \alpha \in \{0,+\};\\&\quad l'_{r,+}:(NOP,\{b((j-i_r+p_{r,n+1}){\mathrm{mod}}\,M)\}),\\&\quad \text{ if } j-i_r+p_{r,n+1}<0;\\&\quad l'_{r,+}:(ADD(1),\{l'_{r,0}\}), \text{ if } j-i_r+p_{r,n+1}<M;\\&\quad l'_{r,0}:(NOP,\{b((j-i_r+p_{r,n+1}){\mathrm{mod }}\, M)\}),\\&\quad \text{ if } j-i_r+p_{r,n+1}<M;\\&\quad l'_{r,0}:(ADD(1),\{b((j-i_r+p_{r,n+1}){\mathrm{mod}}\, M)\}),\\&\quad \text{ if } j-i_r+p_{r,n+1}\ge M;\\&\quad l_h:halt. \end{aligned}$$
Indeed, instruction
b(
j) corresponds to checking whether neuron
\(n+1\) has at least
M spikes, transitioning into the halting instruction, or into the set of instructions associated with the corresponding applicable rules, in the context of the result of the checking mentioned above. Sending spikes to output neurons is simulated by writing the corresponding symbols on the tape. This goal is obtained, knowing values
j,
\(i_r\),
\(p_{r,n+1}\), and whether neuron 1 had at least
M spikes or not, by transitioning to instruction
\(b((j-i_r+p_{r,n+1}){\mathrm{mod}}\, M)\) after incrementing register 1 the needed number of times (0, 1 or 2), which is equal to
\(\left( j-i_r+p_{r,n+1}{\mathrm{div}}\ M\right) +d\), where
\(d=0\) if neuron 1 had at least
M spikes, and
\(d=1\) otherwise (to compensate for the subtraction done by instruction
b(
j) in the initial checking). The simulation of instructions continues until we reach the situation where no rules of the underlying spiking system are applicable, transitioning to some
\(L_{j,\alpha }=\{l_h\}\).
Finally, let us formally describe the instruction sequences from
\(l_{r,\alpha }\) to
\(l'_{r,\alpha }\). For the sake of simplicity of notation, we do not mention subscripts
\(r,\alpha\) in the notation of the intermediate instructions, keeping in mind that these are different instructions for different
\(r,\alpha\). The difficulty for generating the string languages is that, by the definition, all permutations are to be considered if spikes are sent to multiple neurons
\(1,\ldots ,m\).
$$\begin{aligned}&l_{r,\alpha }:(NOP,\{s(p_{r_1},\ldots ,p_{r_n})\});\\&\quad s(i_1,\ldots ,i_n):\\&\quad \ (NOP,\{s^k(i_1,\ldots ,i_n) \mid i_k>0,\ 1\le k\le n\}),\\&\quad 0\le i_j\le p_{r_j},\ 1\le j\le n, (i_1,\ldots ,i_n)\ne (0,\ldots ,0);\\&\quad s^{(k)}(i_1,\ldots ,i_n):(write(a_k),\{s(i'_1,\ldots ,i'_n)\}),\\&\quad i'_k=i_k-1, \text{ and } i'_j=i_j,\quad 1\le j\le n,\ j\ne k,\\&\quad 0\le i_j\le p_{r_j},\ 1\le j\le n, (i_1,\ldots ,i_n)\ne (0,\ldots ,0);\\&\quad s(0,\ldots ,0):(NOP,\{t(p_{r_{n+1}})\});\\&\quad t(i):(ADD(n+1),t(i-1)),\quad 1\le i\le p_{r_{n+1}};\\&\quad t(0):(NOP,l'_{r,\alpha }). \end{aligned}$$
The rules above describe precisely the following behavior: to produce any sequence with the desired numbers of occurrences of symbols
\(a_1,\ldots ,a_n\), a symbol is non-deterministically chosen (out of those, the current desired number of occurrences of which is positive) and written, iterating until all desired symbols are written.
Next, the register is incremented the needed number of times. This finishes the explanation of the instruction sequences from \(l_{r,\alpha }\) to \(l'_{r,\alpha }\), as well as the explanation of the simulation.
Therefore, the class of languages generated by ESNP systems with only one neuron containing rules and n output neurons is included in the class of languages generated by 1-register machines with an output tape of n symbols.
Applying Parikh mapping to both classes, just replacing write-instructions by ADD-instructions on new registers associated with these symbols, it follows that the class of sets of vectors generated by ESNP systems with only one neuron containing rules and n output neurons is included in the class of sets of vectors generated by \(n+1\)-register machines where all registers except one are restricted to be increment-only. These observations conclude the proof. \(\square\)
The inclusions formulated at the end of the proof given above are actually characterizations, as we can also prove the opposite inclusion.
5 ESNP systems with white hole rules
In this section, we recall the definition of extended spiking neural P systems with white hole rules as introduced in Alhazov et al. (
2015a). We will show that with this new variant of extended spiking neural P systems, computational completeness can already be obtained with only one actor neuron, by proving that the computations of any register machines can already be simulated in only one neuron equipped with the most general variant of white hole rules. Using this single actor neuron to also extract the final result of a computation, we even obtain weak universality with only one neuron.
As already mentioned in Remark 1, we are going to describe the checking sets and the number of spikes by non-negative integers. The following definition is an extension of Definition
1:
Allowing the white hole rules having productions being of the form \(w=\left( all +p\right) \cdot q+z\) with \(p,q,z\in \mathbb{Q}\) is a very general variant, which can be restricted in many ways, for example, by taking \(z\in \mathbb{Z}\) or omitting any of the rational numbers \(p,q,z\in \mathbb{Q}\) or demanding them to be in \({\mathbb{N}}\) etc.
Obviously, every ESNP system also is an EESNP system, but without white hole rules, and a finite EESNP system also is a finite ESNP system, as in this case the effect of white hole rules is also bounded, i.e., even with allowing the use of white hole rules, the following lemma as a counterpart of Lemma
3 is still valid:
Hence, in the following our main interest is in EESNP systems which really make use of the whole power of white hole rules.
EESNP systems can also be used for computing functions, not only for generating sets of (vectors of) integer numbers. As a simple example, we show how the function \(n\mapsto 2^{n+1}\) can be computed by a deterministic EESPNS, which only has exactly one rule in each of its two neurons; the output neuron 2 in this case is not free of rules.
5.1 Pure white hole model
To consider the generalization of the example above to multiple neurons, we first would like to recall a related model considered in Klejn and Rozenberg (
1980) already in 1980, for the case of L systems, calling them 0
LIP systems: like in Indian parallel grammars, all identical symbols simultaneously evolve by the
same rule, but like in Lindenmayer systems, all symbols evolve in parallel. We also note that in the area of P systems such a requirement may be viewed as a special case of the
label agreement feature. Label selection, target selection, and target agreement have extensively been studied, for example, see Alhazov and Freund (
2014,
2015); hence, it is proper to call it
rule agreement, as studied, e.g., in Alhazov et al. (
2015b).
Clearly, as a particular case with \(n=1\), we get the previous example covering DTU0L.
5.2 Computational completeness of EESNP systems
The following main result was already established in Alhazov et al. (
2015a).
Based on the preceding main result, i.e., Lemma
8, the following theorems were proved in Alhazov et al. (
2015a).
6 Red–green EESNP systems
For defining a suitable model of red–green EESNP systems we have to consider several constraints.
First of all, the computations should be deterministic, i.e., for any configuration of the EESNP system \(\varPi\) there should be at most one rule applicable in each neuron. This condition can be fulfilled syntactically by requiring the checking sets of all the rules in each neuron to be disjoint.
Whereas in the generating case we had one output neuron for each possible input symbol, these specific neurons now have to act as input neurons. As we only want deterministic behavior to be considered now, we assume that in every derivation step at most one input neuron spikes until the whole input is “read”, but this input has to be made “on demand”, i.e., we imagine that the EESNP system \(\varPi\) sends out an input request to the environment which is answered in the next step by the spiking of exactly one input neuron as long as the string has not been “read” completely.
“Reading” the spiking of an input neuron into the single actor neuron means that we have to be able to distinguish the signals coming from different input neurons. Hence, the simplest variant to do this is to multiply the spike coming from input neuron number k by k. Yet then we have to take into account that the minimum value in the actor neuron must be bigger than the maximal number k, i.e., the smallest prime number used for the prime number encoding must fulfill this condition, and our encoding of the number \(n_i\) now is chosen to be \({p_i}^{n_i+1}\).
Finally, we have to define red and green “states” of the red–green EESNP system; yet as we only have a finite number of rules in each neuron, each of the possible vectors of rules represents a color; hence, the color of the current configuration, i.e., its “state”, can be defined via the (unique) vector of rules to be applied.
Based on the proof Lemma
8, we now can easily establish the following results, similar to the results obtained for red–green register machines, see Lemmas
1 and
2 as well as Theorem
3:
As an immediate consequence, the preceding two lemmas yield the characterization of \(\varSigma _2\) and \(\varSigma _2\cap \varPi _2\) by red–green EESNP systems: