It is shown that there is no standard spiking neural P system that simulates Turing machines with less than exponential time and space overheads. The spiking neural P systems considered here have a constant number of neurons that is independent of the input length. Following this we construct a universal spiking neural P system with exhaustive use of rules that simulates Turing machines in polynomial time and has only 18 neurons.
展开▼
