Computations in spiking neural P systems simulations and structural plasticity - Cabarle, Francis George Carreon (College of Engineering, University of the Philippines Diliman, 2015)
Spiking neural P systems (in short, SNP systems) are parallel, distributed, synchronous, and nondeterministic models of computation. SNP systems are membrane models within the membrane computing area (a branch of the larger natural computing area) initiated by Gheorghe Paun in 1998. SNP systems are inspired by the structure and function of spiking neurons, which compute using indistinct signals called spikes. Neurons are spike processors which are placed on the nodes of a directed graph, where the directed edges between neurons are called synapses. In this work, the neuroscience feature of structural plasticity is introduced into the SNP systems framework. The computing power of SNP systems with structural plasticity (in short, SNPSP systems) are investigated by simulating other models of computation, e.g. linear grammars, register machines. SNPSP systems are SNP systems that can create or delete synapses: they have a dynamical structure applied only to the synapses. We prove the computational (non)universality of SNPSP systems in several semantics, i.e. depending on how the system applies rules. Two of these semantics include the usual parallel and synchronous semantic, and a modification of this semantic called spike saving mode. The remaining semantics include two restrictions: removing either synchronization (i.e. asynchronous operation) or parallelism (i.e. sequential operation. We prove that such restricted SNPSP systems can still achieve universality. All universality results in this work apply to SNPSP systems as number generators or acceptors. In SNPSP systems, the plasticity rules used provide a new source of nondeterminism when selecting which synapses to create or delete. Plasticity rules also provide a "programming capacity" that could, at certain cases, replace two common rule types in SNP systems: forgetting rules (rules that remove but do not produce spikes) and rules with delays (a time delay takes effect prior to spike productions). This nondeterminism source and capacity also allow SNPSP systems to have normal forms, which are a set of simplifying restrictions on system parameters, e.g. number of types of rules inside a neuron. We provide uniform modules of sequential SNPSP systems, i.e. the system construction is independent from the simulated register machine, providing some hint to an open problem on uniform modules of sequential SNP systems. The asynchronous SNPSP systems in this work provide support to the conjecture that asynchronous SNP systems with standard rules (each step, each neuron produces at most one spike) are not universal. Lastly, semi-uniform (i.e. system construction is based on the problem instance) and uniform solution, both nondeterministic and under a normal form, to the NP-complete problem Subset Sum are provided. The uniform solution reduces the number of neurons by a linear amount (with respect to the input size) as compared to a previous uniform solution using SNP systems.