Dendrite P systems

Dendrite P systems✩ Hong Peng a, Tingting Bao a, Xiaohui Luo a, Jun Wang b,∗, Xiaoxiao Song b, Agustín Riscos-Núñez c, Mario J. Pérez-Jiménez c a School of Computer and Software Engineering, Xihua University, Chengdu 610039, China b School of Electrical Engineering and Electronic Information, Xihua University, Chengdu 610039, China c Research Group of Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Sevilla 41012, Spain Keywords: P systems Neural-like P systems Dendrite P systems Computational power a b s t r a c t It was recently found that dendrites are not just a passive channel. They can perform mixed computation of analog and digital signals, and therefore can be abstracted as information processors. Moreover, dendrites possess a feedback mechanism. Motivated by these computational and feedback characteristics, this article proposes a new variant of neural-like P systems, dendrite P (DeP) systems, where neurons simulate the computational function of dendrites and perform a firing–storing process instead of the storing–firing process in spiking neural P (SNP) systems. Moreover, the behavior of the neurons is characterized by dendrite rules that are abstracted by two characteristics of dendrites. Different from the usual firing rules in SNP systems, the firing of a dendrite rule is controlled by the states of the corresponding source neurons. Therefore, DeP systems can provide a collaborative control capability for neurons. We discuss the computational power of DeP systems. In particular, it is proven that DeP systems are Turing-universal number generating/accepting devices. Moreover, we construct a small universal DeP system consisting of 115 neurons for computing functions. 1. Introduction Neural-like P systems are one of the main types of membrane computing models (Bernardini & Gheorghe,2004;Ciencialová, Csuhaj-Varjú, Kelemenová, & Vaszil,2009;Freund, Pˇ aun, & Pérez-Jiménez,2005;Gheorghe et al.,2013;Martínez-DelAmor, Macías-Ramos, Valencia-Cabrera, & Pérez-Jiménez,2016; Pavel & Buiu,2012;Peng, Shi, Wang, Riscos-Núñez, & PérezJiménez,2017;Peng, Wang, Pérez-Jiménez, & Riscos-Núñez,2015; Peng, Wang, Shi, Pérez-Jiménez, & Riscos-Núñez,2016;Păun, 2000;Pˇ aun & Pérez-Jiménez,2010;Pˇ aun & Pˇ aun,2006;Song, Zhang, & Pan,2016;Wang, Shi, & Peng,2016;Xue et al.,2018; Zhang, Gheorghe, Pan, & Pérez-Jiménez,2014;Zhang, Wu, Pˇ aun, & Pan,2016;Zhao, Liu, & Qu,2012). They generally refer to a class of distributed and parallel computing models, motivated by the mechanisms of biological neurons and nervous systems. Topologically, neural-like P systems are expressed by a directed graph or a more complex network. They address three main topics: (i) models and computational theoretical problems (universality, ✩This work was partially supported by Research Fund of Sichuan Science and Technology Project China (No. 2018JY0083), and Research Foundation of the Education Department of Sichuan province China (No. 17TD0034), China. ∗Corresponding author. effectiveness, and complexity); (ii) application of models; and (iii) implementation of models. Much effort has been made in the realm, as found in the Handbook of Membrane Computing (Păun, Rozenberg, & Salomaa,2010). Spiking neural P (SNP) systems (Ionescu, Păun, & Yokomori, 2006) are a widely studied type of neural-like P system, inspired by the way that neurons work with and exchange information by sending spikes along synapses. An SNP system is a distributed and parallel computing model. Except a directed graph, SNP systems have two components: data and rules. Data can usually be denoted by the number of spikes in each neuron, and the collection of the states of all neurons, known as a configuration, describes the state of the entire system. The behavior of the system is controlled by firing rules and forgetting rules. Firing rules are expressed by the form E/ac→ap, where Eis a regular expression. To distinguish the dendrite rules presented below, E/ac→apare called ‘‘usual firing rules’’ in this work, and their semantics can be illustrated as follows. Suppose that a neuron σ has a firing rule E/ac→apand nspikes. If an∈L(E) and n≥c, then the neuron can fire. When the neuron fires, it consumes c spikes (n−cspikes are retained) and generates pspikes. The generated pspikes will be sent to its succeeding neurons. If p=0, then the rules can be written in the form ac→λ. A forgetting rule indicates that cspikes are consumed, but no spike is generated. From the perspective of working mechanism, the action of a neuron contains the two steps of integration and excitation. In E-mail addresses: [email protected] (H. Peng), [email protected] (J. Wang). the integration step, a neuron receives, accumulates, and stores the spikes that its prepositive (source) neurons send out. The excitation step accomplishes a neuron’s firing procedure, as described above. Therefore, the working mechanism of neurons can be simply summarized as a storing–firing process: the spikes are first stored and then are excited by the firing rules. Many variants have appeared since SNP systems were first proposed. Abstracted from the inhibitory and excitatory influence of astrocytes on synapses, Păun (2007) discussed SNP systems with astrocytes. Pan, Wang, and Hoogeboom (2012) presented SNP systems with anti-spikes inspired by inhibitory impulses/spikes. Peng, Yang, et al. (2017) and Song et al. (2018) discussed SNP systems with multiple channels. SNP systems with polarizations were discussed in Wu, Păun, Zhang, and Pan (2018). The structural dynamism of biological synapses inspired Cabarle, Adorna, Jiang, and Zeng (2016) to propose an SNP system with scheduled synapses. Considering a new communication strategy among neurons, Pan, Păun, Zhang, and Neri (2017) investigated SNP systems with communication on request. Wang, Hoogeboom, Pan, Păun, and Pérez-Jiménez (2010) discussed an SNP system with weights, while Zeng, Zhang, Song, and Pan (2014) presented SNP systems with thresholds. Abstracted from Eckhorn’s neuron model and intersecting cortical model (ICM), coupled neural P systems and dynamic threshold neural P systems were investigated by Peng and Wang (2018), Peng, Wang, Pérez-Jiménez, and Riscos-Núñez (2019), respectively. Moreover, spiking neural P systems with inhibitory rules and nonlinear spiking neural P systems were discussed in Peng, Li, et al. (2020), Peng, Lv, et al. (2020). Ionescu, Păun, Pérez-Jiménez, and Yokomori (2011) discussed spiking neural dP systems (with request rules). With the limitation that at each time at most one neuron works, sequential SNP systems were discussed in Ibarra, Păun, and Rodríguez-Pa´ ton (2009) and Zhang, Zeng, Luo, and Pan (2014). A global clock is usually assumed in the above SNP systems, in which case they are synchronized. Cavaliere et al. (2009) and Song, Pan, and Păun (2012) discussed a number of asynchronous SNP systems. Several SNP systems using fuzzy logic were investigated, for example, weighted fuzzy SNP systems (Wang, Shi, Peng, Pérez-Jiménez, & Wang,2013) and fuzzy reasoning SNP systems (Peng et al., 2013). Computational power (as function computing devices and number or language generating devices) has been discussed. As number generating/accepting devices (Cabarle et al.,2016; Cavaliere et al.,2009;Ionescu et al.,2006;Pan et al.,2017;Peng, Yang, et al.,2017;Păun,2007;Song et al.,2012), language generators (Chen, Freund, Ionescu, Păun, & Pérez-Jiménez,2007;Zhang, Zeng, & Pan,2008), and function computing devices (Păun & Păun, 2007;Păun & Sidoroff,2012;Wu et al.,2018), it was proven that many variants of SNP systems are Turing universal. Some efforts have been made to apply SNP systems to practical problems, such as image processing (Díaz-Pernil, Gutiérrez-Naranjo, & Peng, 2019;Díaz-Pernil, Peña-Cantillana, & Gutiérrez-Naranjo,2013), fault diagnosis (Peng, Wang, Ming, et al.,2018;Peng, Wang, Shi, Pérez-Jiménez, & Riscos-Núñez,2017;Wang et al.,2015), and combinatorial optimization problems (Zhang, Rong, Neri, & Pérez-Jiménez,2014), and a number of other SNP systems were implemented (Carandang, Villaflores, Cabarle, Adorna, & Martínez-Del-Amor,2017;Macías-Ramos, Pérez-Jiménez, Song, & Pan,2015). Spiking neural P systems with rules on synapses (Song, Pan, , & Păun,2014) are an interesting form of neural-like P systems where the firing and forgetting rules are moved from neurons to synapses. Thus synapses are regarded as information processing units, while neurons are degenerated into storage units. In addition, Peng et al. (2018) and Song and Pan (2015) discussed two distinct spike consumption strategies, and computational power of the variants as function computing devices and number generating/accepting devices has been discussed. Chen, Ishdorj, and Păun (2007) discussed another form of neural-like P systems, axon P systems, where nodes are placed in a linear way and each sends spikes only to two neighbors. An axon P system is executed concurrently and can nondeterministically process information in nodes. The universality results of axon P systems as function computing, number generating and language generating devices, have been discussed in Zhang, Pan, and Păun (2015), Zhang, Wang, and Pan (2009), respectively. A nerve cell consists of dendrites, somata, axons, and synapses. Each has one or more dendrites, which receive the stimulus and transmit excitement to somata, but only one axon that transmits excitement between somata. Therefore, we generally believe that dendrites simply transmit to somata the electrical impulses received from the synapses. Thus, as in SNP systems or spiking neural networks, neurons are viewed as information processors, while dendrites (and axons) are regarded as transmission channels. However, the conclusion that the dendrites only passively transmit the current to somata has not been confirmed by experiments. Moore et al. (2017) recently indicated that the dendrites are not just a passive channel. Their research shows that: (i) dendrites have an electrical activity, and the generated spike is 10 times one produced by soma; and (ii) dendrites perform a mixed computation of analog and digital signals. In our work, dendrites are abstracted as information processors, while neurons (somata) degenerate into storage units. Some new biological features of dendrites, such as dendritic feedback and delay, have been proven experimentally (London & Hausser,2005). It has usually been thought that information in the nervous system travels in one direction, from dendrites to somata, and then to axons. However, for many types of neurons, the presence of excitable ionic currents in dendrites supports dendritic action potentials that are transmitted in the opposite direction, from somata to dendrites (Stuart, Spruston, Sakmann, & Hausser,1997). This backpropagation implies that the neuron possesses an internal feedback mechanism, and the interaction between dendritic responses and somatic spikes can be abstracted computationally. In this work, the dendritic feedback mechanism is abstracted to develop a new kind of firing rule, called a dendrite rule, of the form (E1,E2, . . . , Es)/ap←(ac1,ac2, . . . , acs), whose firing condition is controlled by its prepositive (source) neurons. The control idea potentially reflects the feedback mechanism of the dendrites. We propose a new model of neural-like P systems, dendrite P (DeP) systems, which consist of several neurons in a directed graph to form a distributed and parallel computing system. DeP systems and SNP systems (and SNP systems with rules on synapses) differ in three aspects: (1) The neurons in DeP systems simulate the information processing mechanism of dendrites instead of that of original neurons or synapses. However, original neurons are used only as storage units in DeP systems. Thus the working mechanism of neurons in DeP systems is a ‘‘firing-storing process’’, i.e., the spikes in prepositive neurons of a neuron can be handled by its dendrite rule, and then the generated spikes are stored in the neuron. Conversely, as mentioned above, SNP systems (and SNP systems with rules on synapses) adopt a ‘‘storing–firing process’’. (2) In DeP systems, dendrite rules potentially reflect the feedback mechanism of dendrites. Therefore, the firing condition of each dendrite rule only depends on states of prepositive neurons of the neuron where the rule resides, and it is irrelevant to the state of the neuron itself. However, in SNP systems (and SNP systems with rules on synapses), the firing condition of the usual firing rule depends only on the state of the neuron where the rule resides, and is unrelated to the states of other neurons. (3) Since a dendrite rule has several regular expressions, the firing of the neuron where the rule resides is controlled by multiple prepositive neurons. Therefore, dendrite rules provide a collaborative control capability for DeP systems, i.e., the collaborative firing mechanism of several prepositive neurons. However, SNP systems and those with rules on synapses lack the collaborative mechanism. Intuitively, DeP systems provide a stronger control condition and processing ability and are potentially suitable for solving some real-life problems. Turing-universality of DeP systems as function computing and number generating/accepting devices is discussed. The proposed DeP systems are defined in Section 2, and an illustrative example and a comparative example are provided. Universality of DeP systems as number generating/accepting and function computing devices is proven in Section 3. Conclusions and discussion are drawn in Section 4. 2. Dendrite P systems In this section, DeP systems are introduced, and then illustrative and comparative examples are provided. The notations and terms similar to those used in SNP systems will be adopted for clarity and ease of understanding. 2.1. Definition Definition 1. A dendrite P (DeP) system with degree m≥1 is a construct, Π=(O, σ1, σ2, . . . , σm,syn,in,out), where: (1) O= {a}is the singleton alphabet (symbol ais known as the spike); (2) σ1, . . . , σmdenote mneurons with the form σi=(ni,Ri), 1≤i≤m, where (a) ni≥0 is the initial number of spikes in neuron σi; (b) Ridenotes the finite set of dendrite rules with the form (E1,E2, . . . , Es)/ap←(ac1,ac2, . . . , acs) where Ejis a regular expression, 1 ≤j≤s,p≥0, and sindicates the number of prepositive (source) neurons of neuron σi; (3) syn ⊆ {1,2, . . . , m} × {1,2, . . . , m}with i= jfor all (i,j)∈syn, 1 ≤i,j≤m(synapses); (4) in and out distinguish input and output neurons, respectively, of the system. As mentioned above, each neuron in SNP systems has two components, data and rules, as shown in Fig. 1(a), where andenotes the data (or state) of a neuron and Riis the set of firing rules. Since any neuron in an SNP system performs a ‘‘storing-firing process’’ (i.e., the received spikes are first integrated and stored, and then the neuron fires by some rule), it can also be understood in the form shown in Fig. 1(b). In contrast, in DeP systems, dendrites are viewed as information processors (characterized by dendrite rules) and neurons are degraded as storages, while synapses only reflect the connection relationships between neurons. Therefore, any neuron in a DeP system can be illustrated as in Fig. 1(c) and (d). In DeP systems, each neuron performs a ‘‘firing-storing process’’: the spikes in the corresponding prepositive neurons are handled first by dendrite rules, and then the generated spikes are stored in the neuron. Fig. 1. Comparison of SNP and DeP systems. (a) and (b): neurons in SNP systems; (c) and (d): neurons in DeP systems. From a topological perspective, a DeP system is expressed by a directed graph, where the nodes are the neurons and the edges correspond to the synapses. DeP systems differ significantly from SNP systems in the use of dendrite rules of the form (E1,E2,...,Es)/ap←(ac1,ac2,...,acs). Note that firing rules in SNP systems are of the form E/ac→ap, called usual firing rules in this work. In usual firing rules, the left part of a firing rule indicates the content (consuming of spikes) in the neuron where the rule resides, while the right part corresponds to other (target) neurons. Since the neuron where a dendrite rule resides is its target, the dendrite rule uses the left arrow ‘‘←’’ instead of the usual right arrow ‘‘→’’. In dendrite rules, the right part of the arrow ‘‘←’’ indicates the consuming of spikes in its source neurons. A neuron connects to several prepositive (source) neurons via its dendrite. Therefore, each dendrite rule has a group of regular expressions, (E1,E2,...,Es). Thus dendrite rules can be written as: (E1∧E2∧ · · · ∧ Es)/ap←(ac1,ac2,...,acs). Note that the firing condition is given in the form of its prepositive (source) neurons. The firing condition can be expressed in a conjunction form, (an1∈L(E1)) ∧(an2∈L(E2)) ∧ · · · ∧ (ans∈L(Es)), where njis the number of spikes in the ith prepositive neuron, 1 ≤j≤s. For neuron σi, if the firing condition for all of its prepositive (source) neurons is satisfied, then the dendrite rule can be applied, where cjspikes in the jth prepositive (source) neuron are consumed (1 ≤j≤s) and pspikes are produced and stored in the neuron where the rule resides. In dendrite rules, if ci=0 (or p=0), then aci(or ap) can be written as λ. Note that in any neuron, two dendrite rules such as (E11,E21, . . . , Es1)/ap1←(ac11 ,ac21 , . . . , acs1) and (E12,E22, . . . , Es2)/ap2← (ac12 ,ac22 , . . . , acs2) may have that (an1∈L(E11))∧(an2∈L(E21))∧ · · · ∧ (ans∈L(Es1)) and (an1∈L(E12)) ∧(an2∈L(E22)) ∧ · · · ∧ (ans∈ L(Es2)), i.e., the firing conditions of the two rules are true. In this case, we choose one of them nondeterministically. There is also the interesting case that dendrite rules in different neurons share one or more prepositive (source) neurons. For example, suppose that two rules, (E1i,E2i, . . . , Esi)/api←(ac1i,ac2i, . . . , acsi ) and (E1j,E2j, . . . , Etj)/apj←(ac1j,ac2j, . . . , actj ), from neurons σi and σj, respectively, can be applied simultaneously and share a prepositive (source) neuron σk. If the number of spikes nkin neuron σksatisfies max{cki,ckj} ≤ nk<cki +ckj, then this brings a conflict. In this case, one of the rules is nondeterministically chosen and applied. As usual, neurons in the system work with each other in parallel, but the dendrite rules in each neuron are applied in sequential way. The configuration of the system at time tis characterized by the number of spikes stored in each neuron, i.e., Ct=(n1(t),n2(t), . . . , nm(t)), so the initial configuration is denoted by C0=(n1(0),n2(0), . . . , nm(0)) =(n1,n2, . . . , nm). The transition between configurations can be defined using dendrite rules. A computation is any sequence of transitions starts from the initial configuration. The computation halts if a configuration is reached for which no rule can be applied. The output of a DeP system is a spike train exported by the output neuron. However, each neuron in a DeP system only stores the received spikes and does not send out spikes in a forward direction. To facilitate the discussion of universality, we assume that the spike train in a DeP system is received by the output neuron instead of the environment. Under this assumption, a spike train is expressed by a binary sequence of 1 and 0: we write 1 if the output neuron receives a spike, and 0 if no spike is received. Thus the number of spikes received by the output neuron is the computation result. The set of numbers computed by Πis denoted by Ngen(Π), where the subscript gen means that the system works in the generating mode. The family of all of the sets Ngen(Π) generated by DeP systems containing at most mneurons and at most nrules in every neuron is denoted by NgenDePn m. A DeP system can work in the accepting mode, where an input neuron is used to receive the spikes from the environment but the system has no output neuron. The system receives a spike train from the environment, and then it introduces the number n in a specified neuron in the form of 2nspikes. It is said that the number nis accepted by the system when the computation halts. Denote by Nacc (Π) the set of numbers accepted by the system Π, where acc indicates that the system works in the accepting mode. Denote by Nacc DePn mthe family of all of the sets Nacc (Π) accepted by DeP systems containing at most mneurons and at most nrules in every neuron. Remark 1. In DeP systems, the constraint p≤c1+c2+· · ·+csis relaxed for dendrite rules. Thus, for a dendrite rule, the number of generated spikes may be greater than the sum of the consumed spikes. The main reason for relaxing the constraint is to ensure that each module in the proof of universality can supply enough spikes. This is different from the usual firing rules in SNP systems, and is limited to the study of universality. 2.2. An illustrative example Fig. 2 shows a simple dendrite P system consisting of four neurons. Initially, four spikes and two spikes are placed in neurons σ1and σ2, respectively. Thus the initial configuration is C0=(4,2,0,0). Note that no rules can be applied in neuron σ4. Since neuron σ1has four spikes and neuron σ2has two spikes, two rules, (a4,a2)/a2←(a2,a2) and (a4,a2)/a← (a2,a), can be applied in neuron σ3at the same time, thus one is nondeterministically chosen and applied. There are two cases: (1) If rule (a4,a2)/a2←(a2,a2) is chosen, then two spikes are consumed in neuron σ1, two spikes are consumed in neuron σ2, and two spikes are generated by the dendrite rule and stored in neuron σ3. At this time, C1=(2,0,2,0). Since neuron σ3has two spikes and neuron σ2has none, rule (λ, a2)/a←(λ, a) can be applied in neuron σ4. Applying this rule, a spike in neuron σ3is removed and a spike is generated and stored in neuron σ4. Therefore, C2=(2,0,1,1). Since no rules can be applied, the system halts. (2) If rule (a4,a2)/a←(a2,a) is chosen, then two spikes are consumed in neuron σ1, a spike is consumed in neuron σ2, and a spike is produced and stored in neuron σ3. Hence C1=(2,1,1,0). Because there are two spikes in neuron σ1 and a spike in neuron σ2, rule (a2,a)/a←(a2,a) in neuron σ3can be applied. At the same time, a spike in neuron σ2 and a spike in neuron σ3mean that rule (a,a)/a←(a,a) in neuron σ4can also be applied. As a result, a conflict arises because only one spike is in neuron σ2. Therefore, one rule is chosen nondeterministically. There are two cases: (a) If rule (a2,a)/a←(a2,a) in neuron σ3is chosen, then two spikes are consumed in neuron σ1, a spike is consumed in neuron σ2, and a spike is produced and Fig. 2. A dendrite P system. stored in neuron σ3. Thus, neuron σ3contains three spikes. At this time, C2=(0,0,3,0) and the system halts. (b) If rule (a,a)/a←(a,a) in neuron σ4is chosen, then a spike is removed from neuron σ2, a spike is removed from neuron σ3, and a spike is produced and stored in neuron σ4. Thus C2=(2,0,0,1) and the system halts. It can be seen from the example that there are two cases of choosing the rule nondeterministically: (i) as usual in SNP systems, if several rules can be applied in a neuron at the same time, then one is nondeterministically chosen; and (ii) in the conflict case, one of the conflict rules in different neurons is nondeterministically chosen. 2.3. Compared with other variants To identify the differences between DeP systems and existing variants, an example is provided to compare DeP systems with SNP systems, SNP systems with multiple channels and SNP systems with rules on synapses. Figs. 3 and 4show the example, where each system has three neurons, σ1,σ2and σ3. We consider two cases. Case 1: Assume that in each system, neurons σ1and σ2respectively have three and two initial spikes. For a DeP system, with three spikes in neuron σ1and two spikes in neuron σ2, dendrite rule (a3,a2)/a2←(a3,a2) can be applied. Thus two spikes are produced and stored in neuron σ3. For an SNP system with rules on synapses, with three spikes in neuron σ1, rule a3/a3→a2is applied to send two spikes to neuron σ3, and with two spikes in neuron σ2, rule a2/a2→a2is applied to send two spikes to neuron σ3. Hence, neuron σ3receives four spikes. For an SNP system, since neuron σ1contains three spikes and neuron σ2contains two spikes, rules a3/a3→a2and a2/a2→a2are applied to send two spikes to neuron σ3. Hence, neuron σ3contains four spikes. For an SNP system with multiple channels, neurons σ1and σ2each send two spikes to neuron σ3 via channel (1). Hence, neuron σ3has four spikes. (See Fig. 3). Case 2: Assume that in each system, neurons σ1and σ2respectively have three and one initial spikes. For a DeP system, although neuron σ1has three spikes, neuron σ2 has only one spike, hence dendrite rule (a3,a2)/a2← (a3,a2) cannot be applied. Note that if neuron σ2later has a chance to receive a spike, then the dendrite rule will be applied. This means that neuron σ1waits for neuron σ2to work together. This indicates an interesting collaborative firing mechanism of neurons in DeP systems. Fig. 3. Four variants in Case 1: (a) DeP system; (b) SNP system with rules on synapses; (c) SNP system; (d) SNP system with multiple channels. Left side is in initial configuration, and right side is in final configuration. However, in each of the other three systems, with three spikes in neuron σ1, its rule is applied to send two spikes to neuron σ3, and since neuron σ2contains only one spike, it cannot fire. Therefore, neurons σ1and σ2cannot work collaboratively in SNP systems, SNP systems with multiple channels, and SNP systems with rules on synapses (see Fig. 4). From the above two cases, we can distinguish the following three distinguishable characteristics in DeP systems. (1) In DeP systems, the working mechanism of neurons can be described as a firing–storing process. (2) In DeP systems, the firing condition of each dendrite rule only depends on states of source neurons of the neuron where the rule resides, and is irrelevant to the state of the neuron where the rule resides. (3) DeP systems can provide a collaborative firing mechanism between several neurons. 3. Universality results We now investigate computational power of DeP systems as number generating/accepting devices, and discuss a small universal DeP system for computing functions. By simulating register machines, DeP systems can generate/accept all recursively enumerable sets of numbers (characterized by NRE) and compute all of the admissible enumerable sets of the unary partial recursive functions. A register machine can be denoted by M=(m,H,l0,lh,I), where mis the number of registers, His the set of instruction labels, Iis the set of instructions, l0is the start label, and lhis the halting label. Each label in Hcorresponds to an instruction in I. There are three forms of instructions: (1) li:(ADD(r),lj,lk) (add 1 to register rand then nondeterministically go to one of the instructions with labels lj, lk). (2) li:(SUB(r),lj,lk) (if register ris nonzero, then decrease it by 1 and go to the instruction with label lj; otherwise, go to the instruction with label lk). (3) lh:HALT (halting instruction). 3.1. Turing universality of DeP systems as number generating devices In the generating mode, a register machine can generate the number nin the following way. Initially, all registers are empty; the register machine starts from instruction l0, and then it applies instructions continuously; when it reaches the halting instruction, the number stored in the first register is regarded as its computation result. As we know, register machines can characterize the family NRE. Theorem 1. NgenDeP2 ∗=NRE. Proof. We must only prove that NRE ⊆NgenDeP2 ∗, since the converse is obvious (Păun,2002). For this purpose, we must simulate register machines in the generating mode based on the characterization of NRE. Without loss of generality, a register machine M=(m,H,l0,lh,I) is given, and for a halting configuration, all registers are empty apart from register 1. Moreover, register 1 is never decremented during the computation. A DeP system Π1is designed to simulate the register machine, containing three kinds of modules: ADD module simulating ADD instruction, shown in Fig. 5; SUB module simulating SUB instruction, shown in Fig. 6; a FIN module exporting the computation result, shown in Fig. 7. Suppose that each register rin Mcorresponds to a neuron σr in Π1, and the number in register ris coded: if register rstores Fig. 4. Four variants in Case 2: (a) DeP system; (b) SNP system with rules on synapses; (c) SNP system; (d) SNP system with multiple channels. Left side is in initial configuration, and right side is in final configuration. Fig. 5. Module ADD of Π1, simulating the ADD instruction li:(ADD(r),lj,lk). the number n≥0, then neuron σrcontains 2nspikes, vice versa. A neuron σlis associated with each instruction lin Hand some auxiliary neurons are considered in the modules. Initially, each auxiliary neuron has no spike, and neuron σl0receives a spike. When neuron σlireceives a spike, the system Π1starts to simulate the instruction li:(OP(r),lj,lk) (OP is an ADD or SUB operation). Starting from the activated li, the simulation handles neuron σras indicated by OP, and then one of neurons σljand σlkreceives a spike. The system accomplishes the simulation of register machine Monce neuron σlhreceives a spike. In the simulation, output neuron σout applies its dendrite rules to receive a series of spikes, and the computation result is the number of the received spikes, i.e., the number in register 1 in M. To explain that register machine Mcan be correctly simulated by system Π1, how the ADD and SUB modules simulate the ADD and SUB instructions respectively and how the FIN module exports the computation result will be discussed in detail. (1) Module ADD (shown in Fig. 5) — simulating an ADD instruction li:(ADD(r),lj,lk). To simulate the register machine, the system Π1starts from instruction l0(an ADD instruction). Suppose that an ADD instruction li:(ADD(r),lj,lk) is simulated at time t. Neuron σli Fig. 6. Module SUB of Π1,Π2, and Π3, simulating li:(SUB(r),lj,lk). Fig. 7. Module FIN of Π1, ending the computation. applies rule a/a3←ato receive a spike, hence three spikes are generated. With three spikes in neuron σli, rule a3/a←ain neurons σc1,σc2and σc3can be applied at time t+1. Consequently, the three neurons each receive a spike. Since neurons σc2and σc3 each have a spike, rule (a,a)/a2←(a,a) is applied at time t+2. Thus neuron σrreceives two spikes, indicating that register ris incremented by 1. Due to a spike in neuron σc1, rules a/a←ain σljand σlkcan be applied. Therefore, one of the rules in the two neurons is chosen nondeterministically. There are two cases: (1) At time t+2, if rule a/a←ain neuron σljis applied, then it receives a spike, indicating that the system Πstarts to simulate the instruction lj. (2) At time t+2, if rule a/a←ain neuron σlkis applied, then it receives a spike. With a spike in neuron σlk, the system Πstarts to simulate the instruction lk. Consequently, the ADD module correctly simulates the ADD instruction: starting from neuron σlireceiving a spike, the number of spikes stored in neuron σris added by 2, and then a spike is received nondeterministically by neurons σljor σlk. (2) Module SUB (shown in Fig. 6) — simulating a SUB instruction li:(SUB(r),lj,lk). Assume that a SUB instruction li:(SUB(r),lj,lk) is simulated at time t, and a spike is received by neuron σli(thus three spikes are generated by rule a/a3←a). Because there are three spikes in neuron σli, rule a3/a←ain neuron σrand rule a3/a←a2 in neuron σc1can be simultaneously applied at time t+1. Thus neurons σrand σc1each receive a spike. Based on the number of spikes in neuron σr, the following two cases are considered: (1) At time t+2, if neuron σrhas 2n+1 (n≥1) spikes (at this time, register rstores the number n), then rule (a(aa)+,a)/a←(a3,a) in neuron σc2can be applied, but rule (a,a)/a←(a,a) in neuron σc3cannot be applied. Thus three spikes are consumed in neuron σrand a spike is removed from neuron σc1, and simultaneously neuron σc2 receives a spike. At time t+3, neuron σljreceives a spike by its rule a/a←a, indicating that the system starts to simulate the instruction lj. (2) At time t+2, if neuron crcontains only one spike (at this time, no number exists in register r), then rule (a,a)/a← (a,a) in neuron σc3can be applied, but rule (a(aa)+,a)/a← (a3,a) in neuron σc2cannot be applied. The number of spikes contained in neuron σrbecomes 0 by the rule, and neuron σc3receives a spike. At time t+3, neuron σlk receives a spike by its rule a/a←a. Therefore, the system Πstarts to simulate the instruction lk. Therefore, the SUB module correctly simulates the SUB instruction: the system starts from neuron σlireceiving a spike, and it ends after neuron σljreceives a spike (if a number greater than zero is contained in register r) or neuron σlkreceives a spike (if register rhas no number). (3) Module FIN (shown in Fig. 7) — outputting the result of computation. Suppose now that at time t, neuron σlhreceives a spike, indicating that the register machine stops (i.e., the halting instruction lhis reached), and neuron σ1has 2nspikes (i.e., the number stored in register 1 is n). Because neuron σlhhas three spikes, rule a3/a←ain neuron σ1and rule a3/a←a2in neuron σc1are applied at time t+1. Neurons σ1and σc1each receive a spike. Thus the number of spikes contained in neuron σ1becomes odd. Because there is a spike in neuron σc1at time t+2, rule (a(aa)+,a)/a←(a2, λ) in neuron σout can be applied to receive a spike. At this time, two spikes are removed from neuron σ1 (meaning that the number in register 1 is reduced by 1), but no spike is consumed in neuron σc1. The process is repeated until only one spike is contained in neuronσ1, and neuron σout receives a spike each time. At time t+n+2, because only one spike is stored in neuron σ1and neuronσc1also has a spike, rule (a,a)/λ ←(a,a) in neuron σout is applied. Thus the spikes in neurons σ1and σc1are consumed. Consequently, from time t+2 to time t+n+1, neuron σout receives a total of nspikes, indicating the number in register 1 when the computation halts. According to our discussion of the modules, register machine Mis correctly simulated by DeP system Π1, where each neuron has at most two rules. Consequently, the theorem holds. □ 3.2. Turing universality of DeP systems as number-accepting devices Theorem 2. Nacc DeP2 ∗=NRE. Proof. A DeP system Π2is designed to simulate deterministic register machine M=(m,H,l0,lh,I) working in accepting mode. This proof will be accomplished by modifying the proof of Theorem 1. The system Π2includes the modules of three types: a deterministic ADD module, a SUB module, and an INPUT module. Fig. 8 shows the INPUT module. For convenience, the input spike train 10n−11 is recoded as 53n−15, where the digits ‘‘5’’ and ‘‘3’’ denote five spikes and three spikes, respectively, to be imported every time. Note that the interval between the first and second ‘‘5’’ spikes in the spike train can be determined by (n+1) −1=n, indicating that nis the number to be accepted. Fig. 8. The INPUT Module of Π2. Suppose that at time t, the first ‘‘5’’ spikes are received from the environment by neuron σin. At time t+1, rule a5/a2←a2in neuron σc1, rule a5/a2←a2in neuron σc2, and rule a5/a←ain neuron σc3are applied. Hence neurons σc2and σc1each receive two spikes and neuron σc3receives a spike. At this time, neuron σin receives the first ‘‘3’’ spikes. At time t+2, rule a3/a←ain neuron σc1, rule a3/a←ain neuron σc2, and rule a3/λ ←ain neuron σc3are applied. Thus neurons σc2and σc1each have three spikes, while neuron σc3still has only one spike. Moreover, neuron σin receives the second ‘‘3’’ spikes. At time t+3, since neurons σc1and σc2each have three spikes, neurons σc4and σc5each receive a spike from neurons σc2and σc1 by rule a3/a←a. Neurons σc2and σc1each receive a spike from neuron σin by rule a3/a←a. At this time, neuron σin receives the third ‘‘3’’ spikes. At time t+4, neuron σ1receives two spikes from neurons σc4and σc5by rule (a,a)/a2←(a,a). Neurons σc4and σc5each receive a spike from neurons σc2and σc1by rule a3/a←a. Each of neurons σc2and σc1receives a spike from neuron σin by rule a3/a←a. At this time, neuron σin receives the fourth ‘‘3’’ spikes. The process is repeated until neuron σin receives the second ‘‘5’’ spikes. At time t+n+2, neuron σin receives the second ‘‘5’’ spikes. At time t+n+3, rule a5/a2←a2in neuron σc1, rule a5/a2←a2in neuron σc2, and rule a5/a←ain neuron σc3are applied again, hence neurons σc2and σc1each contain four spikes and neuron σc3has two spikes. At time t+n+4, four spikes in neurons σc1and σc2are consumed by rule a4/λ ←a4in neurons σc4and σc5, and neuron σc6receives a spike from neuron σc3by rule a2/a←a2. At time t+n+5, neuron σl0receives a spike from neuron σc6, but the rule in neuron σ1cannot be applied since neurons σc4and σc5have no spike. Note that from time t+4 to time t+n+4, two spikes are received by neuron σ1each time. Therefore, 2nspikes are received in total by neuron σ1(meaning that the number of spikes in register 1 is n), and since a spike is received by neuron σl0, the system starts to simulate the initial instruction l0. For accepting mode, deterministic ADD instructions, of the form li:(ADD(r),lj), are used in the register machine, shown in Fig. 9. Assume that at time t, neuron σlireceives a spike by rule a/a3←a. Thus neuron σlihas three spikes. With three spikes in neuron σli, rule a3/a←acan be applied at time t+1 in neurons σc1,σc2, and σc3. Consequently, each of the three neurons Fig. 9. Module ADD of Π2and Π3, simulating li:(ADD(r),lj). receives a spike. Since neurons σc2and σc3each have a spike, rule (a,a)/a2←(a,a) is applied at time t+2. Hence two spikes are received by neuron σr. Because neuron σc1has a spike, rule a/a←ain neuron σljis applied to receive a spike. With a spike in neuron σlj, the system starts to simulate the instruction lj. Module SUB has not been changed (see Fig. 6). Module FIN is removed, but neuron σlhis kept in the system. With the receipt of a spike by neuron σlhregister machine Mattains instruction lh and stops. According to the discussion above, register machine is correctly simulated by DeP system Π2under accepting mode, where each neuron contains two rules at most. □ 3.3. Small universal DeP systems for computing functions We now design a small universal DeP system for computing functions. For computing the function f:Nk→N, a register machine M=(m,H,l0,lh,I) can work as follows: kinitial arguments are introduced into kspecial registers in the register machine (generally, the first two registers are adopted), and all other registers are set to be empty; the register machine starts from instruction l0, and then it works continually until it reaches halting instruction lh; the number stored in a special register rtis regarded as the computed value. Denote by (ϕ0, ϕ1, . . .) the fixed admissible enumeration of the unary partial recursive functions. If a recursive function gexists such that ϕx(y)=Mu(g(x),y) holds for all natural numbers x,y, then the register machine is called universal. Korec (1996) introduced a known small universal register machine for computing functions, denoted by Mu=(8,H,l0,lh,I). The register machine Muhas 23 instructions and 8 registers numbered from 0 to 7. By introducing two numbers g(x) and yinto registers 1 and 2, the register machine Mucan compute any ϕx(y); the number stored in register 0 is the computed function value when the register machine halts. A DeP system will be designed to simulate register machine Mu. For the sake of simplicity, the register machine Muis changed: a new register 8 is introduced, and original halting instruction is replaced with three instructions: l22 :(SUB(0),l23,lh);l23 :(ADD(8),l22);lh:HALT. Denote by M′ uthe modified version of Mu, shown in Fig. 10. Therefore, register machine M′ uhas nine registers, 25 labels, and 24 ADD and SUB instructions. Theorem 3. There exists a small universal DeP system having 115 neurons for computing functions. Proof. We design a DeP system Π3to simulate the universal register machine M′ u. The DeP system Π3consists of an INPUT module, an OUTPUT module, and ADD and SUB modules. The ADD and SUB modules are used to simulate the ADD and SUB instructions of M′ u, respectively. The INPUT module reads a spike Fig. 10. The universal register machine M′ u. Fig. 11. INPUT Module of Π3. train from the environment, while the OUTPUT module exports the computation result. When designing the DeP system Π3, each register rin M′ u is associated with a neuron σr, and if the number n≥0 is stored in register r, then 2nspikes are contained in neuron σr. Moreover, each instruction liin M′ uis associated with a neuron σli in Π3. If neuron σlireceives a spike, then it starts the simulation of instruction li. If neuron σlhcontains a spike, then the system Π3completely simulates the computation of M′ u. As a result, the number of spikes received by the output neuron σout is the result computed by M′ u(in register 8). Suppose that all of the auxiliary neurons in the initial configuration are empty. The INPUT module is shown in Fig. 11. For convenience, the input spike train 10g(x)10y1 is recoded as 53g(x)53y5, where the digits ‘‘5’’ and ‘‘3’’ respectively denote five spikes and three spikes to be imported each time. Note that neuron σ1has 2g(x) spikes and neuron σ2contains 2yspikes. Suppose that at time t1, neuron σin receives the first ‘‘5’’ spikes from the environment. Similar to the analysis of the INPUT module in the proof of Theorem 2, at time t1+1, rule a5/a2←a2 in neuron σc1, rule a5/a2←a2in neuron σc2, and rule a5/a←a in neuron σc3are applied, hence neurons σc2and σc1each receive Fig. 12. OUTPUT Module of Π3. two spikes and neuron σc3receives one spike. At this time, neuron σin receives the first ‘‘3’’ spikes. At time t1+2, rule a3/a←ain neuron σc1, rule a3/a←ain neuron σc2, and rule a3/λ ←ain neuron σc3are applied. Thus neurons σc2and σc1each contain three spikes, while neuron σc3contains only one spike. At time t1+3, because there are three spikes in neurons σc1and σc2, neurons σc4and σc6each receive a spike from neurons σc1and σc2 by rule a3/a←a. At time t1+4, neuron σ1receives two spikes from neurons σc4and σc6by rule (a,a)/a2←(a,a). The process is repeated until neuron σin receives the second ‘‘5’’ spikes. From time t1+4 to time t1+g(x)+4, 2g(x) spikes are received in total by neuron σ1(i.e., the number of spikes in register 1 is g(x)). Note that before time t1+g(x)+2, neuron σc3has only one spike. Suppose that the second ‘‘5’’ spikes are received by neuron σin at time t2(in fact, t2=t1+g(x)+1). Similarly, at time t2+1, rule a5/a2←a2in neuron σc1, rule a5/a2←a2in neuron σc2, and rule a5/a←ain neuron σc3are applied, hence neurons σc2 and σc1each have five spikes and neuron σc3has two spikes. At time t2+2, rule a3/a←ain neuron σc1, rule a3/a←ain neuron σc2, and rule a3/λ ←ain neuron σc3are applied. Thus neurons σc2and σc1each contain six spikes, while neuron σc3still has only two spikes. At time t2+3, with six spikes in neurons σc1and σc2, neurons σc5and σc7each receive a spike from neurons σc2and σc1 by rule a6/a←a. At time t2+4, neuron σ2receives two spikes from neurons σc5and σc7by rule (a,a)/a2←(a,a). The process is repeated until neuron σin receives the third ‘‘5’’ spikes. From time t2+4 to time t2+y+4, 2yspikes are received in total by neuron σ2(i.e., the number of spikes in register 2 is y). Note that at time t2+y+1, neuron σc1receives a spike from neuron σin, so it has three spikes. At time t2+y+1, rule a3/a←a3in neuron σc8is used to receive a spike. Then neuron σl0receives a spike, meaning that the system starts the simulation of initial instruction l0. From Fig. 10, we can observe that ADD instructions have the form li:(ADD(r),lj). Hence a deterministic ADD module can accomplish the simulation of the ADD instruction, as shown in Fig. 9. The working mechanism of the deterministic ADD module is illustrated in the proof of Theorem 2. The SUB module in Fig. 6 can complete the simulation of SUB instruction li:(SUB(r),lj,lk). The working principle of the SUB module is explained in the proof of Theorem 1. Suppose now that the register machine M′ uhalts, i.e., the instruction lharrives. Register 8 stores the computation result, which never decreases during the computation. The computation result will be exported by the OUTPUT module, as shown in Fig. 12. Assume now that neuron σlhreceives a spike at time t, indicating that M′ uhalts (that is, the halting instruction lhis reached), and neuron σ8has 2nspikes (i.e., the number nis contained in register 8). Since neuron σlhhas three spikes, rule a3/a←ain neuron σ8and rule a3/a←a2in neuron σc1are applied at time t+1. Neurons σ8and σc1each receive a spike. Thus the number of spikes in neuron σ8becomes odd. At time t+2, because there is a spike in neuron σc1, rule (a(aa)+,a)/a←(a2, λ) in neuron σout can be applied to receive a spike. At this time, two spikes are removed from neuron σ8(meaning that the number in register 8 is decreased by 1), but no spike is consumed in neuron σc1. The process is repeated until neuron σ8has only one spike, and neuron σout receives a spike each time. At time t+n+2, because each of neurons σ8and σc1has a spike, rule (a,a)/λ ←(a,a) in neuron σout is applied. Thus the spikes in neurons σ8and σc1are consumed. Consequently, from time t+2 to time t+n+1, n spikes are received in total by neuron σout , indicating exactly the number in register 8 when M′ uhalts. According to the discussion above, register machine M′ uis correctly simulated by DeP system Π3. In DeP system Π3, 115 neurons in total are used: (i) nine neurons for nine registers; (ii) 25 neurons for 25 instructions; (iii) 30 neurons for 10 ADD instructions; (iv) 42 neurons for 14 SUB instructions; (v) eight neurons for the INPUT module; (vi) one neuron for the OUTPUT module. □ 4. Conclusions and future work A new neural-like P system was investigated in this paper, called dendrite P (DeP) systems, abstracted by two characteristics of dendrites of nerve cells: (i) dendrites can perform mixed computations of analog and digital signals, and (ii) dendrites have the feedback characteristic. Based on the first characteristic, dendrites were regarded as information processors, while the second was used to develop a new kind of firing rules, dendrite rules. From the working mechanism, DeP systems differs from SNP systems in the following aspects: (1) Neurons in DeP systems use a firing–storing process, i.e., the spikes in prepositive neurons of each neuron are processed by its dendrite rules, and then the generated spikes are stored in the neuron. However, neurons in SNP systems adopt the opposite process, i.e., storing–firing process. (2) The firing condition of each dendrite rule depends on states of prepositive neurons of the neuron where the rule resides, and has nothing to do with the state of the neuron. However, in SNP systems, the firing condition of the usual firing rule depends only on the state of the neuron where the rule resides. (3) Due to multiple regular expressions of dendrite rules, DeP systems provide a collaborative control mechanism of several neurons. However, SNP systems (and SNP systems with rules on synapses) lack this mechanism. We proved that DeP systems can generate/accept any set of Turing-computable numbers, and constructed a small Turinguniversal DeP system of 115 neurons for computing functions. DeP systems seem to be more suitable for solving some reallife problems because of their collaborative control mechanism. Our future work will attempt to apply DeP systems to solve the problems, such as supervisory control problems in discrete event systems. In addition, DeP systems have the interesting feature: a conflict case exists in DeP systems when dendrite rules in different neurons share one or more prepositive (source) neurons. When discussing universality, the conflict case is processed by the nondeterministic choice strategy. However, the conflict case is potentially useful for some real-life applications, such as flexible manufacturing systems (FMSs), because the feature can be used to characterize the problems related to deadlock avoidance.