Computer Science – Computational Complexity
Scientific paper
2009-12-04
Computer Science
Computational Complexity
Version 1 (arXiv:0912.0741v1) of this paper contained some technical errors that were mainly due to the restriction of counter
Scientific paper
In this work we offer a significant improvement on the previous smallest spiking neural P systems and solve the problem of finding the smallest possible extended spiking neural P system. Paun and Paun gave a universal spiking neural P system with 84 neurons and another that has extended rules with 49 neurons. Subsequently, Zhang et al. reduced the number of neurons used to give universality to 67 for spiking neural P systems and to 41 for the extended model. Here we give a small universal spiking neural P system that has only 17 neurons and another that has extended rules with 5 neurons. All of the above mentioned spiking neural P systems suffer from an exponential slow down when simulating Turing machines. Using a more relaxed encoding technique we get a universal spiking neural P system that has extended rules with only 4 neurons. This latter spiking neural P system simulates 2-counter machines in linear time and thus suffer from a double exponential time overhead when simulating Turing machines. We show that extended spiking neural P systems with 3 neurons are simulated by log-space bounded Turing machines, and so there exists no such universal system with 3 neurons. It immediately follows that our 4-neuron system is the smallest possible extended spiking neural P system that is universal. Finally, we show that if we generalise the output technique we can give a universal spiking neural P system with extended rules that has only 3 neurons. This system is also the smallest of its kind as a universal spiking neural P system with extended rules and generalised output is not possible with 2 neurons.
No associations
LandOfFree
A boundary between universality and non-universality in spiking neural P systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A boundary between universality and non-universality in spiking neural P systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A boundary between universality and non-universality in spiking neural P systems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-706285