# Spiking Neural P Systems with Polarizations and Rules on Synapses

Authors: Suxia Jiang; Jihui Fan; Yijun Liu; Yanfeng Wang; Fei Xu
Journal: Complexity
 (2020)

---

## Abstract

Spiking neural P systems are a class of computation models inspired by the biological neural systems, where spikes and spiking rules are in neurons. In this work, we propose a variant of spiking neural P systems, called spiking neural P systems with polarizations and rules on synapses (PSNRS P systems), where spiking rules are placed on synapses and neurons are associated with polarizations used to control the application of such spiking rules. The computation power of PSNRS P systems is investigated. It is proven that PSNRS P systems are Turing universal, both as number generating and accepting devices. Furthermore, a universal PSNRS P system with 151 neurons for computing any Turing computable functions is given. Compared with the case of SN P systems with polarizations but without spiking rules in neurons, less number of neurons are used to construct a universal PSNRS P system.


---

## Body

## 1. Introduction

Membrane computing is a burgeoning branch of natural computing that develops new computation models based on the structure and functioning of living cells [1, 2]. Membrane systems (also called P systems) are distributed parallel computation models in membrane computing. There are three main classes of P systems, based on the structure of membranes inside living cells: cell-like P systems [3], tissue-like P systems [4], and neural-like P systems [5]. In the field of mathematical and theoretical computer science, P systems are used to investigate numerous types of problems, such as the Turing universality of the system [6, 7], complexity classes [8], numerical problems [9, 10], NP-complete problems [11–13], and P systems simulation [14, 15]. The reader can consult [16] for more comprehensive information about membrane computing. Up-to-date research results and open problems can be found on the membrane computing website http://ppage.psystems.eu.Spiking neural P systems (SN P systems) are a class of neural-like P systems, inspired by the biological phenomenon of neurons conveying information by communicating with each other via identical electric impulses (spikes) [17]. In this type of systems, only one type of spike exists, and the information is encoded by the timing and number of spikes. SN P systems are a class of computation models that use spiking/forgetting rules, which is applied by matching the number of spikes with the regular expression. Many variants of SN P systems have been proposed based on various biological characteristics, such as scheduled synapses [18], structural plasticity [19, 20], thresholds [21, 22], and multiple channels [23]. Meanwhile, there are also extensive studies in the view of the mechanism of information communication between neurons, such as white hole neurons [24], request rules [25], inhibitory rules [26], and communication on request [27]. Most of these systems have been proven to have the equivalent computation power with Turing machine.In addition, SN P systems have been widely investigated in the field of computer science, which can be used to produce binary and string languages [28–31] and simulate the registration machine [32, 33]. With the development of the research, the SN P systems as small universal computing devices are studied [34, 35]. Moreover, SN P systems and their variants have been successfully implemented in real-life applications, for instance, logic gate design [36], image processing [37], fault diagnosis of electric power systems [38–40], optimization algorithm design for combinatorial optimization problems [41, 42], and robot control [43–46].Recently, a variant of SN P systems called SN P systems with polarizations (PSN P systems) was proposed in [47], where the rules are controlled by three electrical charges −,0,+ associated with each neuron, not by the regular expression; it is closer to biological reality. In PSN P systems, the use of rules is more limited compared with SN P systems, because only three electrical charges can be selected, but PSN P systems as number devices proved to be Turing universal. As universal computing devices, the computing process of PSN P systems is complicated, and a total of 164 neurons (computational resources) are consumed. It is an open problem whether to find such systems that consume less computational resources, such as using extended spiking rules and delay functions and so on. Herein, we are inspired by the functioning of reflex arcs; the brain sends different signals to different cells to elicit precise actions by the body when a stimulus enters the brain. This biological phenomenon was introduced into SN P systems in [48]; the rules are placed on the synapses, that is, the rules on synapses. However, the rules on the synapse are still triggered using the regular expression. If the use conditions of rules on synapses are weakened, what about the computation power of SN P systems with rules on synapses? Hence, it is also interesting to construct a variant of SN P systems with rules on synapses, where the rules are not controlled by the regular expression.In this work, inspired by the open problems raised in [47], we put the rules on synapses, proposing SN P systems with polarizations and rules on synapses (PSNRS P systems, for short). In PSNRS P systems, the rules associated with each neuron are placed on synapses, and when the polarity of a neuron meets some rules of its synapses, the rules are activated, and the neuron sends different number of spikes and the same electrical charge to its neighboring neurons. Compared with neurons in PSN P systems that can only send the same number of spikes at some point to its neighboring neurons, the rules on synapses in PSNRS P systems will be more flexible. We investigate the computation power of PSNRS P systems working in the maximally parallel mode. The main contributions of the present work are summarized as follows:(i)
Rules on synapses and polarizations are considered in SN P systems; we construct a variant of SN P systems, called SN P systems with polarizations and rules on synapses (PSNRS P systems). In PSNRS P systems, polarization is used to control the application of spiking/forgetting rules associated with each synapse of the neurons.(ii)
The computation power of PSNRS P systems is investigated. Specifically, we prove that PSNRS P systems as accepting devices and generating devices achieve universality. Furthermore, a universal PSNRS P system with 151 neurons for computable functions is presented. Compared to the PSN P system, 13 neurons were reduced in computational resources.The rest of this paper is organized as follows. The formal definition of PSNRS P systems is introduced in the next section. The computation power of PSNRS P systems as number generators and acceptors is investigated inSection 3. In Section 4, a small universal PSNRS P system for computable functions is given. Finally, conclusions and suggestions for further work are presented in Section 5.


## 2. Spiking Neural P Systems with Polarizations and Rules on Synapses

In this section, we first review some prerequisites. For details on the basic elements of membrane computing and automata theory, the reader can refer to [16, 49]. V∗ is the set of all words over the alphabet, including the empty string λ. V∗−λ corresponds to the set of nonempty words over V and is denoted by V+. The family of sets of natural numbers computed by Turing machines is denoted by NRE.In the following definition, the notions of polarity and rules on synapses will be used. Only a brief introduction is provided here; please refer to [47, 48, 50] for details.A PSNRS P system of degreem≥1 is a construction as follows:(1)Π=O,σ1,σ2,σ3,…,σm,syn,in,out,where(i)
O=a is an alphabet and a denotes the spike(ii)
σ1,σ2,σ3,…,σm are neurons of the form σi=αi,ni, 1≤i≤m (m is the number of neurons), where(a)
αi∈−,0,+ is the initial polarity of neuron σi(b)
ni is the number of spikes initially located in σi(iii)
syn∈1,2,3,…,m×1,2,3,…,m; syn is the sets of synapses; each element is a pair of the form i,j,Ri,j, where i,j indicates that there is a synapse connecting neurons σi and σj, with i,j∈1,2,…,m, i≠j, and Ri,j is a finite set of rules of the following two forms:(a)
α/ac⟶a;β, for α,β∈−,0,+, c≥1 (spiking rules)(b)
α/ac⟶λ;β, for α,β∈−,0,+, c≥1 (forgetting rules)(iv)
in,out∈1,2,…,m indicates the input and output neurons, respectivelyThe spiking rules are applied as follows. If neuronσi contains k spikes and has α charge (ak∈LE, k≥c), then the spiking rule α/ac⟶a;β is enabled. Meanwhile, c spikes from neuron σi are consumed, and a spike and β charge are sent to neuron σj via a synapse i,j. Note that each synapse can have rules, and they do not affect each other, indicating that neuron σi sends a difference charge to adjacent neurons.A forgetting ruleα/ac⟶λ;β is used when neuron σi maintains α charge and at least c spikes, so that all c spikes are removed from neuron σi and the β charge is sent to neuron σj by synapse i,j.At some point, if a rule fromRi,j can be used by a synapse i,j, the rule must be used. If several rules from Ri,j can be used by a synapse, these rules are chosen nondeterministically. For example, there are two firing rules, α1/ac⟶a/λ;β1 and α1/ac⟶a/λ;β2, in a synapse, with α1,β1,β2∈−,0,+, β1≠β2. The synapse nondeterministically applies one of the rules. Meanwhile, when some rules associated with several synapses originating from the same neuron can be applied, all rules that are applied consume the same number of spikes from the same neuron. In each unit of time, only one rule on each synapse is used. At the system level, rules are used in parallel at different synapses.In PSNRS P systems, the use of rules is determined by the polarity of neurons and the number of pulses located in neurons and no longer matches the regular expression by checking the number of pulses. More broadly, to use a rule, the total number of spikes inside the neuron should not be less than the number of spikes consumed by the rule. Moreover, the neurons send out not only spikes but also charges, even when using forgetting rules.Specifically, when a neuron receives a charge from neighboring neurons, the changes in the electrical charges connected to the neuron proceed as follows:(i)
Two or more positive charges (+) and two or more negative charges (−) lead to one positive charge (+) and one negative charge(−), respectively; several neutral charges (0) lead to one neutral charge (0)(ii)
One positive (+) and one negative charge (−) cancel each other and give the neutral charge (0)(iii)
One positive (+) or one negative charge (−) cannot be changed by a neutral charge (0)In this work, systemΠ is considered as a number generator. Usually, the time interval between the first two spikes output by the output neuron is used as the result of a computation. The number t2−t1 is said to be computed by systems Π, denoted by N2Π.In addition, systemΠ can work in an accepting mode, where the output neuron is removed. A number n is introduced in the system, by introducing a sequence 10n−11 in neuron σin. This number n is said to be accepted by system Π if the computation eventually halts. The set of numbers accepted by Π is denoted by NaccΠ.We denote the family of all sets of numbers generated or accepted by PSNRS P systems byNαsynPSNPmn, where the symbol α∈2,acc indicates the generating or accepting mode, syn represents rules on synapses, there are up to m neurons, and each neuron has up to n rules on its synapses. As usual, the indices m and n are replaced with ∗ when no bound is imposed on the corresponding parameter.


## 3. Computation Power of PSNRS P Systems

In this section, we mainly investigate the computation power of PSNRS P systems and prove that PSNRS P systems can generate all recursively enumerable sets of numbers.We first briefly review the definition of register machines. The construction of a register machine isM=m,H,l0,lh,I, where m indicates the number of registers, H indicates the set of instruction labels, l0 is the start label, lh is the halt label (assigned to instruction HALT), and I indicates the set of instructions (each of which is precisely labeled by an individual label from H). Each instruction is one of the following forms: ADD instruction li:ADDr,lj,lk indicates that the register r is added 1, and then the present instruction labeled with li passes to the next instruction lj or lk (being chosen nondeterministically); SUB instruction li:SUBr,lj,lk shows that the register r is subtracted 1 (if the register r is nonzero), and the present instruction labeled with li passes to the instruction lj, or else (if the register r is zero) the present instruction labeled with li passes to the instruction lk.It is known that register machines with three registers can precisely generate a family of sets of recursively enumerable natural numbers; in other words, it can characterizeNRE [34].Theorem 1.
N2synPSNP∗2=NRE.Proof.
We prove only the inclusionNRE⊆N2synPSNP∗2; the reverse inclusion can be invoked from the Church–Turing thesis. For this, a specific PSNRS P system Π is constructed to simulate a register machine M, and the register machine M=m,H,l0,lh,I is considered. Each register of M is associated with a neuron of Π; we represent the number n contained in register r by 2n spikes located in σr, and the instruction l of H corresponds to a neuron σl. Initially, all neurons are empty; when neuron σl is active, the instruction labeled with l starts. When two spikes are received by neuron σli, system Π starts to simulate instruction li:OPr,lj,lk (OP denotes one of the operations ADD and SUB), and either neuron σlj or σlk receives two spikes and a neutral charge, one of which is activated. Then, the system starts to simulate the corresponding instruction. During the simulation of M, when neuron σlh, which is associated with the halting label lh of M, is activated, the computation halts. Without any loss of generality, all registers other than register 1 are empty in the halting configuration, and register 1 is never decremented during the computation. The time interval between the first two spikes output by the output neuron σout is used as the computation result.
The PSNRS P systemΠ consists of the following three components: ADD, SUB, and FIN modules, shown in Figures 1–3, respectively.Figure 1
ADD module (simulatingli:ADDr,lj,lk).Figure 2
SUB module (simulatingli:SUBr,lj,lk).Figure 3
FIN module (ending the computation).In the following sections, we explain how these modules work.ADDmodule: simulating an ADD instruction li:ADDr,lj,lk.As shown in Figure1, suppose that an ADD instruction li:ADDr,lj,lk is simulated in step t, and neuron σli has a neutral charge and receives two spikes.At stept, neuron σli receives two spikes, rule 0/a2⟶a;0 on synapses li,C1 and li,C2 is applied, and then neuron σli sends one spike and a neutral charge to auxiliary neurons σc1 and σc2, respectively. At step t+1, auxiliary neurons σc1 and σc2 both receive one spike and a neutral charge, the polarity of which remain the same. Rule 0/a⟶a;0 is used on synapses C1,r and C2,r, and each of the neurons sends a spike to neuron σr. When the two spikes are received, the number of spikes in neuron σr is increased by two, simulating an increase in the number stored in register r by one. At the same time, neuron σc3 receives a spike from each of neurons σc1 and σc2. Rule 0/a⟶a;0 is applied on synapse C2,C3, and neuron σc2 sends a spike and a neutral charge to neuron σc3. Then, one of the rules 0/a⟶a;+ and 0/a⟶a;− on synapse C1,C3 is nondeterministically chosen and applied, and neuron σc1 sends a spike to neuron σc3. There are two possible cases depending on the polarity received by neuron σc3.Case I.
At stept+1, if rule 0/a⟶a;+ is used on synapse C1,C3, then neuron σc3 receives a spike and positive charge from neuron σc1, and the polarization of the neuron is changed from a neutral charge to a positive charge. At step t+2, neuron σc3 sends a spike to neuron σc4 via rule +/a2⟶a;0 on synapse C3,C4, and a spike is maintained in neuron σc4. At the same step, rule +/a2⟶a;+ is applied on synapse C3,C6, and neuron σc6 receives a spike and a positive charge. In this way, neuron σc6 accumulates a spike and changes to a neutral charge. At step t+3, neuron σlj receives two spikes from neurons σc4 and σc6, which both have a neutral charge. Meanwhile, by means of rule −/a⟶λ;−, neuron σc4 sends a negative charge to neurons σc3 and σc6, so the polarizations of neurons σc3 and σc6 are changed back to their original state. At the same step, rule is used via synapse C4,lj, and neuron σc4 sends a spike to neuron σlj. In this way, two spikes are present in neuron σlj, and system Π starts to simulate instruction lj of M.Case II.
At stept+1, if rule 0/a⟶a;− can be enabled on synapse C1,C3, a spike and a negative charge are sent to neuron σc3. At step t+2, neuron σc5 receives a spike via synapse C3,C5 via rule −/a2⟶a;0. At the same step, neuron σc3 sends a spike and negative charge to neuron σc7 along synapse C3,C7 by rule −/a2⟶a;−; afterwards, neuron σc7 has a neutral charge. At step t+3, rule +/a⟶λ;+ is applied on synapse C5,C3, and neuron σc3 receives a positive charge and returns the original state. Similarly, neuron σc5 executes the same rule for neuron σc7 via synapse C5,C7. Otherwise, neuron σlk receives two spikes from neurons σc5 and σc7 by rules 0/a⟶a;0 and +/a⟶a;0 via synapses C5,lk and C7,lk. In this way, the system Π starts to simulate instruction lk of M.
Therefore, the ADD module can correctly simulate ADD instructions: in neuronσr, the number of spikes is increased by two; meanwhile, one of two neurons σlj and σlk nondeterministically receives two spikes.
SUBmodule: simulating a SUB instruction li:SUBr,lj,lk.
In this section, we will describe the SUB module, as shown in Figure2. Suppose that a SUB instruction li:SUBr,lj,lk is simulated and neuron σli receives two spikes at step t. Initially, neuron σli fires, sending spikes to neuron σc2 and neuron σr using rule 0/a2⟶a;+ on synapses li,C2 and li,r. However, neuron σc2 maintains a positive charge, and neuron σr is changed to a positive charge. At the same step, rule 0/a2⟶a;− is applied on synapse li,C1, and neuron σc1 receives a spike from neuron σli. According to the number of spikes in neuron σr, the following two cases are considered.Case I.
At stept+1, neuron σr has 2n + 1(n≥0) spikes (corresponding to the number stored in register r, being n). In this way, neuron σr has a positive charge, rule +/a3⟶λ;+ is applied on synapse r,C3, and neuron σc2, which has a positive charge, sends a spike and a negative charge to neuron σc3. Note that neuron σc3 maintains a neutral charge when a positive charge meets a negative charge, resulting in a spike in neuron σc3. Simultaneously, neuron σr fires, sending a spike to neuron σc4 via rule +/a3⟶a;+ on synapse r,C4. At the same step, neuron σc1 sends a negative charge to neuron σr, and the initial state of neuron σr is recovered to avoid inaccurate operation. At step t+2, neuron σc4 is activated by rule +/a⟶a;0 on synapse C4,lj, sending a spike to neuron σlj; meanwhile, neuron σc3 sends a spike to neuron σlj via rule 0/a⟶a;0 on synapse C3,lj. Neuron σlj receives two spikes, which indicates that system Π simulates the instruction lj of M.Case II.
At stept+1, neuron σr has a spike (corresponding to the number stored in register r being 0). Then, a negative charge is sent to neuron σr via rule −/a⟶λ;− on synapse C1,r, and neuron σr returns to the initial state when a positive charge meets a negative charge. At the same step, neuron σc2 is activated by rule +/a⟶a,− on synapse C2,C3, sending a spike and a negative charge to neuron σc3. At step t+2, rule −/a⟶a;− is enabled on synapse C3,C5, and neuron σc3 sends a spike and a negative charge to neuron σc5. At step t+3, neuron σc5 fires, sending a spike to neurons σr and σc6 by rules −/a⟶a;− and −/a⟶a;+ on synapses C5,r and C5,C6. Then, there are two spikes in neuron σr with a neutral charge and a spike in neuron σc6. At step t+4, rule −/a2⟶a;− is applied via synapse r,C7, and a spike is sent to neuron σc7 from neuron σr. Simultaneously, neuron σc8 receives a spike from neuron σc6 by rule +/a⟶a;0 on synapse C6,C8. Meanwhile, neuron σc6 sends a positive charge to neurons σr and σc3, restoring their initial states. At step t+5, neuron σlk receives two spikes from neurons σc7 and σc8 via rule −/a⟶a;0 on synapses C7,lk and C8,lk. In this way, system Π simulates the instruction lk.
The simulation of the SUB instructionli:SUBr,lj,lk is correct: system Π starts with neuron σli having two spikes inside and ends with sending two spikes and a neutral charge to neuron σlj (if the number located in register r is greater than 0, the register r is decreased by one) or sending two spikes and a neutral charge to neuron σlk (if the number located in register r is 0).
Obviously, there is no interference between the ADD and SUB modules, but interferences exist between two SUB modules. If there are two SUB instructionsls acting on register r, neurons σc4 and σc7 associated with register r send synapses to neurons σs3 and σs4, respectively. In the SUB module associated with ls (ls≠li), when we simulate a SUB instruction li:SUBr,lj,lk, all neurons except neurons σs3 and σs4 receive no spikes and charges.
It is important to note that the synapses and their rules associated with neuronsσs3 and σs4 are not shown in Figure 2; for example, neurons σs3 and σs4 exist between any two subtraction modules, and the rule +/a⟶λ;0 is present on the synapse of such two neurons, respectively. Neurons σs3 and σs4 only consume spikes and restore neutral charge, not affecting other neurons’ states. Moreover, the synapses of neurons σs3 and σs4 may be connected to any neuron in the environment or neurons related to SUB instruction ls; that is to say, the synaptic connections between neuron σs3 (or σs4) and other neurons cannot be described in Figure 2.
Whenn>0 spikes are present in neuron r, neuron σc4 sends a spike and a neutral charge to neuron σs3; therefore, neuron σs3 fires, rule +/a⟶λ;0 (not shown in Figure 2) is enabled, then one spike a is forgotten, and neuron σs3 returns to the initial state. If no spike exists in neuron r, neuron σs4 receives a spike and a neutral charge from neuron σc7, rule +/a⟶λ;0 is enabled, and one spike a is forgotten. Next, neurons σs3 and σs4 return to their initial state with respect to the initial number of spikes. Consequently, there is no interference between the SUB modules.
FINmodule: outputting the result of the computation.
As shown in Figure3, the FIN module is constructed. Assume that the computation halts; in other words, the halt instruction lh is reached and the result of the computation is stored in register 1 (register 1 contains n spikes). Neuron σlh receives two spikes and a neutral charge at step t, rule 0/a2⟶a;0 on synapse lh,C2 is activated, and neuron σlh sends a spike and a neutral charge to neuron σc2. At that moment, neuron σlh fires, sending a positive charge to neuron σ1 via rule 0/a2⟶λ;+ on synapse lh,1. Meanwhile, neuron σc1 receives a spike and a positive charge from neuron σlh by rule 0/a2⟶a;+ via synapse lh,C1. At step t+1, neuron σc2 sends a spike and a neutral charge to neuron σc3 via synapse C2,C3 by rule 0/a⟶a;0. Simultaneously, neuron σ1 sends a spike and a positive charge to neurons σc1 and σc4 via rule +/a2⟶a;+. Meanwhile, rule +/a⟶a;− on synapse C1,C4 is enabled, and neuron σc4 receives a spike and a negative charge from neuron σc1.
At that moment, a positive charge and a negative charge meet in neuronσc4, which therefore has a neutral charge and two spikes. At step t+2, rule 0/a⟶a;0 on synapse C3,out is applied, and a spike is sent from neuron σout. Meanwhile, neuron σc4 fires, sending no spike and a neutral charge to neuron .σc5 via rule 0/a2⟶λ;0 on synapse C4,C5. At step t+3, rule 0/a⟶a;0 is applied, and neuron σout sends the first spike to the environment. At the same time, neuron σc4 receives two spikes from neurons σ1 and σc1.
From stept+3 to step t+n+1, the spike of neuron σ1 is exhausted by rule 0/a2⟶λ;0 on synapse C4,C5. At step t+n+1, neuron σc4 receives a spike and negative charge from neuron σc1. Then, neuron σc4, which now has a negative charge, sends a spike and a neuron charge to neurons σout and σc5 by rule −/a⟶a;0 on synapses C4,out and C4,C5 at step t+n+2. At step t+n+3, neuron σc5 fires, sending a negative charge via synapses C5,1 and C5,C1 and restoring the initial state of charge. Meanwhile, neuron σout sends the second spike to the environment by rule 0/a⟶a;0. Hence, the interval at which two spikes are sent to the environment by the system Π is t+n+3−t+3=n, where n is exactly the number stored in register 1, i.e., corresponding to the result computed by system. Therefore, the register machine M is correctly simulated by the system Π, NM=N2Π.Theorem 2.
NaccsynPSNP∗2=NRE.Proof.
A PSNRS P systemΠ′, working in the accepting mode, is constructed to simulate a deterministic register machine M=m,H,l0,lh,I. The system Π′ contains an INPUT module, a deterministic ADD module, and a SUB module. The INPUT module is shown in Figure 4. Spike train 10n−11 is introduced into Π′ by means of neuron σin. In this system, the time interval of the first two spikes introduced by the INPUT module is used as the computing result.
At stept, we suppose that neuron σin receives the first spike from the environment. Neuron σin fires, sending a spike and neutral charge to neuron σin1 via rule 0/a⟶a;0 on synapse in,in1. At the same step, rule 0/a⟶a;− is applied on synapses in,in5 and in,in6. A spike is sent to neurons σin5 and σin6, and their polarity is changed to a negative charge. Similarly, neurons σin4 and σin7 receive one spike and a neutral charge from neuron σin via rules 0/a⟶a;0 (corresponding to synapses in,in4 and in,in7). At step t+1, neurons σin2 and σin3 receive a spike and neutral charge from neuron σin1, respectively. Meanwhile, neuron σin5 fires, rule −/a⟶a;0 is applied on synapses in5,in6 and in5,1, and neurons σin6 and σ1 receive a spike and a neutral charge from neuron σin5, respectively. Similarly, neurons σin5 and σ1 receive a spike and a neutral charge by rule −/a⟶a;0 on synapses in6,in5 and in6,1. From step t+1 on, neurons σin5 and σin6 exchange one spike with each other, and neuron σ1 receives two spikes in each step. In this case, at step t+n−1, neuron σin receives the second spike from the environment. Then, neurons σin4, σin5, σin6, and σin7 receive the second spike and accumulate two spikes. Note that neuron σ1 still receives spikes at step t+n, and there are 2n spikes in neuron σ1, which represents the number stored in register 1 of M.
At the same step, neuronsσin4 and σin7 send a positive charge to neurons σin5 and σin6, respectively, restoring their original states of charge. Meanwhile, neurons σin2 and σin3 have spikes according to rule 0/a⟶a;0 on synapses in1,in2 and in1,in3. At step t+n+1, the spikes in neurons σin5 and σin6 are depleted by rule 0/a2⟶λ;0 on synapses in5,1 and in6,1.
At the same step, neuronσl0 receives two spikes and a neutral charge from neurons σin2 and σin3 by rule 0/a2⟶a;0. In this way, neuron σl0 receives two spikes and the system simulates the initial instruction l0 of M.
For a deterministic ADD instruction of the formli:ADDr,lj, the corresponding ADD module shown in Figure 5 is simpler than that shown in Figure 1. Hence, we do not consider the details here.
In systemΠ′, the SUB module remains unchanged as shown in Figure 2, and neuron σlh remains in the system; however, the FIN module is removed. There is no rule in neuron σlh. When neuron σlh receives two neurons and no rules are available, the computation stops. The computing result introduced is t+n+1−t+1=n, which means that the number accepted by system Π′ is n. The operation process of INPUT module is shown in Table 1.
According to the above description, the register machineM working in accepting mode can be correctly simulated by PSNRS P systems. Hence, the Theorem holds.Figure 4
INPUT module ofΠ′.Figure 5
ADD module ofΠ′.Table 1
Simulation for the INPUT module.
StepNeurons activeRules executedSynapsestin,0,a0/a⟶a;0in,in10/a⟶a;0in,in40/a⟶a;−in,in50/a⟶a;−in,in60/a⟶a;0in,in7t+1in1,0,a0/a⟶a;0in1,in20/a⟶a;0in1,in3in5,−,a−/a⟶a;0in5,in6−/a⟶a;0in5,1in6,−,a−/a⟶a;0in6,in5−/a⟶a;0in6,1t+2in5,−,a−/a⟶a;0in5,in6−/a⟶a;0in5,1in6,−,a−/a⟶a;0in6,in5−/a⟶a;0in6,1t+3⋯⋯⋯t+4in5,−,a−/a⟶a;0in5,in6−/a⟶a;0in5,1in6,−,a−/a⟶a;0in6,in5−/a⟶a;0in6,1t+n−1in,0,a0/a⟶a;0in,in10/a⟶a;0in,in40/a⟶a;−in,in50/a⟶a;−in,in60/a⟶a;0in,in7in5,−,a−/a⟶a;0in5,in6−/a⟶a;0in5,1in6,−,a−/a⟶a;0in6,in5−/a⟶a;0in6,1t+nin1,0,a0/a⟶a;0in1,in20/a⟶a;0in1,in3in5,−,a2−/a⟶a;0in5,in6−/a⟶a;0in5,1in6,−,a2−/a⟶a;0in6,in5−/a⟶a;0in6,1in4,+,a+/a⟶λ;+in4,in5in7,+,a+/a⟶λ;+in7,in6t+n+1in2,0,a20/a2⟶a;0in1,l0in3,0,a20/a2⟶a;0in1,l0in5,0,a20/a2⟶λ;0in5,1in6,0,a20/a2⟶λ;0in6,1


## 4. A Small Universal PSNRS P System

In this section, a small universal PSNRS P system of computing device is constructed. Generally, a register machineM is used to compute a Turing computable function f:Nk⟶N in the following way: arguments n1,n2,…,nk are introduced by the specified registers r1,r2,…,rk (representing the first k registers). We begin with the first instruction with label l0 and stop with the halt instruction with label lh (if we stop), and then the value of the function is stored in a specific register rt; beyond that, all other registers are empty. For further information about universal register machines for computable functions, readers can refer to [34].In the following proof of the universal result, we use a specific universal register machine mentioned in [34], as shown in Figure 6. The universal register machine is of the construct Mu=8,H,l0,lh,I, where there are 8 registers, numbered from 0 to 7, and 23 instructions; the last instruction is the halting one. As defined in [34], the input numbers are introduced in registers 1 and 2, and the result is stored in register 0 when the machine Mu halts.Figure 6
The universal register machineMu.According to the previous description, subtraction instructions are not allowed on the registers where the results are stored, but register 0 ofMu is subject to SUB instructions. Therefore, register machine Mu is modified into Mu′: a register with label 8 is added, and the halting instruction lh of Mu is replaced by the following instructions:(2)lh:SUB0,l22,lh′,l22:ADD8,lh,lh′:  HALT.In this way, the universal register machine Mu′ has 9 registers, 24 ADD and SUB instructions, and 25 labels. The result of the computation is stored in register 8, which is never decremented during the computation. Furthermore, the register machine Mu′ can be considered deterministic, and, without losing Turing completeness, the ADD instructions li:ADDr,lj,lk having lj=lk is denoted by the form li:ADDr;lj.Theorem 3.
There is a universal PSNRS P system with 151 neurons for computable functions.Proof.
A PSNRS P systemΠ′ is constructed to simulate the universal register machine Mu′, as shown in Figure 7. The system Π′ consists of seven modules: ADD, ADD-ADD, SUB, ADD-SUB, SUB-ADD, INPUT, and OUTPUT. The ADD module (resp., SUB module) is applied to simulate the ADD instruction (resp., SUB instruction) of Mu′; in a similar way, each module is applied to simulate its corresponding instruction. However, the INPUT module is used to introduce a spike train from the environment, and the OUTPUT module is used to output the computation result.
In systemΠ′, each register r corresponds to a neuron σr, and the number saved in register r is encoded by the number of spikes stored in neuron σr. Specifically, register r having the number n (n≥0) is equivalent to neuron σr containing 2n spikes. Moreover, a neuron σli in system Π′ is associated with each instruction li in Mu′. When neuron σli holds two spikes, the rules on synapses are enabled, which means system Π′ simulates the instruction li. Until two spikes and a neutral charge are received by neuron σlh′, the computation in Mu′ is simulated by system Π′. The number of spikes emitted from system Π′ into the environment is exactly the result computed by Mu′.
All modules are presented in graphical form, indicating the neurons and synapses with the associated sets of rules. In the initial configuration, there is no spike in each neuron.
The INPUT module, shown in Figure8, introduces 2gx and 2y spikes into neurons σ1 and σ2 by reading the spike train 10gx−310y−21, respectively. The module works as follows.
Initially, neuronσin receives one spike from the environment. Neuron σin fires, rule 0/a⟶a;0 is applied, and a spike and a neutral charge are sent to neurons σc1, σc2, σc3, σc7, σc8, σc9. Afterwards, neuron σc3 fires, sending a spike and a negative charge to neurons σc5 and σc6 by using rules 0/a⟶a;− via synapses C3,C5 and C3,C6. The neuron σc4 holds a spike, and no rule is used. Then, neurons σc5 and σc6 have neutral charge, and the rules 0/a⟶a;0 on synapses C5,C6 and C6,C5 can be enabled. From that moment on, neurons σc5 and σc6 exchange a spike and a neutral charge with each other until the neuron σc4 receives the second spikes. After gx−2 step, neuron σc4 receives second spike. One step later, the neuron σc4 receives a spike and neutral charge. Subsequently, rules +/a2⟶λ;+ on synapses C4,C5 and C4,C6 are applied, and neurons σc5 and σc6 are changed to positive charge. Rules +/a2⟶λ;0 can be enabled, removing two spikes in each of the neurons σc5 and σc6. At that moment, no rules associated with neuron σ1 can be used. In this way, 2gx spikes are introduced in neuron σ1.
When the second spike arrives in neuronsσc8 and σc9, rules +/a2⟶a;− on synapses C8,C9 and C9,C8 are applied, and then each one receives one spike and one negative charge; hence, they become neutral and contain one spike. From the next moment on, rules 0/a⟶a;0 are used, and neurons σc8 and σc9 emit a spike and a neutral charge to each other, in each step, until the third spike arrives in neurons σc7. After y−1 step, neuron σc7 gets the third spike, and rules +/a3⟶λ;− on synapses C7,C8 and C7,C9 can be applied. The neurons σc8 and σc9 have negative charge, and no rules are applied. At the same time, rules +/a3⟶λ;+ via synapses C7,C4, C7,C5, and C7,C6 are applied; neurons σc4, σc5, and σc6 still keep positive charge; and the extra spikes will be consumed by rules +/a2⟶λ;+ on synapse C4,C5 and +/a2⟶λ;0 via synapses C5,C6, C6,C5. In this way, 2y spikes have been loaded in neuron σ2. With a third spike into neurons σc1 and σc2, this two neurons fire, rules 0/a3⟶a;0 on synapses C1,l0 and C2,l0 can be enabled, the neuron l0 receives two spikes and a neutral charge, and the system starts to simulate the initial instruction l0 of Mu′.
For ADD and SUB modules, we will follow the ADD module in accepting mode as shown in Figure5 and the SUB module in generating mode as shown in Figure 2.
When neuronσlh′ receives two spikes, that is, the instruction lh′ is reached, the result of computation is store in register 8. The tasks of outputting the result is carried out by the OUTPUT module shown in Figure 9.
Assume that, at stept, the neuron σlh′ gets two spikes, rule 0/a2⟶a;0 on synapse lh′,8 is used, and neuron σ8 receives a spike and a neutral charge. Then, there are 2n+1 spikes in neuron σ8, it fires, using rules 0/a3⟶a;0 on synapses 8,out and 8,C1, and a spike and one neutral charge are sent to neurons σout and σc1. Then, neuron σc1 sends a spike and neutral charge to neurons σ8 and σout, so neuron σout emits a spike and neutral charge out by rule 0/a2⟶a;0, until n spikes are sent out. Note that neuron σ8 and neuron σc1 exchange a spike and neutral charge with each other, ensuring that neuron σout can emit all the results of computation for system Mu′.
Therefore, according to the above INPUT module, deterministic ADD module, SUB module, and OUTPUT module, we have used the following:(i)
9 neurons for 9 registers(ii)
25 neurons for 25 labels(iii)
8×14 neurons for 14 SUB instructions(iv)
2×10 neurons for 10 ADD instructions(v)
10 neurons in the INPUT module(vi)
2 neurons in the OUTPUT moduleAll these come to a total of 178 neurons.
This number can be slightly decreased by some code optimization, exploring some particularities of the register machineMu′.
For instance, the sequence of ADD instructions(3)l17:ADD2,l21,l21:ADD3,l18without any other instruction addressing the label l21, can be simulated by the module shown in Figure 10. Then, three neurons associated with label l21 can be saved.
There are also two pairs of ADD-SUB instructions:(4)l5:ADD5,l6,l6:SUB7,l7,l8,l9:ADD6,l10,l10:SUB4,l0,l11.
Each sequence of ADD-SUB instructions,(5)li:ADDr′,lg,lg:SUBr″,lj,lk,can be simulated by the ADD-SUB module shown in Figure 11.
In this way, we save the 6 neurons associated with labelsl6 and l10.
A similar operation is possible for the following six sequences of SUB-ADD instructions:(6)l0:SUB1,l1,l2,l1:ADD7,l0,l4:SUB6,l5,l3,l5:ADD5,l6,l6:SUB7,l7,l8,l7:ADD1,l4,l8:SUB6,l9,l0,l9:ADD6,l10,l14:SUB5,l16,l17,l16:ADD4,l11,lh:SUB1,l22,lh′,l22:ADD8,lh.
Each sequence of ADD-SUB instructions,(7)lg:SUBr″,lj,lk,li:ADDr′,lg,can be simulated by the SUB-ADD module given in Figure 12. In this way, we save 18 neurons associated with labels l1, l5, l7, l9, l16, l22.
Therefore, by using the ADD-ADD module, ADD-SUB module, and SUB-ADD module, we can totally save 27 neurons (3(ADD-ADD) + 6(ADD-SUB) + 18(SUB-ADD)). Then, the number of neurons can be decreased from 178 to 151.Figure 7
The general design of the universal PSNRS P systems.Figure 8
INPUT module ofΠ′.Figure 9
OUTPUT module ofΠ′.Figure 10
ADD-ADD module ofΠ′.Figure 11
The module simulating consecutive ADD-SUB instructions.Figure 12
The module simulating consecutive SUB-ADD instructions.


## 5. Conclusions and Remarks

A variant of SN P systems, called SN P systems with polarizations and rules on synapses (PSNRS P systems), is proposed. We prove that as number generating devices and accepting devices, SN P systems with polarizations and rules on synapses are Turing universal. Moreover, a small universal system with 151 neurons as computing function device is given. Compared with the small universal SN P systems with polarizations proposed in [47], by moving rules to synapses, 13 neurons were reduced.In the proof of Theorems1 and 2, only standard spiking rules are used. It is interesting to use extended rules to construct universal systems with fewer neurons. In this work, PSNRS P systems are used as number generating or accepting devices. It is of interest to investigate the computation power of PSNRS P systems as language generators or to control language generators.In general, some open problems about PSNRS P systems may be considered based on the results obtained in this work; for instance, it remains open whether the results about the universality of PSNRS P systems still hold with fewer neurons. The PSNRS P systems proved to be universal when using both spiking rules and forgetting rules; it is challenging to investigate whether PSNRS P systems are still universal when using only one type of rules. In this work, the systems work in the synchronous mode. It is of interest to study the computation power of PSNRS P systems working in asynchronous mode [51] or local synchronous mode [52].



---

*Source: 8742308-2020-07-09.xml*