Research On Computational Property Of Spiking Neural P Systems

In the past few decades, the traditional computer processing power has been increased following the Moore's Law. As the CMOS linewidth of silicon-based microelectronic de-vices would develop to be less than lOnm, the growth of computer processing power would encounter many insurmountable technical obstacles, such as insulation materials, electrical connection technology, circuit printing technology, and so on. In addition, the manufactur-ing cost will be substantially increased. Nowadays, a frontier and hot issue in the field of computer science is to break through the framework of silicon-based devices, and to develop new computing models, algorithms and devices. Researches in this area include quantum computing, optical computing, biological computing, and so on. Membrane computing is a branch of biological computing, membrane computing models (also called P systems) are a class of distributed parallel computing models based on the structure and function of cells. Neurons are a special class of cells. The present work deals with spiking neural P systems based on neurons. By using analysis tools such as formal language, automata theory and discrete mathematics, several computational properties of spiking neural P systems are in-vestigated, they are small universality, homogeneousness, robustness, language generating power and the capability for arithmetic progression. The detailed contents of this disserta-tion are as follows:Looking for small universal computing devices is a natural and well investigated topic in computer science. In this work, small universality is investigated in spiking neural P systems when they work in synchronous manner and asynchronous manner, respectively. For spiking neural P systems working in synchronous manner, by using the states of neu-rons to store instructions, a universal system with a small number of neurons is produced, which greatly improves the previous results obtained by Paun et al. For spiking neural P systems working in asynchronous manner, a system is constructed for computing functions, the problem on how to input and output in asynchronous manner is considered. By analyz-ing and simplifying the instructions, the number of neurons used in the universal system is optimized. For spiking neural P systems, besides in computer science, small universality is also interesting in biology:a measure method of small universal "brain" is given.There are few types of neurons in biological nervous system, and all the neurons work in a similar way. Based on this biological background, homogeneous spiking neural P sys-tems are considered, where each neuron has the same set of rules. Such kind of spiking neural P systems is proved to be universal, both when using weighted synapses and using usual synapses (weight on all synapses is 1). The result is important in the following sense: the structure of a neural system is crucial for the functioning of the system. Although the individual neuron is simple and homogeneous, by cooperating with each other, a network of neurons can be powerful-"complete (Turing) creativity".Biological processes (reactions in neurons, transport of spikes) take uncertain times to be completed, which can also be influenced by many environmental factors. In order to establish robust systems against the environmental factors, a special class of spiking neural P systems, called time-free spiking neural P systems, is introduced, which always produce the same computation result independently from the execution times of the rules. The number generating power of this restrictive variant is investigated. A special signalling mechanism was proposed to control the work of neurons. By using this mechanism, time-free spiking neural P systems with extended rules can generate the length sets of recursively enumerable languages. If the number of spikes present in the system is bounded, then a characterization of semilinear sets of natural numbers is obtained. This research provides as a theoretical basis of the establishment of robust spiking neural P systems.One of the central problems on investigating the computational power of computing devices is to consider their language generative power. This work investigates the language generative power of a special class of spiking neural P systems, where thresholds are used as the firing condition of neurons. The relationships between the language generated by this kind of spiking neural P system and finite language and regular languages are discussed. An important result obtained in this work is as follows:for an arbitrarily polynary alphabet, a mapping from binary alphabet{0,1}to the polynary alphabet is designed, under this mapping spiking neural P systems with thresholds can characterize recursively enumerable languages. The meaning of this result is as follows:when the thresholds, instead of regular expressions, are used as the firing condition of neurons, spiking neural P systems still have the same language generative power.The problem of performing arithmetic operation on spiking neural P system is consid-ered. Three family of spiking neural P systems are constructed for dealing with the addition of n natural numbers, the multiplication of 2 natural numbers and division of a natural num-ber with a fixed divisor. The numbers introduced in these systems are provided in binary form, encoded as appropriate sequences of spikes, and the computing result emitted by the output neuron is also of binary form. This work provides an answer to an open problem formulated by Gutierrez-Naranjo and Leporati, it also provides as the theoretical basis of the design of a CPU based on the working of spiking neural P systems.Matrices are used to represent spiking neural P systems:configuration vectors are defined to monitor the number of spikes in each neuron; transition net gain vectors are introduced to quantify the total amount of spikes consumed and received every step. Nondeterminism of the systems is assured by a set of spiking transition vectors that could be used at any given time during the computation. With such matrix representation, it is quite convenient to determine the next configuration from a given configuration, since it involves only multiplication and addition of matrices.