# Spiking Neural P Systems with Rules Dynamic Generation and Removal
## 3 The Turing Universality of SNP Systems with Rules Dynamic Generation and Removal  
This section is used to prove the Turing universality of RDGRSNP systems when used as a number-generating device and a number-accepting device, respectively. It has been shown that register machines can be used to characterize Turing computable sets of numbers (NRE), so we demonstrate the Turing universality of RDGRSNP systems by simulating register machines. Figure 1: An Illustrative Example. For a register machine \(M=(m,H,l_{0},l_{h},I)\), \(m\) denotes the number of registers \(r\) in the register machine \(M\), \(H\) is a label set in which each label corresponds to an instruction in the instruction set \(I\), \(l_{0}\) denotes the start instruction, \(l_{h}\) denotes the halt instruction, and \(I\) denotes an instruction set. The instructions in \(I\) have the following three forms:  
1. \(l_{i}:(ADD(r),l_{j},l_{k})\), the instruction indicates that: add one to the number in \(r\) and then jump non-deterministically to \(l_{j}\) or \(l_{k}\);
2. \(l_{i}:(SUB(r),l_{j},l_{k})\), the instruction indicates that: if the number in \(r\) is not zero, subtract the number by one and jump to \(l_{j}\); if the number in \(r\) is zero, jump directly to \(l_{k}\);
3. \(l_{h}:HALT\), the instruction is the halt instruction, indicating that \(M\) stops computing. In the number-generating mode, all registers in \(M\) are initially empty, and \(M\) starts from \(l_{0}\) and executes until \(l_{h}\). After the computation is finished, all registers except register 1 are empty, and the number generated by \(M\) is stored in register 1. It is assumed that there is no \(l_{i}:(SUB(r),l_{j},l_{k})\) for the instructions related to register 1, i.e., the number in register 1 will not be subtracted. In the number-accepting mode, all registers of \(M\) except register 1 are initially empty, and the number to be accepted is stored in register 1. If \(M\) can reach the halt instruction \(l_{h}:HALT\), it proves that the number is accepted by \(M\). Note that the instruction \(l_{i}:(ADD(r),l_{j},l_{k})\) needs to be changed to deterministic \(l_{i}:(ADD(r),l_{j})\) in the number accepting mode. In this paper, we use \(N_{2}RDGRSNP(\Pi)\) and \(N_{acc}RDGRSNP(\Pi)\) to denote the set of numbers that can be generated and accepted by a RDGRSNP system, respectively. In the proofs of this paper, we use neuron \(\sigma_{l_{i}}\) to denote instruction \(l_{i}\), neuron \(\sigma_{r}\) to denote register \(r\), and auxiliary neurons \(\sigma_{l_{i}^{(j)}}\) for module construction, where \(j\in N^{+}\). In addition, we stipulate that the simulation of instruction \(l_{i}\) starts when \(\sigma_{l_{i}}\) has four spikes. **Theorem 1**. : \(N_{2}RDGRSNP(\Pi)=NRE\)__  
Proof. : By [PERSON]'s theorem, there is \(N_{2}RDGRSNP(\Pi)\subseteq NRE\), so it is sufficient if we can prove \(NRE\subseteq N_{2}RDGRSNP(\Pi)\). For \(NRE\subseteq N_{2}(\Pi)\), we simulate the register machine to prove it by following the process shown in Figure 2.  
In the initial state, all neurons are empty except neuron \(\sigma_{l_{0}}\). Four spikes in neuron \(\sigma_{l_{0}}\) are used to trigger the simulation of computation. The simulation of computation follows the simulation of the instructions in the register machine until neuron \(\sigma_{l_{h}}\) receives four spikes. When neuron \(\sigma_{l_{h}}\) receives four spikes, it means that the computation process  
Figure 2: The flowchart of the SNP system with rules dynamic generation and removal simulating register machine in the number-generating mode. in the register machine is successfully simulated, and the FIN module starts to output the computation result stored in register 1. **ADD module:** The ADD module is used to simulate instruction \(l_{i}:(ADD(r),l_{j},l_{k})\), as shown in Figure 3. This module consists of six neurons and eight rules. Suppose that at step \(t\), \(\sigma_{l_{i}}\) has four spikes and starts simulating instruction \(l_{i}:(ADD(r),l_{j},l_{k})\).