# Turing Universality of Weighted Spiking Neural P Systems with Anti-spikes

Authors: Qianqian Ren; Xiyu Liu; Minghe Sun
Journal: Computational Intelligence and Neuroscience
 (2020)

---

## Abstract

Weighted spiking neural P systems with anti-spikes (AWSN P systems) are proposed by adding anti-spikes to spiking neural P systems with weighted synapses. Anti-spikes behave like spikes of inhibition of communication between neurons. Both spikes and anti-spikes are used in the rule expressions. An illustrative example is given to show the working process of the proposed AWSN P systems. The Turing universality of the proposed P systems as number generating and accepting devices is proved. Finally, a universal AWSN P system having 34 neurons is proved to work as a function computing device by using standard rules, and one having 30 neurons is proved to work as a number generator.


---

## Body

## 1. Introduction

Membrane computing, introduced by Păun [1], is a branch of nature-inspired computing. It provides a rich computational framework for biomolecular computing. Models of membrane computing are inspired by the structures and functions of living cells. The obtained models are distributed and parallel computing devices, usually called P systems [2]. There are three main classes of P systems: cell-like P systems, tissue-like P systems [3], and neural-like P systems [4]. Neural-like P systems, inspired by the ways of information storage and processing in human brain nervous systems, are systems that combine neurons and membrane computing, among which the most widely known are spiking neural P systems (SN P systems) [5]. A SN P system consists of a group of neurons located at the nodes of a directed graph, and neurons send spikes to adjacent neurons through synapses, i.e., links in the graph. There is only one type of objects, i.e., spikes, in the neurons.With different biological features and mathematical motivations, many variants of SN P systems have emerged. Some of them made changes on synapses between neurons, such as SN P systems with rules on synapses [6], SN P systems with multiple channels [7], and SN P systems with thresholds [8], while others made changes on the communication rules, such as SN P systems with communication on request [9], SN P systems with polarizations [10], and SN P systems with inhibitory rules [11]. Various new variants of SN P systems are provided in [12, 13]. Recently, some new variants of neural-like P systems have been proposed, which are inspired by SN P systems, such as those reported in [14]. In addition, many publications appeared in the literature on the computational power of SN P systems as function computing devices and the number generating/accepting devices. Pǎun [18] proved small universality of SN P systems. Pan [19] proved the small universality of SN P systems with communication on request by using 14 neurons, and more details are available in [20, 21].Since the SNP system was proposed, many scholars have explored its applications. At present, there are many applications of SN P systems, such as skeletonizing image processing [22, 23], optimization problems [24], fault diagnosis [25–27], and working models [28].Inspired by the spikes of inhibition of communication between neurons, a new type of SN P systems is proposed by adding anti-spikes to SN P systems, which is called spiking neural P systems with anti-spikes (ASN P systems) [29]. In ASN P systems, each neuron contains multiple copies of symbolic object a or a¯ and processes information by spiking rules and forgetting rules. The annihilating rule aa¯⟶λ exists in each neuron and is the first to apply, meaning a and a¯ cannot coexist in any neuron. Many researchers have proposed different ASN P systems, such as ASN P systems with multiple channels [30], ASN P systems with rules on synapses [31], and asynchronous ASN P systems [32]. The computational power of ASN P systems as number generating and accepting devices, as well as function computing devices, also can be proved [33].In [34], SN P systems with weighted synapses were proposed. The weights represent the numbers of synapses between connected neurons. Based on the above, a new variant of SN P systems, called the weighted spiking neural P systems with anti-spikes (AWSN P systems),is proposed in this work. In these systems, neurons receive spikes or anti-spikes from their connected neurons and the numbers of spikes or anti-spikes they receive are determined by the weights of the synapses. Only one type of objects, i.e., spikes or antispikes, exists in each neuron with standard rules in SN P systems. These systems use spiking rules with the form of E/ac⟶ap;d (called standard rules if p=1 and extended rules otherwise), where E is a regular expression over spikes a and c, andp and d are all positive integers. The meaning of the spiking rules is that c spikes are consumed and p spikes are generated after d time periods. SN P systems also have forgetting rules of the form as⟶λ, where s is a positive integer. The meaning of the forgetting rules is that s spikes are dissolved or removed from a neuron.The rest of this article is organized as follows. In Section2, the basic knowledge of a register machine is given. The definition of AWSN P systems is given, and an example is presented to show their working process in Section 3. By simulating register machines, the computational power of AWSN P systems is proved as natural number generating devices and accepting devices in Section 4. In Section 5, the universality of these systems as function computing devices and number generating devices is obtained by using 34 neurons and 30 neurons, respectively. Remarks and future research directions are given in Section 6.


## 2. Prerequisites

The universality of systems is proved by simulating a register machineM. A register machine is structured as M=m,H,l0,lh,I, where m is the number of registers, H is the set of instruction labels, l0 and lh are the starting and ending labels, and I is the set of instructions shown below:(1)
li:ADDr,lj,lk (add 1 to register r and then go to instruction labels lj or lk with nondeterministic choice)(2)
li:SUBr,lj,lk (if register r is not empty, then subtract 1 from it and go to lj; otherwise, go to lk)(3)
lh:HALT (the ending instruction)A register machine has two modes: a generating mode and an accepting mode. A register machineM generates a set of numbers indefinitely, denoted by NgenM , and works in the following way in the generating mode. When all the registers start empty, M starts the computational process from the instruction label l0. When M reaches lh, the computation ends with the results stored in register 1. If the computation does not stop, the numbers will not be generated. A set of numbers can also be accepted by a register machine, denoted as NaccM, in the accepting mode. Only the input neuron is nonempty at the beginning. It then works in a way similar to that in the generating mode. As register machines are universal in the accepting mode, the add instructions can be written as li:ADDr,lj. Register machines can compute any set of Turing computable numbers represented by NRE (see, e.g., [6]).Generally, a universal register machine is used to compute Turing computable functions for the purpose of analyzing the computing power of system. A universal register machineMu is proposed by Minsky [35]. If φxy=Mugx,y satisfies that x and y are natural numbers and g is a recursive function, then Mu is universal, denoted by Mu=8,H,l0,lh,I, including 8 registers and 23 instructions. Compared with register machine Mu′ as shown in Figure 1, register machine Mu does not have instructions l22 and l23, and the final result is placed in register 0. Since the result is stored in register 0, it cannot contain any SUB instruction. Hence, register 8 is added and used to store the result without any SUB instruction. In general, in order to analyze the universality of the system, i.e., to verify that the system is equivalent to a Turing machine, a universal register machine Mu′as shown in Figure 1 is simulated by a system, denoted by Mu′=9,H,l0,lh,I, consisting of 9 registers and 25 instructions.Figure 1
The universal register machineMu′.


## 3. Weighted Spiking Neural P Systems with Anti-spikes

### 3.1. Definition

The proposed AWSN P system is described as follows:(1)∏=O,σ1,σ2,…,σm,syn,in,out,where(1)
O=a,a¯ is the set of alphabets, where the symbol a is a spike, and a¯ is an anti-spike.(2)
σ1,σ2,…,σm are neurons, in the form of σi=ni,Ri for 1≤i≤m, where ni≥0 is the initial number of spikes stored in σi, and Ri is the set of rules used in σi in the following form:(a)
Spiking rules,E/bc⟶b′p;d, where E is a regular expression over a or a¯, b,b′∈a,a¯, c≥p≥1, and d≥0 are the time unit(b)
Forgetting rules,bs⟶λ, where b∈a,a¯ ands≥1(3)
syn∈1,…,h×1,…,h×W represents the synapses, where W=1,…,n is the set of weights. For anyi,j,n∈syn, 1≤i,j≤h, i≠j, and n∈W.(4)
in and out are the input neuron and output neuron.In the AWSN P system, each neuron has one or more spiking rules and some of them also have forgetting rules, and either spikes or anti-spikes exist in each neuron. If there arek spikes or anti-spikes in neuron σi, bk∈LE and k≥c, the spiking rule E/bc⟶b′p;d can be stimulated. If k=c, then the spiking rule is called pure, and the rule can be written asbc⟶b′;d. The spiking rule can be interpreted as follows. If c spikes or anti-spikes are removed from neuron σi and the neuron fires, p spikes will be generated after d time periods (as usual in membrane computing, all neurons in a system Π work in parallel with an assumed global clock) and p×n spikes will be sent to neuron σji≠j, where n∈W. If the spiking rule of neuron σi is used in time d for all d≥1, the neuron will be closed before time t+d and will not receive any spikes or anti-spikes, and then the neuron will open at time t+d. If t=0, spikes will be emitted immediately, which means the neuron receives spikes or anti-spikes from the upper neuron without delay.If the forgetting rulesbs⟶λ in the neurons are used, then the s spikes or anti-spikes are removed from the neurons. Spiking rules and forgetting rules must be applied if the conditions are met, but the choice of rules is nondeterministic if the conditions of multiple rules are met in a neuron. However, the annihilating rule aa¯⟶λ must be applied first in each neuron.Through these rules, transitions between configurations can occur. Any sequence of transitions starting from the initial configuration is called a computation. A computation will stop when it reaches a configuration where all neurons are open and no rules can be used. To compute the functionf:NK⟶N, k natural numbers n1,n2⋯,nk are introduced into the system by reading a binary sequence z=10n1,10n21,…,10nk1 from the environment. That is to say, the input neuron of Π receives a spike in a step if it corresponds to 1 in z, but it receives nothing if it corresponds to 0. The input neuron received exactly k+1 spikes and will not receive any more spikes after receiving the last spike. The result of the computation is encoded in the distance between two spikes, which means that the computation halts with exactly two spikes as outputs immediately after outputting the second spike. Hence, it generates a spike string of the form 0b10r−11, for b≥0 and r=fn1,…,nk. The computation outputs no spike for a nonspecified number of steps from the beginning of the computation until outputting the first spike.LetNgen∏ and Nacc∏ be the sets of numbers generated and accepted by Π, respectively. Let NαASNPmn, with α∈gen,acc, denote the family of sets of numbers generated or accepted by an AWSN P system with m neurons and a maximum of n rules in a neuron.


### 3.2. An Illustrative Example

An example as graphically shown in Figure2 is given to explain the working process of the AWSN P system. The results of each step are shown in Table 1. A positive number in the table represents the number of spikes in the neuron, and a negative number represents the number of anti-spikes. For example, 2 means there are two spikes, and −2 means there are two anti-spikes.Figure 2
An example of the AWSN P system.Table 1
The results of the example.
Stepσ1σ2σ3σ4t2200t + 11−1−30t + 220−32t + 31−3−62t + 41−303 (fires)The system has four neurons as shown in Figure2. Assume that each of neurons σ1 and σ2 has two spikes, and neurons σ3 and σ4 are empty with no spikes. Suppose that the rule a2/a⟶a¯ in neuron σ1 can be used at time t, generating one anti-spike and sending three anti-spikes to neurons σ2 and σ3 because the weight of synapses between these neurons is 3. Two anti-spikes together with two spikes disappear immediately because the annihilating rule is applied first, and there is one anti-spike left in neuron σ2. The rule in σ2 generates two spikes to be sent to neuron σ4 and one spike to be sent to neuron σ1. So the rule in σ1 can be applied again. Neuron σ3 receives six anti-spikes from σ1 by using the rule of neuron σ1 twice, so that the rule in σ3 fires. Neuron σ4 gets three spikes (two from neuron σ2) and sends one spike to the environment.


## 3.1. Definition

The proposed AWSN P system is described as follows:(1)∏=O,σ1,σ2,…,σm,syn,in,out,where(1)
O=a,a¯ is the set of alphabets, where the symbol a is a spike, and a¯ is an anti-spike.(2)
σ1,σ2,…,σm are neurons, in the form of σi=ni,Ri for 1≤i≤m, where ni≥0 is the initial number of spikes stored in σi, and Ri is the set of rules used in σi in the following form:(a)
Spiking rules,E/bc⟶b′p;d, where E is a regular expression over a or a¯, b,b′∈a,a¯, c≥p≥1, and d≥0 are the time unit(b)
Forgetting rules,bs⟶λ, where b∈a,a¯ ands≥1(3)
syn∈1,…,h×1,…,h×W represents the synapses, where W=1,…,n is the set of weights. For anyi,j,n∈syn, 1≤i,j≤h, i≠j, and n∈W.(4)
in and out are the input neuron and output neuron.In the AWSN P system, each neuron has one or more spiking rules and some of them also have forgetting rules, and either spikes or anti-spikes exist in each neuron. If there arek spikes or anti-spikes in neuron σi, bk∈LE and k≥c, the spiking rule E/bc⟶b′p;d can be stimulated. If k=c, then the spiking rule is called pure, and the rule can be written asbc⟶b′;d. The spiking rule can be interpreted as follows. If c spikes or anti-spikes are removed from neuron σi and the neuron fires, p spikes will be generated after d time periods (as usual in membrane computing, all neurons in a system Π work in parallel with an assumed global clock) and p×n spikes will be sent to neuron σji≠j, where n∈W. If the spiking rule of neuron σi is used in time d for all d≥1, the neuron will be closed before time t+d and will not receive any spikes or anti-spikes, and then the neuron will open at time t+d. If t=0, spikes will be emitted immediately, which means the neuron receives spikes or anti-spikes from the upper neuron without delay.If the forgetting rulesbs⟶λ in the neurons are used, then the s spikes or anti-spikes are removed from the neurons. Spiking rules and forgetting rules must be applied if the conditions are met, but the choice of rules is nondeterministic if the conditions of multiple rules are met in a neuron. However, the annihilating rule aa¯⟶λ must be applied first in each neuron.Through these rules, transitions between configurations can occur. Any sequence of transitions starting from the initial configuration is called a computation. A computation will stop when it reaches a configuration where all neurons are open and no rules can be used. To compute the functionf:NK⟶N, k natural numbers n1,n2⋯,nk are introduced into the system by reading a binary sequence z=10n1,10n21,…,10nk1 from the environment. That is to say, the input neuron of Π receives a spike in a step if it corresponds to 1 in z, but it receives nothing if it corresponds to 0. The input neuron received exactly k+1 spikes and will not receive any more spikes after receiving the last spike. The result of the computation is encoded in the distance between two spikes, which means that the computation halts with exactly two spikes as outputs immediately after outputting the second spike. Hence, it generates a spike string of the form 0b10r−11, for b≥0 and r=fn1,…,nk. The computation outputs no spike for a nonspecified number of steps from the beginning of the computation until outputting the first spike.LetNgen∏ and Nacc∏ be the sets of numbers generated and accepted by Π, respectively. Let NαASNPmn, with α∈gen,acc, denote the family of sets of numbers generated or accepted by an AWSN P system with m neurons and a maximum of n rules in a neuron.


## 3.2. An Illustrative Example

An example as graphically shown in Figure2 is given to explain the working process of the AWSN P system. The results of each step are shown in Table 1. A positive number in the table represents the number of spikes in the neuron, and a negative number represents the number of anti-spikes. For example, 2 means there are two spikes, and −2 means there are two anti-spikes.Figure 2
An example of the AWSN P system.Table 1
The results of the example.
Stepσ1σ2σ3σ4t2200t + 11−1−30t + 220−32t + 31−3−62t + 41−303 (fires)The system has four neurons as shown in Figure2. Assume that each of neurons σ1 and σ2 has two spikes, and neurons σ3 and σ4 are empty with no spikes. Suppose that the rule a2/a⟶a¯ in neuron σ1 can be used at time t, generating one anti-spike and sending three anti-spikes to neurons σ2 and σ3 because the weight of synapses between these neurons is 3. Two anti-spikes together with two spikes disappear immediately because the annihilating rule is applied first, and there is one anti-spike left in neuron σ2. The rule in σ2 generates two spikes to be sent to neuron σ4 and one spike to be sent to neuron σ1. So the rule in σ1 can be applied again. Neuron σ3 receives six anti-spikes from σ1 by using the rule of neuron σ1 twice, so that the rule in σ3 fires. Neuron σ4 gets three spikes (two from neuron σ2) and sends one spike to the environment.


## 4. Computational Models

### 4.1. Generating Mode

Theorem 1.
NgenASNP∗2=NRE.Proof.
A register machineM=m,H,l0,lh,I is considered. M is simulated by an AWSN P system, including three modules, i.e., modules ADD, SUB, and OUTPUT.
In the simulation process, a registerr of M corresponds to neuronσr , and the number n contained in register r is the number of spikes contained in neuron σr. An instruction l in H corresponds to neuron σl. Furthermore, the modules require some other neurons in addition to σr and σl. The simulation of the ADD and SUB instructions begins at neuron σli. Modules ADD and SUB are simulated by sending spikes to σlj and σlk as rules in neuron σr fire. Neuron σr sends a spike to either σlj or σlk, but the choice is nondeterministic. When a spike arrives at neuron σlh, the computation in M stops, and the module OUTPUT begins to send the result stored in register 1 to the environment. At the beginning of the simulation, neuron σl0 has one spike but other neurons do not have any spikes.(a)
Module ADD (Shown in Figure3) Assume that an ADD instruction li:ADDr,lj,lk has to be simulated at time t, one spike is in neuron σli, and the rule a⟶a can be used. Neuron σli sends one spike a to neurons σr, σb1, and σb2, respectively. The rules a⟶a¯ and a⟶a in neuron σb1 are chosen in a nondeterministic way for use at time t+1. In this way, there are two cases to consider depending on the choice of the rules in σb1. If a⟶a is chosen, neuron σb2 sends a spike to neuron σlk. Thus, σlk will generate one spike by using its rule. If a⟶a¯ is chosen, neuron σb1 sends an anti-spike to neurons σli and σb2, respectively. Thus σlj will fire and generate one spike by using its rule. The rule in neuron σb2 cannot be used because of the annihilating rule, so that σlk is empty. After one spike is added to σr, the register r adds 1 and the instruction lj or lk is activated. Therefore, the ADD instruction can be simulated correctly by the module ADD.Figure 3
Module ADD: stimulating the ADD instructionli:ADDr,lj,lk.(b)
Module SUB (Shown in Figure4) Suppose that neuron σli has one spike. After the rule a⟶a¯ is enabled at time t, each of the neurons σlj and σlk receives two anti-spikes a¯, and σr receives one anti-spike. The rest of the computation can be divided into two cases according to the number of spikes contained in σr.Figure 4
Module SUB: simulating the SUB instructionli:SUBr,lj,lk.(1)
Neuronσrhas at least one spike. Neuron σr receives one anti-spike from neuron σlj, but anti-spike will disappear immediately by annihilating one spike in σr. Therefore, the rule a¯⟶a in neuron σr is not used at time t+1. At the same time, neuron σc1 opens to get one anti-spike from σli, and then the rule in σc1 fires and generates one spike but sends three spikes to neurons σlj and two spikes to σlk. The two spikes are annihilated with two anti-spikes from σli and one spike is left in neuron σlj. Simultaneously, the same happens in neuron σlk, i.e., the two spikes are annihilated immediately and there is no spike left in σlk.(2)
Neuronσrhas no spike. Neuron σr gets one anti-spike from σli and its rule can be applied at time t+1. Simultaneously, neuron σc1 gets one anti-spike from σli. Hence, one spike from σr is annihilated in the next time. The rule in σr cannot be used because σr does not have any anti-spikes. At the same time, neuron σlj receives five spikes, among which two spikes are used to annihilate the two anti-spikes received from neuron σli; thus the rule a2⟶λ in σlj can be applied. Neuron σlk receives one spike that annihilates one anti-spikea¯ received from neuron σli, and then the rule a¯⟶a in σlk is enabled to generate one spike a.Therefore, the SUB instruction can be simulated correctly by module SUB.(c)
Module OUTPUT (Shown in Figure5) Assume that σlh of system ∏ accumulated one spike at time t, and neuron σ1 has n spikes for the number n being stored in register 1 of M. When the rule in σlh′ is fired at time t, neuron σlh′ sends one spike to σ1. At this moment, σ1 has an odd number of spikes and its rule fires. At time t+1, σ1 sends one spike to σout and σb1, respectively. Thus, neuron σout has one spike, which is an odd number. At time t+2, neuron σout fires, sending one spike to the environment. At the same time, the rules in σ1 and σb1 are used, and both send one a to σout. After n−1 steps, until neuron σ1 has no spike, the number of spikes in σout is even. At the same time, the use of the rule in σ1 is stopped, and neuron σb1 has one spike. Neuron σout will receive one spike at time t+n+2, and then the number of spikes is odd. Neuron σout fires a second time. Therefore, the number computed by the AWSN P system is the difference between the first two steps when the neuron σout fires; that is, t+n+2−t+2=n. The module OUTPUT can be simulated correctly.Figure 5
Module OUTPUT.


### 4.2. Accepting Mode

Theorem 2.
NaccASNP∗2=NRE.Proof.
The proof of this theorem is similar to that of Theorem1. A register machine M=m,H,l0,lh,I, consisting of three modules, ADD, SUB, and INPUT, is considered. Module SUB is shown in Figure 4.(1)
Module ADD (Shown in Figure6) Assume that an ADD instruction li:ADDr,lj has to be simulated at time t. Suppose that one spike is in neuron σli; then the rule a⟶a can be used. Thus, neuron σli sends one spike to neurons σr and σlj. In this way, the number of spikes in σr increases by 1 and the instruction lj is activated. Hence, the ADD instruction can be simulated correctly by this module.Figure 6
Module ADD: simulating the ADD instructionli:ADDr,lj.(2)
Module INPUT (Shown in Figure7) Module INPUT shown in Figure 7 works as follows. The function of module INPUT is to read the spike train 10n−11 and compute the number n in the time between receiving two spikes. When neuron σin receives the first spike at timet and then neurons σd1,σd2, and σd3 receive one spike each, the rule in σd2and σd3 can be applied at timet+1. At timet+2, neuron σ1 gets one spike, and, at the same time, neuron σd3 gets one spike from σd2 and neuron σd2 receives one a from σd3. Therefore, in the next n−1time periods, the rules in neurons σd2 and σd3 can continued to be used. During this period, σ1 gets n−1 spikes. When neuron σin receives the second spike at step t+n, each of neurons σd2 and σd3 receives one spike at step t+n+1 and they both have two spikes. In this way, neurons σd2 and σd3 cannot fire to send any spikes to neuron σ1. In the whole process, neuron σ1 receives n−1+1=n spikes, i.e., the number nis stored in register 1.Figure 7
Module INPUT.From the descriptions above about the three modules, it is clear that the register machineM can correctly simulate the system. The proof is complete.


## 4.1. Generating Mode

Theorem 1.
NgenASNP∗2=NRE.Proof.
A register machineM=m,H,l0,lh,I is considered. M is simulated by an AWSN P system, including three modules, i.e., modules ADD, SUB, and OUTPUT.
In the simulation process, a registerr of M corresponds to neuronσr , and the number n contained in register r is the number of spikes contained in neuron σr. An instruction l in H corresponds to neuron σl. Furthermore, the modules require some other neurons in addition to σr and σl. The simulation of the ADD and SUB instructions begins at neuron σli. Modules ADD and SUB are simulated by sending spikes to σlj and σlk as rules in neuron σr fire. Neuron σr sends a spike to either σlj or σlk, but the choice is nondeterministic. When a spike arrives at neuron σlh, the computation in M stops, and the module OUTPUT begins to send the result stored in register 1 to the environment. At the beginning of the simulation, neuron σl0 has one spike but other neurons do not have any spikes.(a)
Module ADD (Shown in Figure3) Assume that an ADD instruction li:ADDr,lj,lk has to be simulated at time t, one spike is in neuron σli, and the rule a⟶a can be used. Neuron σli sends one spike a to neurons σr, σb1, and σb2, respectively. The rules a⟶a¯ and a⟶a in neuron σb1 are chosen in a nondeterministic way for use at time t+1. In this way, there are two cases to consider depending on the choice of the rules in σb1. If a⟶a is chosen, neuron σb2 sends a spike to neuron σlk. Thus, σlk will generate one spike by using its rule. If a⟶a¯ is chosen, neuron σb1 sends an anti-spike to neurons σli and σb2, respectively. Thus σlj will fire and generate one spike by using its rule. The rule in neuron σb2 cannot be used because of the annihilating rule, so that σlk is empty. After one spike is added to σr, the register r adds 1 and the instruction lj or lk is activated. Therefore, the ADD instruction can be simulated correctly by the module ADD.Figure 3
Module ADD: stimulating the ADD instructionli:ADDr,lj,lk.(b)
Module SUB (Shown in Figure4) Suppose that neuron σli has one spike. After the rule a⟶a¯ is enabled at time t, each of the neurons σlj and σlk receives two anti-spikes a¯, and σr receives one anti-spike. The rest of the computation can be divided into two cases according to the number of spikes contained in σr.Figure 4
Module SUB: simulating the SUB instructionli:SUBr,lj,lk.(1)
Neuronσrhas at least one spike. Neuron σr receives one anti-spike from neuron σlj, but anti-spike will disappear immediately by annihilating one spike in σr. Therefore, the rule a¯⟶a in neuron σr is not used at time t+1. At the same time, neuron σc1 opens to get one anti-spike from σli, and then the rule in σc1 fires and generates one spike but sends three spikes to neurons σlj and two spikes to σlk. The two spikes are annihilated with two anti-spikes from σli and one spike is left in neuron σlj. Simultaneously, the same happens in neuron σlk, i.e., the two spikes are annihilated immediately and there is no spike left in σlk.(2)
Neuronσrhas no spike. Neuron σr gets one anti-spike from σli and its rule can be applied at time t+1. Simultaneously, neuron σc1 gets one anti-spike from σli. Hence, one spike from σr is annihilated in the next time. The rule in σr cannot be used because σr does not have any anti-spikes. At the same time, neuron σlj receives five spikes, among which two spikes are used to annihilate the two anti-spikes received from neuron σli; thus the rule a2⟶λ in σlj can be applied. Neuron σlk receives one spike that annihilates one anti-spikea¯ received from neuron σli, and then the rule a¯⟶a in σlk is enabled to generate one spike a.Therefore, the SUB instruction can be simulated correctly by module SUB.(c)
Module OUTPUT (Shown in Figure5) Assume that σlh of system ∏ accumulated one spike at time t, and neuron σ1 has n spikes for the number n being stored in register 1 of M. When the rule in σlh′ is fired at time t, neuron σlh′ sends one spike to σ1. At this moment, σ1 has an odd number of spikes and its rule fires. At time t+1, σ1 sends one spike to σout and σb1, respectively. Thus, neuron σout has one spike, which is an odd number. At time t+2, neuron σout fires, sending one spike to the environment. At the same time, the rules in σ1 and σb1 are used, and both send one a to σout. After n−1 steps, until neuron σ1 has no spike, the number of spikes in σout is even. At the same time, the use of the rule in σ1 is stopped, and neuron σb1 has one spike. Neuron σout will receive one spike at time t+n+2, and then the number of spikes is odd. Neuron σout fires a second time. Therefore, the number computed by the AWSN P system is the difference between the first two steps when the neuron σout fires; that is, t+n+2−t+2=n. The module OUTPUT can be simulated correctly.Figure 5
Module OUTPUT.


## 4.2. Accepting Mode

Theorem 2.
NaccASNP∗2=NRE.Proof.
The proof of this theorem is similar to that of Theorem1. A register machine M=m,H,l0,lh,I, consisting of three modules, ADD, SUB, and INPUT, is considered. Module SUB is shown in Figure 4.(1)
Module ADD (Shown in Figure6) Assume that an ADD instruction li:ADDr,lj has to be simulated at time t. Suppose that one spike is in neuron σli; then the rule a⟶a can be used. Thus, neuron σli sends one spike to neurons σr and σlj. In this way, the number of spikes in σr increases by 1 and the instruction lj is activated. Hence, the ADD instruction can be simulated correctly by this module.Figure 6
Module ADD: simulating the ADD instructionli:ADDr,lj.(2)
Module INPUT (Shown in Figure7) Module INPUT shown in Figure 7 works as follows. The function of module INPUT is to read the spike train 10n−11 and compute the number n in the time between receiving two spikes. When neuron σin receives the first spike at timet and then neurons σd1,σd2, and σd3 receive one spike each, the rule in σd2and σd3 can be applied at timet+1. At timet+2, neuron σ1 gets one spike, and, at the same time, neuron σd3 gets one spike from σd2 and neuron σd2 receives one a from σd3. Therefore, in the next n−1time periods, the rules in neurons σd2 and σd3 can continued to be used. During this period, σ1 gets n−1 spikes. When neuron σin receives the second spike at step t+n, each of neurons σd2 and σd3 receives one spike at step t+n+1 and they both have two spikes. In this way, neurons σd2 and σd3 cannot fire to send any spikes to neuron σ1. In the whole process, neuron σ1 receives n−1+1=n spikes, i.e., the number nis stored in register 1.Figure 7
Module INPUT.From the descriptions above about the three modules, it is clear that the register machineM can correctly simulate the system. The proof is complete.


## 5. A Small Universal AWSN P System

### 5.1. The Universality as Function Computing Devices

Theorem 3.
There is a universal AWSN P system having 34 neurons which can be used to perform function computing.Proof.
A general framework of a system∏u′ used to simulate a universal register machine Mu′ is shown in Figure 8, which is a universal AWSN P system. Π′ consists of 8 modules: ADD, SUB, ADD-ADD, SUB-ADD-1, SUB-ADD-2, SUB-SUB, INPUT, and OUTPUT. The modules SUB, OUTPUT, and ADD are the same as those in Figures 4–6, respectively. The module INPUT is shown in Figure 9.
Module INPUT works as follows: when neuronσin gets a spike from the environment, the rule a⟶a fires and one spike is sent to neurons σc1, σc3, and σc4, and two spikes are sent to neuron σc2. Then, the rule in neuron σc1 sends one spike to both σc2 and σ1. At the same time, neuron σc2 fires and then sends one spike to σc1 and two spikes to σc3. Up to this point, three spikes were sent to neuron σc3. Therefore, before neuron σin receives more spikes from the environment, neurons σc1 and σc2 have received one spike from each other in each time period and neuron σ1 has received gx spikes.
Whenσin receives the second spike, each of the neurons σc1, σc3, and σc4 can get one spike and σc2 gets two spikes. Neuron σc2 has four spikes at this moment, and its rule can be used to send two spikes to neuron σc3. Neuron σc3 then has six spikes, so that the rule in σc3 is used to produce one spike and send it to σc2. In this way, neurons σc2 and σc3 receive one spike from each other in each step before σin receives the third spike from the environment. Neuron σ2 has y spikes at the end. When neuron σin receives the third spike, each of the neurons σc1, σc3, and σc4 gets one spike, while σc2 receives two spikes. As a result, neuron σc3 has an odd number of spikes and the rule cannot be applied. At present, neuron σc4 has three spikes, and the rule a3⟶a in neuron σc4 fires, which generates one spike and sends it to σl0. In this way, it can simulate the instruction l0 in the next step.
As with the proof of Theorems1 and 2, the system uses the following numbers of neurons:9 neurons for 9 registers25 neurons for 25 labels5 neurons for the module INPUT1 neuron in each SUB instructions and 14 in total2 neurons for the module OUTPUT
Therefore, totally 55 neurons are used.
The numbers of neurons can be decreased by exploring some relationships between some instructions of register machineMu′. The following modules are given to reduce the number of neurons in the computation process.
The SUB-ADD instructions can be divided into two cases, depending on the number of spikes placed in registerr1 (the register involved in the SUB instruction). Modules SUB-ADD-1 and SUB-ADD-2 shown in Figures 10 and 11 can simulate the SUB and ADD instructions sequentially. The working process of module SUB-ADD-1 is similar to that of module SUB. When the rule in neuron σli is used and σr1 contains at least one spike, neuron σr1 cannot fire. Neuron σc1 fires by receiving one a¯ and then sends one spike to σr2. At the end of the computation, neuron σlg has one spike, neuron σr2 has one spike, and neuron σlk is empty. When σr1 is empty, neurons σr2 and σlg are also empty and neuron σlk contains one spike. Thus, each pair of SUB-ADD-1 instructions li:SUBr1,lj,lk and lj:ADDr2,lg can share a common neuron when r1≠r2, and there are totally 6 pairs in Mu′:(2)l0:SUB1,l1,l2,l1:ADD7,l0,l4:SUB6,l5,l3,l5:ADD5,l6,l6:SUB7,l7,l8,l7:ADD6,l4,l8:SUB6,l9,l0,l9:ADD6,l10,l14:SUB5,l16,l17,l16:ADD4,l11,l22:SUB0,l23,lh′,l23:ADD0,l0.
By using this module, 6 neurons can be saved. In the same way, the module shown in Figure10 can simulate the two instructions l15 and l20. Neuron σl20 can be saved.
The module ADD-ADD shown in Figure12 can simulate instructions l17 and l21. In this way, one neuron can be saved.
The SUB instructions share a common neuron when the labels of their registers are different, as shown in Figure13. Assume that the simulation of the SUB instruction li:SUBr1,lj,lk starts at time t. When neuron σli gets a spike, the rule a⟶a¯ fires and sends one anti-spike to σr1 and two anti-spikes to σlj and σlk, respectively, at time t+1. Neuron σc1 receives an anti-spike at time t+2. Neurons σr1, σlj, σlk, and σc1 work in the same way as those in module SUB shown in Figure 4. Neuron σc1 will send three spikes to σlk′ and two spikes to σlj′, where forgetting rules will be applied. Thus, the instruction li:SUBr1,lj,lk is correctly simulated by this module. The process when starting with instruction li′ is similar to that described above.
Two SUB modules dealing with the same register, as shown in Figure14, can also be proved to work correctly in a similar way. Assume that the instruction li:SUBr1,lj,lk is simulated and one spike is contained in neuron σli′. The process is divided into two cases according to the number of spikes in neuron σr. When σr has at least one spike, the working process of the system is similar to that of module SUB. When σr is empty, the rule in neuron σc1 cannot be used. Neurons σlj, σlk′, and σlj′ are all empty but neuron σlk contains one spike. All SUB instructions can be simulated correctly by the module. Therefore, all SUB modules can share a common neuron.
From the above description about the numbers of neurons saved, the system uses the following:9 neurons for 9 registers17 neurons for 17 labels5 neurons for the module INPUT1 neuron for all the 14 SUB instructions2 neurons for the module OUTPUT
A total of 21 neurons can be saved and the number of neurons in this system can be decreased from 55 to 34. The proof is complete.Figure 8
General framework of the universal AWSN P system.Figure 9
Module INPUT.Figure 10
Module SUB-ADD-1: the sequence of the ADD and SUB instructionslj:ADDr2,lg and li:SUBr1,lj,lk.Figure 11
Module SUB-ADD-2: the sequence of the ADD and SUB instructionsl20:ADD0,l0 and l15:SUB3,l18,l20.Figure 12
Module ADD-ADD: the sequence of ADD and ADD instructionsl17:ADD2,l21 and l21:ADD3,l18.Figure 13
Module SUB-SUB withr1≠r2.Figure 14
Module SUB-SUB withr1=r2.


### 5.2. The Small Universality as Number Generator

A small universal AWSN P system as a number generator is considered. The process of simulating universal number generators is similar to that of simulating general function computing devices, but the difference between them lies in the module INPUT. The system starts with the spike train10gx−11 from environment and ends with neuron σ1 receivinggx spikes. This system is then loaded with an arbitrary number k, and neuron σ2 receives k spikes. The number k is also the output at the same time as the output spike train 10gx−11, with gx in register 1 and k in register 2. Since the output module is not required, that is to say, register 8 is not required, the register machine Mu is simulated. If the computation in Mu halts, the computation can also halt.Furthermore, module INPUT and module OUTPUT can be combined. The module INPUT-OUTPUT is shown in Figure15, and an example is used to prove its feasibility. The label lh′ can also be saved because of module INPUT-OUTPUT. The string 101 is used in module INPUT-OUTPUT, where gx=2 and k=4. The computation follows the above working processes of the modules. The results of each step are shown in Table 2.Figure 15
Module INPUT-OUTPUT.Table 2
The computation process of the module INPUT-OUTPUT.
Stepσinσf1σf2σf3σf4σf5σ1σ2σoutσl0t1000200000t+10110200000t+2111126102 (fire)0t+30221182130t+40220042230t+50220−122330t+6022001244 (fire)1Assume thatσin has one spike at timet, and neuron σf4 has two spikes. At timet+1, σf1 and σf2 receive one spike, respectively. From the structure shown in Figure 15, neurons σf1 and σf2 receive one spike from each other at each step until σf1 and σf2stop firing. Then σin receives the second spike. Each of neurons σ1 and σf3 receives one spike, σf5 receives six spikes, and σout receives two spikes, so that neurons σf5 and σout can fire. At timet+3, both σf1 and σf2 have two spikes, but they cannot fire again. σf5 receives six spikes from σf2, but σf5 also receives two anti-spikes from σf3, plus four spikes existing in σf5, so that neuron σf5 has eight spikes. In addition, neuron σout receives two spikes again, so that there are three spikes contained. Neuron σf4 only has one spike because the received anti-spike annihilates one spike. At timet+4, the neuron σf4 is empty after receiving an anti-spike. σf5 receives two anti-spikes, so that there are four spikes contained in neuron σf5, the number of spikes is even, and its rule can fire. At the next step, σf4 receives one anti-spike and fires. Neuron σf5 consumes two spikes and still can fire. At timet+6, neurons σf5 and σout receive one spike from σf4, respectively. So, there are 4 spikes in σout, meeting the required conditions for firing. Neuron σl0 also gets one spike.The string is read through neuronσin, and g(x) spikes are stored in register 1 when the calculation stops. At the same time , the output number (t + 6 − t − 2 = 4) is the same as the number stored in register 2. Neuron σl0 activates and starts simulating the register machine by simulating modules ADD and SUB. Therefore, through this process, the module INPUT-OUTPUT can be simulated correctly.Therefore, this system contains the following:8 neurons for the 8 registers14 neurons for the 14 labels (lh is saved; 8 neurons are saved by modules SUB-ADD and ADD-ADD)1 neuron for 13 SUB instructions7 neurons in the module INPUT-OUTPUTThere is a universal AWSN P system having 30 neurons that can be used to perform number generating.


## 5.1. The Universality as Function Computing Devices

Theorem 3.
There is a universal AWSN P system having 34 neurons which can be used to perform function computing.Proof.
A general framework of a system∏u′ used to simulate a universal register machine Mu′ is shown in Figure 8, which is a universal AWSN P system. Π′ consists of 8 modules: ADD, SUB, ADD-ADD, SUB-ADD-1, SUB-ADD-2, SUB-SUB, INPUT, and OUTPUT. The modules SUB, OUTPUT, and ADD are the same as those in Figures 4–6, respectively. The module INPUT is shown in Figure 9.
Module INPUT works as follows: when neuronσin gets a spike from the environment, the rule a⟶a fires and one spike is sent to neurons σc1, σc3, and σc4, and two spikes are sent to neuron σc2. Then, the rule in neuron σc1 sends one spike to both σc2 and σ1. At the same time, neuron σc2 fires and then sends one spike to σc1 and two spikes to σc3. Up to this point, three spikes were sent to neuron σc3. Therefore, before neuron σin receives more spikes from the environment, neurons σc1 and σc2 have received one spike from each other in each time period and neuron σ1 has received gx spikes.
Whenσin receives the second spike, each of the neurons σc1, σc3, and σc4 can get one spike and σc2 gets two spikes. Neuron σc2 has four spikes at this moment, and its rule can be used to send two spikes to neuron σc3. Neuron σc3 then has six spikes, so that the rule in σc3 is used to produce one spike and send it to σc2. In this way, neurons σc2 and σc3 receive one spike from each other in each step before σin receives the third spike from the environment. Neuron σ2 has y spikes at the end. When neuron σin receives the third spike, each of the neurons σc1, σc3, and σc4 gets one spike, while σc2 receives two spikes. As a result, neuron σc3 has an odd number of spikes and the rule cannot be applied. At present, neuron σc4 has three spikes, and the rule a3⟶a in neuron σc4 fires, which generates one spike and sends it to σl0. In this way, it can simulate the instruction l0 in the next step.
As with the proof of Theorems1 and 2, the system uses the following numbers of neurons:9 neurons for 9 registers25 neurons for 25 labels5 neurons for the module INPUT1 neuron in each SUB instructions and 14 in total2 neurons for the module OUTPUT
Therefore, totally 55 neurons are used.
The numbers of neurons can be decreased by exploring some relationships between some instructions of register machineMu′. The following modules are given to reduce the number of neurons in the computation process.
The SUB-ADD instructions can be divided into two cases, depending on the number of spikes placed in registerr1 (the register involved in the SUB instruction). Modules SUB-ADD-1 and SUB-ADD-2 shown in Figures 10 and 11 can simulate the SUB and ADD instructions sequentially. The working process of module SUB-ADD-1 is similar to that of module SUB. When the rule in neuron σli is used and σr1 contains at least one spike, neuron σr1 cannot fire. Neuron σc1 fires by receiving one a¯ and then sends one spike to σr2. At the end of the computation, neuron σlg has one spike, neuron σr2 has one spike, and neuron σlk is empty. When σr1 is empty, neurons σr2 and σlg are also empty and neuron σlk contains one spike. Thus, each pair of SUB-ADD-1 instructions li:SUBr1,lj,lk and lj:ADDr2,lg can share a common neuron when r1≠r2, and there are totally 6 pairs in Mu′:(2)l0:SUB1,l1,l2,l1:ADD7,l0,l4:SUB6,l5,l3,l5:ADD5,l6,l6:SUB7,l7,l8,l7:ADD6,l4,l8:SUB6,l9,l0,l9:ADD6,l10,l14:SUB5,l16,l17,l16:ADD4,l11,l22:SUB0,l23,lh′,l23:ADD0,l0.
By using this module, 6 neurons can be saved. In the same way, the module shown in Figure10 can simulate the two instructions l15 and l20. Neuron σl20 can be saved.
The module ADD-ADD shown in Figure12 can simulate instructions l17 and l21. In this way, one neuron can be saved.
The SUB instructions share a common neuron when the labels of their registers are different, as shown in Figure13. Assume that the simulation of the SUB instruction li:SUBr1,lj,lk starts at time t. When neuron σli gets a spike, the rule a⟶a¯ fires and sends one anti-spike to σr1 and two anti-spikes to σlj and σlk, respectively, at time t+1. Neuron σc1 receives an anti-spike at time t+2. Neurons σr1, σlj, σlk, and σc1 work in the same way as those in module SUB shown in Figure 4. Neuron σc1 will send three spikes to σlk′ and two spikes to σlj′, where forgetting rules will be applied. Thus, the instruction li:SUBr1,lj,lk is correctly simulated by this module. The process when starting with instruction li′ is similar to that described above.
Two SUB modules dealing with the same register, as shown in Figure14, can also be proved to work correctly in a similar way. Assume that the instruction li:SUBr1,lj,lk is simulated and one spike is contained in neuron σli′. The process is divided into two cases according to the number of spikes in neuron σr. When σr has at least one spike, the working process of the system is similar to that of module SUB. When σr is empty, the rule in neuron σc1 cannot be used. Neurons σlj, σlk′, and σlj′ are all empty but neuron σlk contains one spike. All SUB instructions can be simulated correctly by the module. Therefore, all SUB modules can share a common neuron.
From the above description about the numbers of neurons saved, the system uses the following:9 neurons for 9 registers17 neurons for 17 labels5 neurons for the module INPUT1 neuron for all the 14 SUB instructions2 neurons for the module OUTPUT
A total of 21 neurons can be saved and the number of neurons in this system can be decreased from 55 to 34. The proof is complete.Figure 8
General framework of the universal AWSN P system.Figure 9
Module INPUT.Figure 10
Module SUB-ADD-1: the sequence of the ADD and SUB instructionslj:ADDr2,lg and li:SUBr1,lj,lk.Figure 11
Module SUB-ADD-2: the sequence of the ADD and SUB instructionsl20:ADD0,l0 and l15:SUB3,l18,l20.Figure 12
Module ADD-ADD: the sequence of ADD and ADD instructionsl17:ADD2,l21 and l21:ADD3,l18.Figure 13
Module SUB-SUB withr1≠r2.Figure 14
Module SUB-SUB withr1=r2.


## 5.2. The Small Universality as Number Generator

A small universal AWSN P system as a number generator is considered. The process of simulating universal number generators is similar to that of simulating general function computing devices, but the difference between them lies in the module INPUT. The system starts with the spike train10gx−11 from environment and ends with neuron σ1 receivinggx spikes. This system is then loaded with an arbitrary number k, and neuron σ2 receives k spikes. The number k is also the output at the same time as the output spike train 10gx−11, with gx in register 1 and k in register 2. Since the output module is not required, that is to say, register 8 is not required, the register machine Mu is simulated. If the computation in Mu halts, the computation can also halt.Furthermore, module INPUT and module OUTPUT can be combined. The module INPUT-OUTPUT is shown in Figure15, and an example is used to prove its feasibility. The label lh′ can also be saved because of module INPUT-OUTPUT. The string 101 is used in module INPUT-OUTPUT, where gx=2 and k=4. The computation follows the above working processes of the modules. The results of each step are shown in Table 2.Figure 15
Module INPUT-OUTPUT.Table 2
The computation process of the module INPUT-OUTPUT.
Stepσinσf1σf2σf3σf4σf5σ1σ2σoutσl0t1000200000t+10110200000t+2111126102 (fire)0t+30221182130t+40220042230t+50220−122330t+6022001244 (fire)1Assume thatσin has one spike at timet, and neuron σf4 has two spikes. At timet+1, σf1 and σf2 receive one spike, respectively. From the structure shown in Figure 15, neurons σf1 and σf2 receive one spike from each other at each step until σf1 and σf2stop firing. Then σin receives the second spike. Each of neurons σ1 and σf3 receives one spike, σf5 receives six spikes, and σout receives two spikes, so that neurons σf5 and σout can fire. At timet+3, both σf1 and σf2 have two spikes, but they cannot fire again. σf5 receives six spikes from σf2, but σf5 also receives two anti-spikes from σf3, plus four spikes existing in σf5, so that neuron σf5 has eight spikes. In addition, neuron σout receives two spikes again, so that there are three spikes contained. Neuron σf4 only has one spike because the received anti-spike annihilates one spike. At timet+4, the neuron σf4 is empty after receiving an anti-spike. σf5 receives two anti-spikes, so that there are four spikes contained in neuron σf5, the number of spikes is even, and its rule can fire. At the next step, σf4 receives one anti-spike and fires. Neuron σf5 consumes two spikes and still can fire. At timet+6, neurons σf5 and σout receive one spike from σf4, respectively. So, there are 4 spikes in σout, meeting the required conditions for firing. Neuron σl0 also gets one spike.The string is read through neuronσin, and g(x) spikes are stored in register 1 when the calculation stops. At the same time , the output number (t + 6 − t − 2 = 4) is the same as the number stored in register 2. Neuron σl0 activates and starts simulating the register machine by simulating modules ADD and SUB. Therefore, through this process, the module INPUT-OUTPUT can be simulated correctly.Therefore, this system contains the following:8 neurons for the 8 registers14 neurons for the 14 labels (lh is saved; 8 neurons are saved by modules SUB-ADD and ADD-ADD)1 neuron for 13 SUB instructions7 neurons in the module INPUT-OUTPUTThere is a universal AWSN P system having 30 neurons that can be used to perform number generating.


## 6. Conclusions

In this work, a variant of the SN P systems, called the AWSN P systems,is proposed. Because of the use of anti-spikes, the proposed systems are more biologically significant thanSN P systems, with inhibitory spikes in the communication between neurons. An example is used to illustrate the working process of this system. The computational universality is then proved in the case of generating mode and accepting mode, respectively. Finally, the Turing universality of AWSN P systems is proved. The function computing device can be realized by using 34 neurons. Compared with the small universal SN P system using anti-spikes introduced by Song [17], the AWSN P system uses 13 fewer neurons. Compared with the SN P systems with weighted synapses introduced by Pan [34], the AWSN P system uses 4 fewer neurons. The small universality of the ASN P system as number generator is investigated with 30 neurons. Compared with Pan’s work [34], the proposed system uses 6 fewer neurons.The computational universality is proved for AWSN P systems with standard rules. There are three types of spiking rules,a⟶a¯, a⟶a, and a¯⟶a, used that are time dependent, and there is one type of forgetting rules, ac⟶λ. There are several future research directions. One direction is to investigate whether the computational power will remain the same if only one or two types of spiking rules are used or if the forgetting rules are not used and to investigate whether AWSN P systems can perform better or the same if the spiking rules are not time-dependent. These open problems certainly need further studies. Another future research direction is the application of the proposed systems. There have been studies, such as using SN P systems with learning function for letter recognitions [36]. If the learning function was introduced in AWSN P systems, it may perform better in letter recognitions. Because the use of anti-spikes improves the ability of AWSN P systems to represent and process information, it may solve more practical problems, which still require further research.



---

*Source: 8892240-2020-09-17.xml*