# Universal Nonlinear Spiking Neural P Systems with Delays and Weights on Synapses

Authors: Liping Wang; Xiyu Liu; Yuzhen Zhao
Journal: Computational Intelligence and Neuroscience
 (2021)

---

## Abstract

The nonlinear spiking neural P systems (NSNP systems) are new types of computation models, in which the state of neurons is represented by real numbers, and nonlinear spiking rules handle the neuron’s firing. In this work, in order to improve computing performance, the weights and delays are introduced to the NSNP system, and universal nonlinear spiking neural P systems with delays and weights on synapses (NSNP-DW) are proposed. Weights are treated as multiplicative constants by which the number of spikes is increased when transiting across synapses, and delays take into account the speed at which the synapses between neurons transmit information. As a distributed parallel computing model, the Turing universality of the NSNP-DW system as number generating and accepting devices is proven. 47 and 43 neurons are sufficient for constructing two small universal NSNP-DW systems. The NSNP-DW system solving the Subset Sum problem is also presented in this work.


---

## Body

## 1. Introduction

Membrane computing (MC) is a representative of a new type of computing, abstracted from the phenomenon of signal transmission between cells in animals. It was proposed by Gheorghe Păun in 1998 and published in 2000 [1]. As a new type of natural computing, membrane computing has abundant model support [2–4] and is widely used in real life [5, 6]. The distributed computing model is named after the membrane system or P system. So far, P systems are mainly divided into three categories: cell-like P systems [7, 8], tissue-like P systems [9, 10], and neural-like P systems. Spiking neural P (SNP) systems [11], axon P systems [12], and dendrite P systems [13] are widely studied types of neural-like P systems. The research on SNP systems has been abundant for more than ten years. Similar to the spiking neural network (SNN), in the SNP system, neurons are activated, and the spikes are transmitted to other neurons along the synapse. SNP systems encode information through spikes in neurons. Intuitively, SNP systems are represented by a directed graph, where the nodes in the graph represent neurons, and the neurons are connected by arcs representing synapses. Neurons contain spikes and rules; two kinds of rules are used in SNP systems: firing rules E/ar⟶a and forgetting rules as⟶λ. Generating, accepting, and functional computing are the three working modes of SNP systems. It is worth mentioning that, by introducing neuron division, budding, or dissolution, the SNP system has been proven to be able to solve some computationally difficult problems, like SAT problem and Subset Sum problem [14, 15]. SNP can also solve many practical problems such as fault diagnosis of power systems [16–18], image processing [19, 20], and combination optimization problem [21]. Based on those innovative works, more and more scholars pay attention to SNP systems. Many variants of SNP systems have been proposed, and their computing power has also been proven.The generation of the SNP system itself is affected by the spike signal in biological phenomena. From the perspective of biological facts, Păun et al. considered another important component related to brain function, astrocytes, which implicitly control the number of spikes along the axon. The functional application of astrocytes in the SNP model was first introduced in 2007 [22]. In 2012, Pan et al. formally proposed SNP systems with astrocytes [23]. More discussions about this type of system have been formed, such as [24, 25]. For such systems, astrocytes influence computation by controlling the transmission of spikes on synapses. Considering the difference in the number of synapses connected between neurons, Pan et al. [26] previously proposed spiking neural P systems with weighted synapses. Then considering the mutual annihilation between spikes, Pan and Păun [27] used a pair of antispikes a,a¯ to explain the SNP system with antispikes. In the initial SNP system, there was a unique synapse connection between two neurons. Based on biological facts, Peng et al. [28] proposed that the synapse of each neuron can have an indefinite number of channels connected to subsequent neurons, and the SNP system with multiple channels was reasonably verified. Later, for the phenomenon that neurons carry positive and negative ions, the polarized SNP system was studied [29, 30]. In view of this neurophysiological observation, the speed of information transmission on the synapse is different. Song et al. [31] proposed spiking neural P systems with delay on synapses (SNP-DS) in 2020. On the other hand, driven by the ideas of mathematics and computing science, many variants of SNP systems make the SNP computing model with a parallel mechanism more powerful, for example, a complete arithmetic calculator constructed from SNP systems [32], SNP systems with random application of rules by introducing probability [33], homogeneous SNP systems with structural plasticity by adding and deleting connections between neurons [34], SNP systems with colored spikes by the idea of colored Petri nets [35], SNP systems with communication on request by using the parallel-cooperating grammar system to communicate on request [36], SNP systems with learning functions used to identify letters and symbols [37], and numerical SNP systems inspired by the numerical nature of the numerical P (NP) systems [38].For SNP systems and variants mentioned above, the number of spikes in neurons is in integer form. So the nonlinear spiking neural P (NSNP) systems were investigated by Peng et al. [39]. In this system, the nonnegative integer state of neurons is replaced by real numbers; the number of spikes consumed and generated is replaced by nonlinear functions. However, NSNP systems need 117 and 164 neurons to construct Turing universal systems as functional computing device and number generator, respectively. For a new heuristic computing model such as this one, computing power is an important measure. At the same time, as a computational model of exchanging space for time, the computing power of NSNP systems needs to be further improved.In this work, for the purpose of greater calculation power of NSNP systems, inspired by [26, 31], a novel P system, the nonlinear spiking neural P systems with delays and weights on synapses are proposed, abbreviated as NSNP-DW. In NSNP-DW systems, related to several factors, such as the dendrites’ length, the spikes emitted from the same firing neuron reach different postsynaptic neurons at different times. So delays on synapses are introduced into the NSNP systems. Also, the number of dendrites among a firing neuron and its postsynaptic neurons is different. Although the spikes emitted from one neuron are the same, postsynaptic neurons with different amounts of dendrites to the firing neuron receive different amounts of spikes. Therefore, weights on synapses are added to the NSNP systems, and weights are treated as multiplicative constants by which the number of spikes varies when transiting across synapses. Both of these elements play a role in enhancing the computing power of the system.Different from NSNP systems, the main novelties of this work are as follows:(i)
We propose a novel P system called universal nonlinear spiking neural P systems with delays and weights on synapses closer to biological neurons.(ii)
For the NSNP systems in [39], integer spikes are replaced by nonlinear functions. In the proposed NSNP-DW system, we find more applicable nonlinear functions that are also common in neural networks and machine learning, so as to abstract the complex responses generated by spikes.(iii)
We prove the computational power of the new P system; in addition, 47 and 43 neurons are successfully used for simulating function calculation and number generator, respectively.(iv)
Computational efficiency is also an important evaluation for a P system, usually considering whether the NP-complete problem can be solved in a feasible time. We prove the computational efficiency of the new P system by solving a typical NP-complete problem: Subset Sum problem in polynomial time. It is an attraction of P system solving computationally hard problems so quickly. This makes the NSNP-DW system another powerful tool to solve the NP-complete problem.The remaining contributions of the paper are reflected as follows:Section 2 briefly shares the relevant content of register machine. Section 3 proposes NSNP-DW systems and gives two intuitive examples. The computing power of NSNP-DW systems equivalent to the Turing machine is proven in Section 4. Section 5 verifies the universality of the NSNP-DW system using fewer neurons. The uniform solution of the Subset Sum using the NSNP-DW system is added in Section 6. Conclusion and follow-up research on the NSNP-DW system are explained in the last section.


## 2. Prerequisites

The elements of the formal language of the SNP system can be consulted in [11, 26]. Here, we only introduce some symbolic theories used in this work, such as Turing machine construction, execution instructions, and universal Turing machine.We show that the proposed NSNP-DW system as number generating and accepting device is equivalent to Turing machine. An arbitrary family of Turing computable natural numbers, defined as NRE, is a family of length sets for recursively enumerable languages. NRE can be characterized by a register machineM. The structure of the form M=m,H,l0,lh,I, where m is the number of registers, H denotes the instruction tag set, l0 is the starting label, lh is the halting instruction HALT, and I denotes the instruction set. Each instruction in I is one of the following three forms:(1)
li:ADDr,lj,lk (add 1 to register r and then execute nondeterministically the instruction with label lj or lk).(2)
li:SUBr,lj,lk (if register r is nonzero, then subtract 1 from it, and go to the instruction with label lj; otherwise, go to the instruction with label lk).(3)
lh:HALT (the halting instruction).By imitating the register machine, the universal NSNP-DW system was verified. When all the registers are empty, the calculation starts froml0, and the instructions in I are continuously executed until halting instruction lh. The number set generated by the register machine M is defined as Ngen. Nacc is the number set accepted by M; corresponding instruction li:ADDr,lj,lk is deterministic and can be expressed as li:ADDr,lj.Computable functionf:Nk⟶N (k is a natural number) can be calculated by the register machine. If the equation ψxy=Mugx,y is satisfied, where x and y are nonnegative integers and gx is a recursive function, then the register machine Mu is universal. A universal register machine Mu′ simulated by the NSNP-DW system is shown in Figure 1, consisting of 9 registers, 14 SUB instructions, 10 ADD instructions, and one HALT instruction.Figure 1
The universal register machineMu′.


## 3. NSNP-DW Systems

The materials and methods section should contain sufficient detail so that all procedures can be repeated. It may be divided into headed subsections if several methods are described.In the following, we provide the definition of the NSNP-DW system and related semantic explanations. An example shows the operation of the system more clearly.


### 3.1. Definition

The structure of the proposed NSNP-DW system with degreem≥1 is(1)Π=O,σ1,σ2,…,σm,syn,Dsyn,in,out,where(1)
O=a is the singleton alphabet (a denotes spike);(2)
σ1,σ2,…,σm are neurons, in the form of σi=xi,Ri for 1≤i≤m, where xi∈R+ is the initial value of spikes contained in neuron σi, indicating the initial state of neuron σi, and Ri is the finite set of spiking rules in the following form:(a)
Spiking/firing rules:E|apxi⟶aqxi, where E is the firing condition, pxi is a linear or nonlinear function, and qxi is a nonlinear function, and pxi≥qxi≥0.(b)
Forgetting rules:E|apxi⟶λ, for a linear or nonlinear function pxi.(3)
syn∈1,…,h×1,…,h×W is a synaptic expression with weight, where W=1,…,n, h=m∪environment. For any i,j,n∈syn, 1≤i,j≤h, i≠j, and n∈W.(4)
Dsyn represents the delay on synapse i,j, expressed in the form of a time number.(5)
in and out indicate the input and output neurons of the system, respectively.The NSNP-DW system can be visualized by a directed graphGΠ with nodes and arcs, where nodes are neurons and arcs represent synapse connections. In original SNP systems, the number of spikes is described by an integer. In NSNP-DW systems, besides integer, it can also be described by nonlinear functions. For the rules E|apxi⟶aqxi and E|apxi⟶λ in the NSNP-DW system, the firing condition E has two forms. (1) It is a regular expression like aa3+ to exactly “cover” the contents of the neuron. If E is exactly apxi, then E can be omitted. (2) It is a threshold for enabling the rule and exists in the form of a positive real number. In order to distinguish, we write the rules as T|apxi⟶aqxi and T|apxi⟶λ, T∈R+. Both types of rules can be used in this paper. We assume that xit is the spike value of neuron σi at step t. For firing rules T|apxi⟶aqxi, only when xit≥pxi and xit≥T are satisfied, the rule can be applicable. Intuitively speaking, when the firing rule is met, the neuron is fired, consuming pxi spikes (if the remaining xit−pxi spike can no longer enable the rule, it will disappear in the neuron) and sending out qxi spikes. Forgetting rules T|apxi⟶λ, qxi≡0 mean that spikes with value pxi are consumed but not generated in the neuron to which it belongs. There will inevitably be multiple rules (greater than or equal to 2) in a neuron, assuming two rules, corresponding to the thresholds of T1 and T2, respectively. (i) When T1≠T2 and both rules can be executed, the maximum threshold strategy is applied. For instance, if T1>T2, the rule with T1 takes precedence, and the rule with threshold T2 is not used. For this strategy, the forgetting rule is no exception. (ii) When T1=T2=T, nondeterministic rule selection strategy is enabled. That is, the rules with T1 and T2 need to be discussed separately.In addition, for the NSNP-DW system, weights and delays are reflected in synapses. For anyi,j,n∈syn, n is the weight on the synapse. If the spikes with value qxi are emitted by neuron σi, neuron σj will receive n×qxi spikes. The delay between synapses i,j is represented by Dsyn, Dsyn is in the form of a time number. If there is a delay between neurons σi and σj, the spiking rules T|apxi⟶aqxi belonging to neuron σi are enabled at step t. The spikes with value pxi are consumed from σi in step t+1; neuron σj will receive the spikes with value qxi from neuron σi at step t+Dsyn+1. Therefore, the spikes are owned by σj after Dsyni,j moments.Besides, the consumption functionpxi and the production function qxi can be selected from the following common activation functions in neural networks:(1)
Tanh function:fx=tanhx=e2x−1/e2x+1.(2)
Sigmoid function:fx=1/1+e−cx.(3)
RuLU function:fx=x,x≥0,0,x<0.(4)
Derivative function of RuLU:fx=1,x≥0,0,x<0.(5)
ELU function:fx=x,x≥0,αex−1,x<0.(6)
fx=2,x>0,0,x≤0.(7)
fx=1,x>0,0,x=0,−1,x<0.(8)
fx=1,x>1,x,−1≤x≤1,−1,x<−1.(9)
LReLU function:fx=x,x>0,αx,x≤0.(10)
PReLU function:fx=maxαx,x.(11)
Softplus function:fx=log1+ex.(12)
Swish function:fx=x⋅sigmoidβx.In the NSNP-DW system, neurons are used in parallel, and the use strategy of rules in each neuron is in a sequential manner; that is, only one rule is allowed to be employed nondeterministically in a calculation step.Assumingm neurons, xit is the number of spikes of the i-th 1≤i≤m neuron, then the configuration (state) of the system Π at step t can be expressed as x1t,…,xmt, and the initial configuration is X0=x10,…,xm0. By executing spike rules, configuration X1 to configuration X2, denoted by X1⇒X2, is defined as a transition of system Π, and the sequence obtained by this transition is defined as a calculation. Each calculation is related to a spike sequence similar to a binary sequence. The sequence is composed of 0 and 1. The output neuron emits a spike to the environment corresponding to 1; otherwise, it corresponds to 0. In this study, the time interval at which the output neuron emits spikes to the environment is used as the calculation result.For an NSNP-DW system with at mostm neurons and at most 2 rules in each neuron, we use NgenSNPm2 to represent all natural number sets generated by the NSNP-DW system and NaccSNPm2 to represent all natural number sets accepted by the NSNP-DW system. When the number of neurons is uncertain, m is often replaced by ∗.


### 3.2. Two Illustrative Examples

Example 1.
A simple example of the NSNP-DW system is given in Figure2, containing three neurons labeled by 1, 2, and 3. The weight between neuron σ1 and neuron σ2 is 2. The delay between neuron σ1 and σ3 is Dsyn1,3=1, denoted by t=1. It is assumed here that px and qx take (5) and (4) of the above function.
At stept, neuron σ1 receives two spikes from the environment, its state is x=2, and rule 2|ax⟶apx/2 is applied. Neuron σ1 consumes two spikes and sends one spike to neurons σ2 and σ3 each (because px/2=1). At step t+1, neuron σ2 receives two spikes due to weight 2. At this moment, neuron σ3 is not fired because of Dsyn1,3=1. At step t+2, neuron σ3 receives two spikes, one from neuron σ1 and one from neuron σ2 (because qx=1). There are two rules in neuron σ3 that both meet the fired conditions. Subject to the maximum threshold strategy, rule 2|ax⟶aqx is used and emits one spike to the environment (for qx=1). This example is complete and the results of each step are presented in Table 1.Figure 2
A simple example.Table 1
Number of spikes at each moment in neurons.
Stepσ1σ2σ3t200t+1020t+2002 (fire)Example 2.
Letpx and qx take (2) and (3) of the above functions as the consumption and generation functions. We define Πk as the system for generating natural numbers; as shown in Figure 3, each neuron initially has a spike.
In the first step, neuronσ3 uses rule 1|apx⟶aqx/2 to emit 1/2 spike to the environment. At the same time, neurons σ1 and σ2 also fire by applying rule 1|apx⟶aqx/2, sending a spike to each other (because of weight 2), and neuron σ1 and neuron σ2 send one (because of weight 2) and 1/2 spike to neuron σ3, respectively. In the next step, neurons σ1 and σ2 continue their initial actions any number of times, and the 3/2 spikes in neuron σ3 are always removed. Once neuron σ2 executes rule 1|apx⟶aλ at step t, neuron σ2 stops emitting spike, and neuron σ1 sends the last spike to neuron σ3. At step t+1, neuron σ3 has a spike, using rule 1|apx⟶aqx/2 to send 1/2 spike to the environment again. In this way, the time interval t+1−1=t of transmitting spike to the environment, that is, the natural number N generated by the system Πk.Figure 3
An example of simulating natural number generation.


## 3.1. Definition

The structure of the proposed NSNP-DW system with degreem≥1 is(1)Π=O,σ1,σ2,…,σm,syn,Dsyn,in,out,where(1)
O=a is the singleton alphabet (a denotes spike);(2)
σ1,σ2,…,σm are neurons, in the form of σi=xi,Ri for 1≤i≤m, where xi∈R+ is the initial value of spikes contained in neuron σi, indicating the initial state of neuron σi, and Ri is the finite set of spiking rules in the following form:(a)
Spiking/firing rules:E|apxi⟶aqxi, where E is the firing condition, pxi is a linear or nonlinear function, and qxi is a nonlinear function, and pxi≥qxi≥0.(b)
Forgetting rules:E|apxi⟶λ, for a linear or nonlinear function pxi.(3)
syn∈1,…,h×1,…,h×W is a synaptic expression with weight, where W=1,…,n, h=m∪environment. For any i,j,n∈syn, 1≤i,j≤h, i≠j, and n∈W.(4)
Dsyn represents the delay on synapse i,j, expressed in the form of a time number.(5)
in and out indicate the input and output neurons of the system, respectively.The NSNP-DW system can be visualized by a directed graphGΠ with nodes and arcs, where nodes are neurons and arcs represent synapse connections. In original SNP systems, the number of spikes is described by an integer. In NSNP-DW systems, besides integer, it can also be described by nonlinear functions. For the rules E|apxi⟶aqxi and E|apxi⟶λ in the NSNP-DW system, the firing condition E has two forms. (1) It is a regular expression like aa3+ to exactly “cover” the contents of the neuron. If E is exactly apxi, then E can be omitted. (2) It is a threshold for enabling the rule and exists in the form of a positive real number. In order to distinguish, we write the rules as T|apxi⟶aqxi and T|apxi⟶λ, T∈R+. Both types of rules can be used in this paper. We assume that xit is the spike value of neuron σi at step t. For firing rules T|apxi⟶aqxi, only when xit≥pxi and xit≥T are satisfied, the rule can be applicable. Intuitively speaking, when the firing rule is met, the neuron is fired, consuming pxi spikes (if the remaining xit−pxi spike can no longer enable the rule, it will disappear in the neuron) and sending out qxi spikes. Forgetting rules T|apxi⟶λ, qxi≡0 mean that spikes with value pxi are consumed but not generated in the neuron to which it belongs. There will inevitably be multiple rules (greater than or equal to 2) in a neuron, assuming two rules, corresponding to the thresholds of T1 and T2, respectively. (i) When T1≠T2 and both rules can be executed, the maximum threshold strategy is applied. For instance, if T1>T2, the rule with T1 takes precedence, and the rule with threshold T2 is not used. For this strategy, the forgetting rule is no exception. (ii) When T1=T2=T, nondeterministic rule selection strategy is enabled. That is, the rules with T1 and T2 need to be discussed separately.In addition, for the NSNP-DW system, weights and delays are reflected in synapses. For anyi,j,n∈syn, n is the weight on the synapse. If the spikes with value qxi are emitted by neuron σi, neuron σj will receive n×qxi spikes. The delay between synapses i,j is represented by Dsyn, Dsyn is in the form of a time number. If there is a delay between neurons σi and σj, the spiking rules T|apxi⟶aqxi belonging to neuron σi are enabled at step t. The spikes with value pxi are consumed from σi in step t+1; neuron σj will receive the spikes with value qxi from neuron σi at step t+Dsyn+1. Therefore, the spikes are owned by σj after Dsyni,j moments.Besides, the consumption functionpxi and the production function qxi can be selected from the following common activation functions in neural networks:(1)
Tanh function:fx=tanhx=e2x−1/e2x+1.(2)
Sigmoid function:fx=1/1+e−cx.(3)
RuLU function:fx=x,x≥0,0,x<0.(4)
Derivative function of RuLU:fx=1,x≥0,0,x<0.(5)
ELU function:fx=x,x≥0,αex−1,x<0.(6)
fx=2,x>0,0,x≤0.(7)
fx=1,x>0,0,x=0,−1,x<0.(8)
fx=1,x>1,x,−1≤x≤1,−1,x<−1.(9)
LReLU function:fx=x,x>0,αx,x≤0.(10)
PReLU function:fx=maxαx,x.(11)
Softplus function:fx=log1+ex.(12)
Swish function:fx=x⋅sigmoidβx.In the NSNP-DW system, neurons are used in parallel, and the use strategy of rules in each neuron is in a sequential manner; that is, only one rule is allowed to be employed nondeterministically in a calculation step.Assumingm neurons, xit is the number of spikes of the i-th 1≤i≤m neuron, then the configuration (state) of the system Π at step t can be expressed as x1t,…,xmt, and the initial configuration is X0=x10,…,xm0. By executing spike rules, configuration X1 to configuration X2, denoted by X1⇒X2, is defined as a transition of system Π, and the sequence obtained by this transition is defined as a calculation. Each calculation is related to a spike sequence similar to a binary sequence. The sequence is composed of 0 and 1. The output neuron emits a spike to the environment corresponding to 1; otherwise, it corresponds to 0. In this study, the time interval at which the output neuron emits spikes to the environment is used as the calculation result.For an NSNP-DW system with at mostm neurons and at most 2 rules in each neuron, we use NgenSNPm2 to represent all natural number sets generated by the NSNP-DW system and NaccSNPm2 to represent all natural number sets accepted by the NSNP-DW system. When the number of neurons is uncertain, m is often replaced by ∗.


## 3.2. Two Illustrative Examples

Example 1.
A simple example of the NSNP-DW system is given in Figure2, containing three neurons labeled by 1, 2, and 3. The weight between neuron σ1 and neuron σ2 is 2. The delay between neuron σ1 and σ3 is Dsyn1,3=1, denoted by t=1. It is assumed here that px and qx take (5) and (4) of the above function.
At stept, neuron σ1 receives two spikes from the environment, its state is x=2, and rule 2|ax⟶apx/2 is applied. Neuron σ1 consumes two spikes and sends one spike to neurons σ2 and σ3 each (because px/2=1). At step t+1, neuron σ2 receives two spikes due to weight 2. At this moment, neuron σ3 is not fired because of Dsyn1,3=1. At step t+2, neuron σ3 receives two spikes, one from neuron σ1 and one from neuron σ2 (because qx=1). There are two rules in neuron σ3 that both meet the fired conditions. Subject to the maximum threshold strategy, rule 2|ax⟶aqx is used and emits one spike to the environment (for qx=1). This example is complete and the results of each step are presented in Table 1.Figure 2
A simple example.Table 1
Number of spikes at each moment in neurons.
Stepσ1σ2σ3t200t+1020t+2002 (fire)Example 2.
Letpx and qx take (2) and (3) of the above functions as the consumption and generation functions. We define Πk as the system for generating natural numbers; as shown in Figure 3, each neuron initially has a spike.
In the first step, neuronσ3 uses rule 1|apx⟶aqx/2 to emit 1/2 spike to the environment. At the same time, neurons σ1 and σ2 also fire by applying rule 1|apx⟶aqx/2, sending a spike to each other (because of weight 2), and neuron σ1 and neuron σ2 send one (because of weight 2) and 1/2 spike to neuron σ3, respectively. In the next step, neurons σ1 and σ2 continue their initial actions any number of times, and the 3/2 spikes in neuron σ3 are always removed. Once neuron σ2 executes rule 1|apx⟶aλ at step t, neuron σ2 stops emitting spike, and neuron σ1 sends the last spike to neuron σ3. At step t+1, neuron σ3 has a spike, using rule 1|apx⟶aqx/2 to send 1/2 spike to the environment again. In this way, the time interval t+1−1=t of transmitting spike to the environment, that is, the natural number N generated by the system Πk.Figure 3
An example of simulating natural number generation.


## 4. Computational Power

In the nonlinear spike rule of the NSNP-DW system, we choose two of the aforementioned functions (representing consumption or generation function) to verify the Turing universality of the system and its computing power. The following functionspx and qx are considered:(2)px=x,x≥0,αex−1,x<0,qx=1,x≥0,0,x<0.Thus, the state of neuronσi can be recorded by a nonlinear equation:(3)xit+1=xit−pxit+yit,if neuronσifires,xit+yit,otherwise,where xit and xit+1 are the states of neuron at step t and t+1, respectively, pxit represents the consumption value, and yit is the reception value.In this part, we are committed to showing Turing universal NSNP-DW system as number generating device and accepting device. Given that the register machineM can generate and accept any NRE, the NSNP-DW system is proved to be universal through simulating the number generated by M. In order to facilitate understanding, we assume that number n in register r represents 2n spikes in neuron σr. Neurons σli, σlj, and σlk receive two spikes, and the corresponding instructions are activated.


### 4.1. NSNP-DW Systems as Number Generating Device

Theorem 1.
NgenSNP∗2=NRE.Proof.
NgenSNP∗2⊆NRE is beyond doubt based on the Turing-Church thesis; only NgenSNP∗2⊇NRE needs to be proved. In the number generating mode, M=m,H,l0,lh,I is the needed register machine, and the number generating device includes ADD, SUB, and FIN modules. M generates the number n in the following way: initially, the number of all registers is empty, and the simulation starts from instruction l0, continues the process with the required label instructions, and stops at instruction lh. According to the instructions, the number n stored in the first register is calculated by M. In ADD and SUB modules, neuron σli receives two spikes and runs according to instruction li:OPr,lj,lk (OP is ADD or SUB operation). Neuron σlj or σlk receives two spikes indefinitely, and corresponding instruction lj or lk is activated. In the FIN module, neuron σout sends spikes outside twice at intervals.
ADD module (shown in Figure4)—simulating an ADD instruction li:ADDr,lj,lk.
Neuronσli will receive two spikes from environment. After running the ADD mode, spikes will be sent to neuron σlj or σlk indefinitely to simulate instruction lj or lk. When two spikes are in neuron σr, the corresponding register r is increased by 1.
In detail, neuronσli fires at step t, and rule 2|ax⟶apx/2 is executed, sending one spike to neurons σc1, σc2, σc3, and σr, respectively. The next moment, neuron σc1 receives one spike. Since the same thresholds of rule 1|ax⟶apx and rule 1|ax⟶λ, the two rules are executed indefinitely:(i)
At stept+1, if rule 1|ax⟶apx is used, one spike will be sent to neurons σc2 and σc3, respectively. Next step, both neurons σc2 and σc3 contain two spikes, one from neuron σli and one from neuron σc1. At step t+3, neuron σc3 fires by using rule 2|ax⟶λ, so that two spikes are removed. Rule 2|ax⟶apx/2 in neuron σc2 is applied simultaneously, consuming two spikes and emitting one to neurons σc4 and σlj. At the next step, neuron σc4 becomes active by executing rule 1|ax⟶apx, emitting one spike to neuron σr and σlj each. In this way, the second spike is received by σr, which will aggrandize the value of register r by 1. Neuron σlj receives a total of two spikes successively, and then instruction lj starts to be simulated.(ii)
At stept+1, neuron σc1 fires by using rule 1|ax⟶λ, which causes a spike to be removed. At step t+2, neurons σc2 and σc3 each receive one spike, and soon this no longer exists in neuron σc2 because of 1|ax⟶λ. The one received in neuron σc3 is sent to neurons σc4 and σlk through rule 1|ax⟶apx. Then, the next moment, neuron σc4 transmits one, which is received by σr and σlk. So neuron σr and σlk have received two spikes at step t+4, respectively, indicating that the register r is increased by 1, and lk is activated.
Therefore, simulating instructionli:ADDr,lj,lk is displayed correctly. Considering two different rules, Table 2 shows the number of spikes in all neurons at each moment.
SUB Module (shown in Figure5)—simulating a SUB instruction li:SUBr,lj,lk.
Two spikes are received by neuronσli. If register r is not empty, then two spikes are sent to neuron σlj, and the corresponding instruction lj is executed. If the value in the register r is zero, then two spikes are sent to neuron σlk, and the instruction with label lk is executed. The detailed simulation process is as follows.
Neuronσli fires at step t, and rule 2|ax⟶apx/2 is applied to emit one spike. At step t+1, neuron σr, σlj, and σlk each receive one spike from neuron σli. Next, there will be two cases according to the value of spike in neuron σr:(i)
At stept+1, if 2n+1n≥1 spikes are contained by σr (the value of the corresponding register r is n), then rule 3|ax⟶aqx is applicable. Next step, the neuron σc1 receives three spikes and fires, one from neuron σli and two from neuron σr. Based on the maximum threshold strategy, rule 2|ax⟶aλ is used to consume these three spikes. At the same step, neuron σlj receives the second spike, and then instruction lj is simulated by system Π.(ii)
At stept+1, if neuron σr only contains one spike (the value of the corresponding register r is 0), then the spike is removed by rule 1|ax⟶aλ. At step t+2, a spike from neuron σli is in neuron σc1. The firing of neuron σc1 by rule 1|ax⟶apx causes neuron σlk to add a spike. At the next step, neuron σlk receives a total of two spikes, and then instruction lk is simulated by system Π, but not lj.
So SUB module simulates instructionli:SUBr,lj,lk correctly. The simulated numerical changes are presented in Table 3.
(3) FIN module (shown in Figure 6) - outputting the result of computation.
At stept, neuron σlh fires by running rule 2|ax⟶apx/2, transmitting a spike to σ1. Originally, neuron σ1 contains 2n−1n≥2 spikes, and after receiving one spike, the rule 3|a2⟶a can be used first because of the maximum threshold strategy. Then neuron σc1 and neuron σout each have a spike from neuron σ1. The first spike is sent by output neuron σout to the environment through 1|ax⟶apx at step t+3. Besides, neuron σout receives one spike from neuron σ1 and neuron σc1, respectively, causing them to be forgotten by 2|ax⟶λ. Since two spikes are consumed in neuron σ1, a spike is continuously given σc1 and σout. As a result, both spikes in neuron σout from t+2 to t+n are forgotten by 2|ax⟶λ. Until step t+n+1, only one spike is kept in σ1, and then the generated one is emitted by 1|ax⟶apx. At step t+n+2, the neuron σout still accepts two spikes but is forgotten instantly. At step t+n+3, the last spike is received by neuron σout from σc1 and sent to the environment through rule 1|ax⟶apx. The time interval between spikes emitted to the environment is the number calculated by the system Π. In short, the numerical result computed through the system Π is t+n+3−t+3=n. Take the generated number n=4 as an example, and the simulated numerical changes of output module are reflected in Table 4.
Through the above discussion, we can see that the systemΠ accurately simulates the register machine M, so the theorem is reasonable.Figure 4
ADD module (simulatingli:ADDr,lj,lk).Table 2
The spike result under ADD module.
Stepσliσc1σc2σc3σc4σljσlkσrt20000002nt+101000002n + 1If1|ax⟶apx is usedIf1|ax⟶λ is usedσliσc1σc2σc3σc4σljσlkσrσliσc1σc2σc3σc4σljσlkσrt+200220002n + 100220002n + 1t+300001102n + 200001012n + 1t+400000212n + 100000122n + 2t+500000202n + 100000022n + 2Figure 5
SUB module (simulatingli:SUBr,lj,lk).Table 3
The results of spike in SUB module.
σr is not emptyσr is emptyStepσliσc1σljσlkσrσliσc1σljσlkσrt20002n + 120000t+100112n + 200111t+203212n − 101110t+300212n − 100120t+400202n − 100020Figure 6
FIN Module (output calculation result).Table 4
The results of spike in FIN module.
Stepσlhσc1σ1σoutEnvironmentt20600t+100700t+201510t+301321t+401120t+500020t+600010t+700001


### 4.2. NSNP-DW Systems as Number Accepting Device

Theorem 2.
NaccSNP∗2=NRE.Proof.
In the number accepting mode, the number in the first register isn (others are empty), and then the calculation starts from l0; when the calculation stops, the number n is accepted. Similar to Theorem 1, we only need to verify NaccSNP∗2⊇NRE. The constructed NSNP-DW system as number accepting device includes an INPUT module, a deterministic ADD module, and a SUB module. Figure 7 shows the INPUT module.
Suppose that the first spike is received by neuronσin at step t; the firing of σin gives a spike to neurons σc1, σc2, and σc3through rule 1|ax⟶apx. Then, neuron σc1 fires and outputs one spike to neuron σl0, while neurons σc2 and σc3 fire by using rule 1|ax⟶apx. At step t+2, neurons σc2 and σc3 send one spike to each other, and especially neuron σ1 receives two spikes from neuron σc2, until neuron σin receives the second spike. Thus, neuron σ1 receives 2n spikes from step t+2 to t+n+1.
At stept+n+1, neuron σin obtains a spike again and reacts using rule 1|ax⟶apx, sending one spike to neurons σc1, σc2, and σc3 again. At step t+n+2, σc2 and σc3 each possess two spikes, and rule 2|ax⟶λ is applicable so that spikes are eliminated. Simultaneously, neuron σc1 fires for the second step, executing rule 1|ax⟶aqx to give neuron σl0 a spike, whereupon instruction l0 is activated.
Figure8 displays the simulating of deterministic ADD instruction li:ADDr,lj. Neuron σli accepts two spikes, consuming them and sending two spikes to neuron σlj through rule 2|ax⟶apx; instruction lj is simulated. Neuron σr contains two spikes, indicating that the register r is increased by 1. The SUB module of accepting mode is the same as in Figure 4.
In short,NaccSNP∗2=NRE holds.Figure 7
INPUT module.Figure 8
ADD module (simulatingli:ADDr,lj).


## 4.1. NSNP-DW Systems as Number Generating Device

Theorem 1.
NgenSNP∗2=NRE.Proof.
NgenSNP∗2⊆NRE is beyond doubt based on the Turing-Church thesis; only NgenSNP∗2⊇NRE needs to be proved. In the number generating mode, M=m,H,l0,lh,I is the needed register machine, and the number generating device includes ADD, SUB, and FIN modules. M generates the number n in the following way: initially, the number of all registers is empty, and the simulation starts from instruction l0, continues the process with the required label instructions, and stops at instruction lh. According to the instructions, the number n stored in the first register is calculated by M. In ADD and SUB modules, neuron σli receives two spikes and runs according to instruction li:OPr,lj,lk (OP is ADD or SUB operation). Neuron σlj or σlk receives two spikes indefinitely, and corresponding instruction lj or lk is activated. In the FIN module, neuron σout sends spikes outside twice at intervals.
ADD module (shown in Figure4)—simulating an ADD instruction li:ADDr,lj,lk.
Neuronσli will receive two spikes from environment. After running the ADD mode, spikes will be sent to neuron σlj or σlk indefinitely to simulate instruction lj or lk. When two spikes are in neuron σr, the corresponding register r is increased by 1.
In detail, neuronσli fires at step t, and rule 2|ax⟶apx/2 is executed, sending one spike to neurons σc1, σc2, σc3, and σr, respectively. The next moment, neuron σc1 receives one spike. Since the same thresholds of rule 1|ax⟶apx and rule 1|ax⟶λ, the two rules are executed indefinitely:(i)
At stept+1, if rule 1|ax⟶apx is used, one spike will be sent to neurons σc2 and σc3, respectively. Next step, both neurons σc2 and σc3 contain two spikes, one from neuron σli and one from neuron σc1. At step t+3, neuron σc3 fires by using rule 2|ax⟶λ, so that two spikes are removed. Rule 2|ax⟶apx/2 in neuron σc2 is applied simultaneously, consuming two spikes and emitting one to neurons σc4 and σlj. At the next step, neuron σc4 becomes active by executing rule 1|ax⟶apx, emitting one spike to neuron σr and σlj each. In this way, the second spike is received by σr, which will aggrandize the value of register r by 1. Neuron σlj receives a total of two spikes successively, and then instruction lj starts to be simulated.(ii)
At stept+1, neuron σc1 fires by using rule 1|ax⟶λ, which causes a spike to be removed. At step t+2, neurons σc2 and σc3 each receive one spike, and soon this no longer exists in neuron σc2 because of 1|ax⟶λ. The one received in neuron σc3 is sent to neurons σc4 and σlk through rule 1|ax⟶apx. Then, the next moment, neuron σc4 transmits one, which is received by σr and σlk. So neuron σr and σlk have received two spikes at step t+4, respectively, indicating that the register r is increased by 1, and lk is activated.
Therefore, simulating instructionli:ADDr,lj,lk is displayed correctly. Considering two different rules, Table 2 shows the number of spikes in all neurons at each moment.
SUB Module (shown in Figure5)—simulating a SUB instruction li:SUBr,lj,lk.
Two spikes are received by neuronσli. If register r is not empty, then two spikes are sent to neuron σlj, and the corresponding instruction lj is executed. If the value in the register r is zero, then two spikes are sent to neuron σlk, and the instruction with label lk is executed. The detailed simulation process is as follows.
Neuronσli fires at step t, and rule 2|ax⟶apx/2 is applied to emit one spike. At step t+1, neuron σr, σlj, and σlk each receive one spike from neuron σli. Next, there will be two cases according to the value of spike in neuron σr:(i)
At stept+1, if 2n+1n≥1 spikes are contained by σr (the value of the corresponding register r is n), then rule 3|ax⟶aqx is applicable. Next step, the neuron σc1 receives three spikes and fires, one from neuron σli and two from neuron σr. Based on the maximum threshold strategy, rule 2|ax⟶aλ is used to consume these three spikes. At the same step, neuron σlj receives the second spike, and then instruction lj is simulated by system Π.(ii)
At stept+1, if neuron σr only contains one spike (the value of the corresponding register r is 0), then the spike is removed by rule 1|ax⟶aλ. At step t+2, a spike from neuron σli is in neuron σc1. The firing of neuron σc1 by rule 1|ax⟶apx causes neuron σlk to add a spike. At the next step, neuron σlk receives a total of two spikes, and then instruction lk is simulated by system Π, but not lj.
So SUB module simulates instructionli:SUBr,lj,lk correctly. The simulated numerical changes are presented in Table 3.
(3) FIN module (shown in Figure 6) - outputting the result of computation.
At stept, neuron σlh fires by running rule 2|ax⟶apx/2, transmitting a spike to σ1. Originally, neuron σ1 contains 2n−1n≥2 spikes, and after receiving one spike, the rule 3|a2⟶a can be used first because of the maximum threshold strategy. Then neuron σc1 and neuron σout each have a spike from neuron σ1. The first spike is sent by output neuron σout to the environment through 1|ax⟶apx at step t+3. Besides, neuron σout receives one spike from neuron σ1 and neuron σc1, respectively, causing them to be forgotten by 2|ax⟶λ. Since two spikes are consumed in neuron σ1, a spike is continuously given σc1 and σout. As a result, both spikes in neuron σout from t+2 to t+n are forgotten by 2|ax⟶λ. Until step t+n+1, only one spike is kept in σ1, and then the generated one is emitted by 1|ax⟶apx. At step t+n+2, the neuron σout still accepts two spikes but is forgotten instantly. At step t+n+3, the last spike is received by neuron σout from σc1 and sent to the environment through rule 1|ax⟶apx. The time interval between spikes emitted to the environment is the number calculated by the system Π. In short, the numerical result computed through the system Π is t+n+3−t+3=n. Take the generated number n=4 as an example, and the simulated numerical changes of output module are reflected in Table 4.
Through the above discussion, we can see that the systemΠ accurately simulates the register machine M, so the theorem is reasonable.Figure 4
ADD module (simulatingli:ADDr,lj,lk).Table 2
The spike result under ADD module.
Stepσliσc1σc2σc3σc4σljσlkσrt20000002nt+101000002n + 1If1|ax⟶apx is usedIf1|ax⟶λ is usedσliσc1σc2σc3σc4σljσlkσrσliσc1σc2σc3σc4σljσlkσrt+200220002n + 100220002n + 1t+300001102n + 200001012n + 1t+400000212n + 100000122n + 2t+500000202n + 100000022n + 2Figure 5
SUB module (simulatingli:SUBr,lj,lk).Table 3
The results of spike in SUB module.
σr is not emptyσr is emptyStepσliσc1σljσlkσrσliσc1σljσlkσrt20002n + 120000t+100112n + 200111t+203212n − 101110t+300212n − 100120t+400202n − 100020Figure 6
FIN Module (output calculation result).Table 4
The results of spike in FIN module.
Stepσlhσc1σ1σoutEnvironmentt20600t+100700t+201510t+301321t+401120t+500020t+600010t+700001


## 4.2. NSNP-DW Systems as Number Accepting Device

Theorem 2.
NaccSNP∗2=NRE.Proof.
In the number accepting mode, the number in the first register isn (others are empty), and then the calculation starts from l0; when the calculation stops, the number n is accepted. Similar to Theorem 1, we only need to verify NaccSNP∗2⊇NRE. The constructed NSNP-DW system as number accepting device includes an INPUT module, a deterministic ADD module, and a SUB module. Figure 7 shows the INPUT module.
Suppose that the first spike is received by neuronσin at step t; the firing of σin gives a spike to neurons σc1, σc2, and σc3through rule 1|ax⟶apx. Then, neuron σc1 fires and outputs one spike to neuron σl0, while neurons σc2 and σc3 fire by using rule 1|ax⟶apx. At step t+2, neurons σc2 and σc3 send one spike to each other, and especially neuron σ1 receives two spikes from neuron σc2, until neuron σin receives the second spike. Thus, neuron σ1 receives 2n spikes from step t+2 to t+n+1.
At stept+n+1, neuron σin obtains a spike again and reacts using rule 1|ax⟶apx, sending one spike to neurons σc1, σc2, and σc3 again. At step t+n+2, σc2 and σc3 each possess two spikes, and rule 2|ax⟶λ is applicable so that spikes are eliminated. Simultaneously, neuron σc1 fires for the second step, executing rule 1|ax⟶aqx to give neuron σl0 a spike, whereupon instruction l0 is activated.
Figure8 displays the simulating of deterministic ADD instruction li:ADDr,lj. Neuron σli accepts two spikes, consuming them and sending two spikes to neuron σlj through rule 2|ax⟶apx; instruction lj is simulated. Neuron σr contains two spikes, indicating that the register r is increased by 1. The SUB module of accepting mode is the same as in Figure 4.
In short,NaccSNP∗2=NRE holds.Figure 7
INPUT module.Figure 8
ADD module (simulatingli:ADDr,lj).


## 5. Small Universal Computing Devices

### 5.1. Small Universal NSNP-DW Systems as Function Computing Device

Theorem 3.
There is a small universal NSNP-DW system possessing 47 neurons for computing functions.Proof.
For simulation of the register machineMu′, the designed NSNP-DW system includes INPUT, ADD, SUB, and OUTPUT modules. The general design is visualized in Figure 9. Still the same as originally assumed, the value n in register r corresponds to 2n spikes in neuron σr. Assume that all neurons are empty in the initial configuration. Figure 10 is the designed INPUT module. σin is the input neuron, reading a spike train 10gx−10y−11. Finally, 2gx and 2y spikes are contained by neurons σ1 and σ2, respectively.
As before, a time step or step represents the execution time of one rule. We still use this notion to mark the moment the rule is executed. At stept1, if the first spike from the environment is received by neuron σin, rule 1|ax⟶apx is applicable, sending one spike to neurons σc1, σc2, σc3, σc4, σc5, and σc6, respectively. At step t1+1, neurons σc3, σc4, σc5, and σc6 will not receive spikes due to one moment of delay; neuron σc1 and neuron σc2 each receive one spike but do not fire. At the next step, the neurons σc3, σc4, σc5, and σc6 receive one spike from neuron σin, but neurons σc5 and σc6 do not fire. Neurons σc3 and σc4 fire by employing rule 1|ax⟶apx, sending one spike to each other and both sending one spike to σ1, so neuron σ1 owns two spikes at t1+3. In this way, neuron σ1 continues to receive two spikes, until step t1+gx+2, σ1 has a total of 2gx spikes.
At stept2, here actually t2=t1+gx+2, and neuron σin fires a second time and applies rule 1|ax⟶apx to send one spike to each of neurons σc1, σc2, σc3, σc4, σc5, and σc6. Neurons σc1 and σc2 each have two spikes at step t2+1. For one delay, neurons σc3, σc4, σc5, and σc6receive one spike from neuron σin at step t2+2. At this step, neurons σc4 and σc5 each have two spikes, and executing rule 2|ax⟶λ causes two spikes to be removed. On the contrary, neurons σc5 and σc6 each have two spikes and stay active. Two spikes are sent to each other by neurons σc5 and σc6, and two are given to σ2 by neuron σc5, so that neuron σ2 contains two spikes at step t2+3. Neuron σ2 accepts two spikes from neuron σc5 continuously until step t2+y+3. At step t2+y+3, neuron σ2 retains 2y spikes in total.
At stept3, here actually t3=t2+y+3, neuron σin fires a third time, one spike is consumed, and one is sent to neurons σc1, σc2, σc3, σc4, σc5, and σc6, respectively, by rule 1|ax⟶apx. At step t3+1, neuron σc1 with three spikes fires, and the rule 3|ax⟶a2qx is used to consume three spikes and send two spikes to neuron σl0. When the neuron σl0 receives two spikes, the introduction l0 is simulated. Neuron σc2 also fires at step t3+1 and sends one spike to neurons σc3 and σc4 through rule 3|ax⟶aqx. At step t3+2, neuron σc3 receives spikes from neuron σin and neuron σc2; forgetting rule 2|ax⟶λ is applied to remove two spikes. The same is true for neuron σc4. At the same step, neurons σc5 and σc6 each receive the third spike from neuron σin, so they have three spikes and remain inactive. The forgetting rule 3|ax⟶λ is used to remove the three spikes.
In order to reflect the rationality of INPUT module, assuminggx=4 and y=3, the change in the number of spikes at each step can be clearly seen in Table 5.
In addition, the ADD and SUB modules are the same as in Figures8 and 5. The design and simulation process of OUTPUT module is the same as Figure 6, except that the register 1 is replaced by register 8 (shown in Figure 11). This is because when a small universal NSNP-DW system is used as function computing device, after each instruction simulation, the final register 8 contains n numbers (the neuron σ8 contains 2n spikes). The result n is output through the OUTPUT module.
From the discussion above, the NSNP-DW system as a function computing device can accurately simulate the register machineMu′ by using 57 neurons: (i) 7 neurons in the INPUT module, (ii) 2 neurons in the OUTPUT module, (iii) 1 neuron in each SUB instruction and 14 in total, (iv) 9 neurons in 9 registers, and (v) 25 neurons for 25 instructions.
The register machineMu′ is simulated by the NSNP-DW system, and each instruction li on Mu′ is regarded as a neuron. However, some instructions are continuous. By exploring the relationship between the instructions of Mu′, correspondingly constituted modules can be combined, instructions are omitted, and the use of neurons is reduced by the way. A detailed introduction to the initial register machine and its instructions can be found in [40]. For the NSNP-DW system, module combination is mainly divided into three categories: module ADD-ADD, module ADD-SUB, and module SUB-ADD (includes modules SUB-ADD-1 and SUB-ADD-2). The working process of module ADD-SUB and module SUB-ADD is closely related to that of module SUB. The working principle is expressed by the structure diagram. Readers interested in a description of the principle can refer to [11, 26, 41].Figure 9
Framework of the universal NSNP-DW system.Figure 10
INPUT module.Table 5
The results of spike in INPUT module whengx=4 and y=3.
Stepσinσc1σc2σc3σc4σc5σc6σ1σ2σl0t1000000000t+10110000000t+20111111000t+30111111200t+41111111400t+50221111600t+60222222800t+71220022820t+80330022840t+90002233860t+100000000862Figure 11
OUTPUT module.


#### 5.1.1. Module ADD-ADD

(4)l17:ADD2,l21,l21:ADD3,l18.These are two deterministic ADD instructions. The simulation of each instruction is the same as in Figure8. The module design is shown in Figure 12 before the instruction l21 is omitted.Figure 12
Module ADD-ADD before omittingl21: the sequence of two consecutive ADD instructions l17:ADD2,l21 and l21:ADD3,l18Obviously, this is a sequence of two consecutive ADD instructions connected byl21; instruction l21 can be omitted through the following module ADD-ADD (shown in Figure 13).Figure 13
Module ADD-ADD after omittingl21: the sequence of two consecutive ADD instructions l17:ADD2,l21 and l21:ADD3,l18.


#### 5.1.2. Module ADD-SUB

(5)l5:ADD5,l6,l6:SUB7,l7,l8,l9:ADD6,l10,l10:SUB4,l0,l11.These are two consecutive pairs of ADD-SUB instructions connected byl6 and l10, respectively; we can combine instructions l5:ADD5,l6 and l6:SUB7,l7,l8 into one instruction l5:ADD5,SUB7,l7,l8, which saves instruction l6. Instructions l9:ADD6,l10 and l10:SUB4,l0,l11 are combined into one instruction l9:ADD6,SUB4,l0,l11, saving instruction l10.Taking the omission ofl6 as an example, neuron σl5 sends spikes to σ5 and σl6, and then neuron σl6 performs the simulation of instruction l6. Here, neuron σl6 can be omitted, and neuron σl5 replaces σl6 to directly simulate the SUB instruction. It can be seen from Figure 14 that this is possible.Figure 14
A module for consecutive ADD-SUB instructionl5:ADD5, SUB7,l7,l8.


#### 5.1.3. Module SUB-ADD

For introductionli:SUBr,lj,lk, when the value r≠0, it is subtracted by 1, and the instruction lj is executed; otherwise, the labeled lk is activated. Therefore, considering that there are two forms of consecutive SUB-ADD instructions, module SUB-ADD is divided into modules SUB-ADD-1 and SUB-ADD-2.Module SUB-ADD-1:(6)l15:SUB3,l18,l20,l20:ADD0,l0.This is the case whenlk is activated and lj is reserved. We can combine instructions l15:SUB3,l18,l20 and l20:ADD0,l0 into one instruction l15:SUB3,l18,ADD0,l0, causing instruction l20 to be omitted (see Figure 15).Figure 15
Module SUB-ADD-1: the sequence of two consecutive instructionsl15:SUB3,l18,l20 and l20:ADD0,l0.Module SUB-ADD-2:(7)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,l22:SUB0,l23,l24,l23:ADD8,l22.This is the case whenlj is activated and lk is reserved. There are six pairs of instructions that can be combined in pairs. It is found through observation that the following ADD instruction happens to be the first execution position of the previous SUB instruction. Then each pair of SUB-ADD instruction combinations can be updated to li:SUBr1,lj,lk andlj:ADDr2,lg. When the register r1≠r2, they can share one neuron σlj. In this way, six neurons in total of σ1, σ5, σ7, σ9, σ19, and σ23 can be saved. The visualization can be illustrated in Figure 16.Figure 16
Module SUB-ADD-2: the sequence of the SUB and ADD instructionsli:SUBr1,lj,lk and lj:ADDr2,lg.Through the above instruction combination (called “code optimization” in [41]), 10 neurons σ21, σ6, σ10, σ20, σ1, σ5, σ7, σ9, σ16, and σ23 can be omitted. In the end, 47 neurons are enough to complete a small universal NSNP-DW system for computing functions:(i)
Nine neurons for 9 registers.(ii)
15 neurons in remaining 15 instruction labels (ten labels are saved).(iii)
Seven neurons in the module INPUT.(iv)
14 neurons for a total of 14 SUB instructions.(v)
Two neurons in the module OUTPUT.


### 5.2. Small Universal NSNP-DW Systems as Number Generator

In the simulation of number generator, the INPUT module can be combined with the OUTPUT module, found in Figure17. In the constructed INPUT-OUTPUT module, instruction lh is removed, and register 8 is no longer needed. The spike train that the input neuron gets from the environment is 10gx−11, neuron σ1 is loaded with 2gx spikes, and neuron σ2 receives 2n spikes nondeterministically. Neuron σout fires twice successively, and the time interval n is the numerical result generated.Figure 17
INPUT-OUTPUT module.The simulation of NSNP-DW systems as number generator shares 43 neurons, and the specific details will not be repeated:(i)
Eight neurons for 8 registers (no register 8).(ii)
14 neurons in the remaining 14 instruction labels (lh and ten labels are saved).(iii)
Seven neurons in the module INPUT-OUTPUT.(iv)
14 neurons for a total of 14 SUB instructions.Theorem 4.
There is a small universal NSNP-DW system possessing 43 neurons for number generator.The specific simulation will not be introduced in detail. We use an example to analyze the feasibility of number generator simulation; assuminggx=2 and n=2, the results of each step are reflected in Table 6.Table 6
The results of spike in INPUT-OUTPUT module.
Stepσinσc1σc2σc3σc4σc5σ1σ2σoutσl0t1000000000t+10111000000t+2111022201 (fire)0t+31221224201t+4000044441 (fire)1t+50000004402


### 5.3. Discussion

Theorem3 gives the Turing universal NSNP-DW system with fewer neurons as a function computing device. In order to more intuitively verify the computing power of the NSNP-DW system, Table 7 compares the number of computing units for the variant and its related systems. According to Table 7, we observe that NSNP systems, SNP systems, SNP-DS systems, and recurrent neural networks use 117, 67, 56, and 886 neurons, respectively, to accomplish Turing universality for computing function, and NSNP-DW systems only require 47 neurons. Besides, according to Table 8, we have observed that 121 neurons are reduced for simulating number generator. In short, NSNP-DW systems are better than these systems in the use of neurons, and the computational power of the NSNP system has been effectively improved.Table 7
Comparison of the least neurons of several calculation models.
Computing modelsNumber of neuronsNSNP-DW systems47NSNP systems [39]117SNP systems [11]67SNP-DS systems [31]56Recurrent neural networks [42]886Table 8
Comparison of the least neurons as number generator.
Computing modelsNumber of neuronsNSNP-DW systems43NSNP systems [39]164


## 5.1. Small Universal NSNP-DW Systems as Function Computing Device

Theorem 3.
There is a small universal NSNP-DW system possessing 47 neurons for computing functions.Proof.
For simulation of the register machineMu′, the designed NSNP-DW system includes INPUT, ADD, SUB, and OUTPUT modules. The general design is visualized in Figure 9. Still the same as originally assumed, the value n in register r corresponds to 2n spikes in neuron σr. Assume that all neurons are empty in the initial configuration. Figure 10 is the designed INPUT module. σin is the input neuron, reading a spike train 10gx−10y−11. Finally, 2gx and 2y spikes are contained by neurons σ1 and σ2, respectively.
As before, a time step or step represents the execution time of one rule. We still use this notion to mark the moment the rule is executed. At stept1, if the first spike from the environment is received by neuron σin, rule 1|ax⟶apx is applicable, sending one spike to neurons σc1, σc2, σc3, σc4, σc5, and σc6, respectively. At step t1+1, neurons σc3, σc4, σc5, and σc6 will not receive spikes due to one moment of delay; neuron σc1 and neuron σc2 each receive one spike but do not fire. At the next step, the neurons σc3, σc4, σc5, and σc6 receive one spike from neuron σin, but neurons σc5 and σc6 do not fire. Neurons σc3 and σc4 fire by employing rule 1|ax⟶apx, sending one spike to each other and both sending one spike to σ1, so neuron σ1 owns two spikes at t1+3. In this way, neuron σ1 continues to receive two spikes, until step t1+gx+2, σ1 has a total of 2gx spikes.
At stept2, here actually t2=t1+gx+2, and neuron σin fires a second time and applies rule 1|ax⟶apx to send one spike to each of neurons σc1, σc2, σc3, σc4, σc5, and σc6. Neurons σc1 and σc2 each have two spikes at step t2+1. For one delay, neurons σc3, σc4, σc5, and σc6receive one spike from neuron σin at step t2+2. At this step, neurons σc4 and σc5 each have two spikes, and executing rule 2|ax⟶λ causes two spikes to be removed. On the contrary, neurons σc5 and σc6 each have two spikes and stay active. Two spikes are sent to each other by neurons σc5 and σc6, and two are given to σ2 by neuron σc5, so that neuron σ2 contains two spikes at step t2+3. Neuron σ2 accepts two spikes from neuron σc5 continuously until step t2+y+3. At step t2+y+3, neuron σ2 retains 2y spikes in total.
At stept3, here actually t3=t2+y+3, neuron σin fires a third time, one spike is consumed, and one is sent to neurons σc1, σc2, σc3, σc4, σc5, and σc6, respectively, by rule 1|ax⟶apx. At step t3+1, neuron σc1 with three spikes fires, and the rule 3|ax⟶a2qx is used to consume three spikes and send two spikes to neuron σl0. When the neuron σl0 receives two spikes, the introduction l0 is simulated. Neuron σc2 also fires at step t3+1 and sends one spike to neurons σc3 and σc4 through rule 3|ax⟶aqx. At step t3+2, neuron σc3 receives spikes from neuron σin and neuron σc2; forgetting rule 2|ax⟶λ is applied to remove two spikes. The same is true for neuron σc4. At the same step, neurons σc5 and σc6 each receive the third spike from neuron σin, so they have three spikes and remain inactive. The forgetting rule 3|ax⟶λ is used to remove the three spikes.
In order to reflect the rationality of INPUT module, assuminggx=4 and y=3, the change in the number of spikes at each step can be clearly seen in Table 5.
In addition, the ADD and SUB modules are the same as in Figures8 and 5. The design and simulation process of OUTPUT module is the same as Figure 6, except that the register 1 is replaced by register 8 (shown in Figure 11). This is because when a small universal NSNP-DW system is used as function computing device, after each instruction simulation, the final register 8 contains n numbers (the neuron σ8 contains 2n spikes). The result n is output through the OUTPUT module.
From the discussion above, the NSNP-DW system as a function computing device can accurately simulate the register machineMu′ by using 57 neurons: (i) 7 neurons in the INPUT module, (ii) 2 neurons in the OUTPUT module, (iii) 1 neuron in each SUB instruction and 14 in total, (iv) 9 neurons in 9 registers, and (v) 25 neurons for 25 instructions.
The register machineMu′ is simulated by the NSNP-DW system, and each instruction li on Mu′ is regarded as a neuron. However, some instructions are continuous. By exploring the relationship between the instructions of Mu′, correspondingly constituted modules can be combined, instructions are omitted, and the use of neurons is reduced by the way. A detailed introduction to the initial register machine and its instructions can be found in [40]. For the NSNP-DW system, module combination is mainly divided into three categories: module ADD-ADD, module ADD-SUB, and module SUB-ADD (includes modules SUB-ADD-1 and SUB-ADD-2). The working process of module ADD-SUB and module SUB-ADD is closely related to that of module SUB. The working principle is expressed by the structure diagram. Readers interested in a description of the principle can refer to [11, 26, 41].Figure 9
Framework of the universal NSNP-DW system.Figure 10
INPUT module.Table 5
The results of spike in INPUT module whengx=4 and y=3.
Stepσinσc1σc2σc3σc4σc5σc6σ1σ2σl0t1000000000t+10110000000t+20111111000t+30111111200t+41111111400t+50221111600t+60222222800t+71220022820t+80330022840t+90002233860t+100000000862Figure 11
OUTPUT module.


### 5.1.1. Module ADD-ADD

(4)l17:ADD2,l21,l21:ADD3,l18.These are two deterministic ADD instructions. The simulation of each instruction is the same as in Figure8. The module design is shown in Figure 12 before the instruction l21 is omitted.Figure 12
Module ADD-ADD before omittingl21: the sequence of two consecutive ADD instructions l17:ADD2,l21 and l21:ADD3,l18Obviously, this is a sequence of two consecutive ADD instructions connected byl21; instruction l21 can be omitted through the following module ADD-ADD (shown in Figure 13).Figure 13
Module ADD-ADD after omittingl21: the sequence of two consecutive ADD instructions l17:ADD2,l21 and l21:ADD3,l18.


### 5.1.2. Module ADD-SUB

(5)l5:ADD5,l6,l6:SUB7,l7,l8,l9:ADD6,l10,l10:SUB4,l0,l11.These are two consecutive pairs of ADD-SUB instructions connected byl6 and l10, respectively; we can combine instructions l5:ADD5,l6 and l6:SUB7,l7,l8 into one instruction l5:ADD5,SUB7,l7,l8, which saves instruction l6. Instructions l9:ADD6,l10 and l10:SUB4,l0,l11 are combined into one instruction l9:ADD6,SUB4,l0,l11, saving instruction l10.Taking the omission ofl6 as an example, neuron σl5 sends spikes to σ5 and σl6, and then neuron σl6 performs the simulation of instruction l6. Here, neuron σl6 can be omitted, and neuron σl5 replaces σl6 to directly simulate the SUB instruction. It can be seen from Figure 14 that this is possible.Figure 14
A module for consecutive ADD-SUB instructionl5:ADD5, SUB7,l7,l8.


### 5.1.3. Module SUB-ADD

For introductionli:SUBr,lj,lk, when the value r≠0, it is subtracted by 1, and the instruction lj is executed; otherwise, the labeled lk is activated. Therefore, considering that there are two forms of consecutive SUB-ADD instructions, module SUB-ADD is divided into modules SUB-ADD-1 and SUB-ADD-2.Module SUB-ADD-1:(6)l15:SUB3,l18,l20,l20:ADD0,l0.This is the case whenlk is activated and lj is reserved. We can combine instructions l15:SUB3,l18,l20 and l20:ADD0,l0 into one instruction l15:SUB3,l18,ADD0,l0, causing instruction l20 to be omitted (see Figure 15).Figure 15
Module SUB-ADD-1: the sequence of two consecutive instructionsl15:SUB3,l18,l20 and l20:ADD0,l0.Module SUB-ADD-2:(7)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,l22:SUB0,l23,l24,l23:ADD8,l22.This is the case whenlj is activated and lk is reserved. There are six pairs of instructions that can be combined in pairs. It is found through observation that the following ADD instruction happens to be the first execution position of the previous SUB instruction. Then each pair of SUB-ADD instruction combinations can be updated to li:SUBr1,lj,lk andlj:ADDr2,lg. When the register r1≠r2, they can share one neuron σlj. In this way, six neurons in total of σ1, σ5, σ7, σ9, σ19, and σ23 can be saved. The visualization can be illustrated in Figure 16.Figure 16
Module SUB-ADD-2: the sequence of the SUB and ADD instructionsli:SUBr1,lj,lk and lj:ADDr2,lg.Through the above instruction combination (called “code optimization” in [41]), 10 neurons σ21, σ6, σ10, σ20, σ1, σ5, σ7, σ9, σ16, and σ23 can be omitted. In the end, 47 neurons are enough to complete a small universal NSNP-DW system for computing functions:(i)
Nine neurons for 9 registers.(ii)
15 neurons in remaining 15 instruction labels (ten labels are saved).(iii)
Seven neurons in the module INPUT.(iv)
14 neurons for a total of 14 SUB instructions.(v)
Two neurons in the module OUTPUT.


## 5.1.1. Module ADD-ADD

(4)l17:ADD2,l21,l21:ADD3,l18.These are two deterministic ADD instructions. The simulation of each instruction is the same as in Figure8. The module design is shown in Figure 12 before the instruction l21 is omitted.Figure 12
Module ADD-ADD before omittingl21: the sequence of two consecutive ADD instructions l17:ADD2,l21 and l21:ADD3,l18Obviously, this is a sequence of two consecutive ADD instructions connected byl21; instruction l21 can be omitted through the following module ADD-ADD (shown in Figure 13).Figure 13
Module ADD-ADD after omittingl21: the sequence of two consecutive ADD instructions l17:ADD2,l21 and l21:ADD3,l18.


## 5.1.2. Module ADD-SUB

(5)l5:ADD5,l6,l6:SUB7,l7,l8,l9:ADD6,l10,l10:SUB4,l0,l11.These are two consecutive pairs of ADD-SUB instructions connected byl6 and l10, respectively; we can combine instructions l5:ADD5,l6 and l6:SUB7,l7,l8 into one instruction l5:ADD5,SUB7,l7,l8, which saves instruction l6. Instructions l9:ADD6,l10 and l10:SUB4,l0,l11 are combined into one instruction l9:ADD6,SUB4,l0,l11, saving instruction l10.Taking the omission ofl6 as an example, neuron σl5 sends spikes to σ5 and σl6, and then neuron σl6 performs the simulation of instruction l6. Here, neuron σl6 can be omitted, and neuron σl5 replaces σl6 to directly simulate the SUB instruction. It can be seen from Figure 14 that this is possible.Figure 14
A module for consecutive ADD-SUB instructionl5:ADD5, SUB7,l7,l8.


## 5.1.3. Module SUB-ADD

For introductionli:SUBr,lj,lk, when the value r≠0, it is subtracted by 1, and the instruction lj is executed; otherwise, the labeled lk is activated. Therefore, considering that there are two forms of consecutive SUB-ADD instructions, module SUB-ADD is divided into modules SUB-ADD-1 and SUB-ADD-2.Module SUB-ADD-1:(6)l15:SUB3,l18,l20,l20:ADD0,l0.This is the case whenlk is activated and lj is reserved. We can combine instructions l15:SUB3,l18,l20 and l20:ADD0,l0 into one instruction l15:SUB3,l18,ADD0,l0, causing instruction l20 to be omitted (see Figure 15).Figure 15
Module SUB-ADD-1: the sequence of two consecutive instructionsl15:SUB3,l18,l20 and l20:ADD0,l0.Module SUB-ADD-2:(7)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,l22:SUB0,l23,l24,l23:ADD8,l22.This is the case whenlj is activated and lk is reserved. There are six pairs of instructions that can be combined in pairs. It is found through observation that the following ADD instruction happens to be the first execution position of the previous SUB instruction. Then each pair of SUB-ADD instruction combinations can be updated to li:SUBr1,lj,lk andlj:ADDr2,lg. When the register r1≠r2, they can share one neuron σlj. In this way, six neurons in total of σ1, σ5, σ7, σ9, σ19, and σ23 can be saved. The visualization can be illustrated in Figure 16.Figure 16
Module SUB-ADD-2: the sequence of the SUB and ADD instructionsli:SUBr1,lj,lk and lj:ADDr2,lg.Through the above instruction combination (called “code optimization” in [41]), 10 neurons σ21, σ6, σ10, σ20, σ1, σ5, σ7, σ9, σ16, and σ23 can be omitted. In the end, 47 neurons are enough to complete a small universal NSNP-DW system for computing functions:(i)
Nine neurons for 9 registers.(ii)
15 neurons in remaining 15 instruction labels (ten labels are saved).(iii)
Seven neurons in the module INPUT.(iv)
14 neurons for a total of 14 SUB instructions.(v)
Two neurons in the module OUTPUT.


## 5.2. Small Universal NSNP-DW Systems as Number Generator

In the simulation of number generator, the INPUT module can be combined with the OUTPUT module, found in Figure17. In the constructed INPUT-OUTPUT module, instruction lh is removed, and register 8 is no longer needed. The spike train that the input neuron gets from the environment is 10gx−11, neuron σ1 is loaded with 2gx spikes, and neuron σ2 receives 2n spikes nondeterministically. Neuron σout fires twice successively, and the time interval n is the numerical result generated.Figure 17
INPUT-OUTPUT module.The simulation of NSNP-DW systems as number generator shares 43 neurons, and the specific details will not be repeated:(i)
Eight neurons for 8 registers (no register 8).(ii)
14 neurons in the remaining 14 instruction labels (lh and ten labels are saved).(iii)
Seven neurons in the module INPUT-OUTPUT.(iv)
14 neurons for a total of 14 SUB instructions.Theorem 4.
There is a small universal NSNP-DW system possessing 43 neurons for number generator.The specific simulation will not be introduced in detail. We use an example to analyze the feasibility of number generator simulation; assuminggx=2 and n=2, the results of each step are reflected in Table 6.Table 6
The results of spike in INPUT-OUTPUT module.
Stepσinσc1σc2σc3σc4σc5σ1σ2σoutσl0t1000000000t+10111000000t+2111022201 (fire)0t+31221224201t+4000044441 (fire)1t+50000004402


## 5.3. Discussion

Theorem3 gives the Turing universal NSNP-DW system with fewer neurons as a function computing device. In order to more intuitively verify the computing power of the NSNP-DW system, Table 7 compares the number of computing units for the variant and its related systems. According to Table 7, we observe that NSNP systems, SNP systems, SNP-DS systems, and recurrent neural networks use 117, 67, 56, and 886 neurons, respectively, to accomplish Turing universality for computing function, and NSNP-DW systems only require 47 neurons. Besides, according to Table 8, we have observed that 121 neurons are reduced for simulating number generator. In short, NSNP-DW systems are better than these systems in the use of neurons, and the computational power of the NSNP system has been effectively improved.Table 7
Comparison of the least neurons of several calculation models.
Computing modelsNumber of neuronsNSNP-DW systems47NSNP systems [39]117SNP systems [11]67SNP-DS systems [31]56Recurrent neural networks [42]886Table 8
Comparison of the least neurons as number generator.
Computing modelsNumber of neuronsNSNP-DW systems43NSNP systems [39]164


## 6. A Uniform Solution to Subset Sum Problem

The Subset Sum problem is one of the typical NP-complete problems proposed in [43]. We use the NSNP-DW system to solve the uniform solution of the Subset Sum in a nondeterministic operation mode.The Swish function and the LReLU function are considered for the spike consumption function and the generating function in the problem.(8)ϕx=x⋅sigmoidx,γx=x,x>0,αx,x≤0.Problem. NAME: Subset Sum.INSTANCE: a set of positive integersV=v1,v2,…,vn and a positive integer S.QUESTION: is there a subsetB⊆V that satisfies ∑b∈Bb=S?Theorem 5.
The uniform solution of Subset Sum problem can be solved by NSNP-DW systems.Figure18 depicts the architecture of the NSNP-DW system to solve the Subset Sum in a uniform way. The complexity of the uniform solution is that the system only “recognizes” the number n when solving the problem. The instance of the problem needs to be introduced into the system. σgi,31≤i≤n is the input neuron of the system. The positive integer vi1≤i≤n in the problem is encoded into σgi,3. At the beginning of the calculation, 3v1−1 spikes a3v1−1 enter neuron σg1,3, 3v2−1 spikes a3v2−1 enter neuron σg2,3, ..., and 3vn−1 spikes a3vn−1 enter neuron σgn,3. In the initial configuration (state) of the system, except that neuron σi1≤i≤n contains four spikes, all other neurons are empty.Figure 18
An NSNP-DW system solving the Subset Sum problem.In the first calculation, both rules in neuronσi are likely to be employed first (because they have the same threshold). The indeterminate use of these two rules indicates that the system solves this Subset Sum problem in a nondeterministic way of operation, and it also corresponds to whether the integer vi is in the subset B. In the following, we carry out a complete derivation.Proof.
Neuronσi initially has four spikes. At step one, if rule 4|aϕx⟶a3/4γx is selected for use, then neuron σi will consume 4⋅sigmoid4 spikes and send three spikes to neurons σgi,1 and σgi,2, respectively (because γx=4). At step 2, neuron σgi,1 forgets three spikes by the rule 3|aϕx⟶λ. At the same time, neuron σgi,2 uses rule 3|aϕx⟶a2/3γx to become active and sends two spikes to neurons σgi,3 (because γx=3). At the end of this step, neurons σgi,1 and σgi,2 maintain their original state. At step 3, neuron σgi,3 has a total of 3vi−1 spikes and fires. The rule a2a3+|a3⟶a3 is used first, sending three spikes to neurons σgi,4 and σout, respectively. This process will continue for vi−1 steps until the rule a2a3+|a3⟶a3cannot be activated. Neurons σgi,4 and σout still cannot be active after receiving 3kk∈N spikes. When there are only two spikes left in neuron σgi,3, rule a2⟶a2 is used, and finally, two spikes are sent to neuron σgi,4 and σout, respectively. After possessing 3k+2 spikes, neuron σgi,4 fires and emits a spike to neurons σout and σh, respectively. In the next step, the neuron σout still cannot fire because it takes 3k+1 spikes to be activated. Conversely, neuron σh that has received n spikes is activated by rule an⟶a and sends one spike to neuron σout. In this way, the output neuron σout can fire and emit spikes to the environment.
If initially neuronσi uses the rule 4|aϕx⟶a1/2γx, 4⋅sigmoid4 spikes are consumed and two spikes are sent to neurons σgi,1 and σgi,2, respectively (because γx=4). In the second step, the two spikes received by neuron σgi,2 are removed by rule 2|aϕx⟶λ. Neuron σgi,1 uses the rule 2|aϕx⟶a1/2γx and sends a spike to neuron σh (because γx=2). Before the neuron σh fires, neuron σout remains inactive. After neuron σh receives a total of n spikes from σgi,11≤i≤n, it fires and sends a spike to neuron σout. In the next step, the neuron σout contains only one spike, so it does not fire, nor does it emit spikes into the environment.
At this point, we have ended the process of solving the uniform solution of the Subset Sum. Obviously, the system requires a total of5n+2 neurons. After stopping operation, if there are exactly S spikes in the environment, the answer to the problem is “yes,” which means that there is a subset B⊆V that makes ∑b∈Bb=S hold. Otherwise, it is “no.” This is enough to show that the NSNP-DW system for solving Subset Sum problem is complete.
In the calculation process, the calculation between neurons is parallel, and the rules in each neuron are calculated sequentially. Through computing and reasoning, it can be known that neuronsσi, σgi,1, σgi,2, σgi,4, and σh fire once, respectively, and neuron σgi,3 fires ∑i=1nvi times. After all other neurons stop computing, the neuron σout can fire at most ∑i=1nvi times. Therefore, the system needs ∑i=1n2vi+5 steps to complete the calculation. In addition, we choose nonlinear functions as the spike consumption function and generation function, which is closer to reality and reflects the significance of nonlinear functions in the NSNP-DW system.


## 7. Conclusions and Further Work

The nonlinear spiking neural P (NSNP) systems are variants of spiking neural P (SNP) systems. Nonlinear functions are used flexibly in NSNP systems. We focus on the computing power of NSNP systems in this work. Two mechanisms of delays and weights are introduced, and nonlinear spiking neural P systems with delays and weights (NSNP-DW) are proposed. An explicit example is given to visually demonstrate the operation of the NSNP-DW system. Through a series of simulation computing, 47 and 43 neurons are sufficient for constructing small universal NSNP-DW systems as function computing device and number generator. Compared with the NSNP systems [39], the NSNP-DW system decreases 70 neurons and 121 neurons, respectively, as function computing device and number generator. Finally, the uniform solution of the Subset Sum problem is solved efficiently by using the NSNP-DW system.For further work, the NSNP-DW system, as a distributed parallel computing model, can be combined with clustering algorithms to improve algorithm efficiency. As far as the computational power of the NSNP-DW system is concerned, we are committed to proving that the 47 and 43 neurons used by the simulating function calculation and the number generator, respectively, are the least in total. In particular, the number of spikes breaks through the integer limit and has been replaced by nonlinear functions in NSNP systems. In view of this breakthrough, we can try to link NSNP-DW systems with the neural network to expand more interesting research.



---

*Source: 3285719-2021-08-26.xml*