Massachusetts Institute of Technology Press, Neural Computation, 12(26), p. 2925-2943, 2014
DOI: 10.1162/neco_a_00665
Full text: Download
Spiking neural P systems (SN P systems) are a class of distributed parallel computing devices inspired by spiking neurons, where the spiking rules are usually used in a sequential way (an applicable rule is applied one time at a step) or an exhaustive way (an applicable rule is applied as many times as possible at a step). In this letter, we consider a generalized way of using spiking rules by “combining” the sequential way and the exhaustive way: if a rule is used at some step, then at that step, it can be applied any possible number of times, nondeterministically chosen. The computational power of SN P systems with a generalized use of rules is investigated. Specifically, we prove that SN P systems with a generalized use of rules consisting of one neuron can characterize finite sets of numbers. If the systems consist of two neurons, then the computational power of such systems can be greatly improved, but not beyond generating semilinear sets of numbers. SN P systems with a generalized use of rules consisting of three neurons are proved to generate at least a non-semilinear set of numbers. In the case of allowing enough neurons, SN P systems with a generalized use of rules are computationally complete. These results show that the number of neurons is crucial for SN P systems with a generalized use of rules to achieve a desired computational power.