Asynchronous Spiking Neural P Systems: Decidability and Undecidability

Matteo Cavaliere, Ömer Egecioglu, Oscar H. Ibarra, Mihai Ionescu, Gheorghe Paun, Sara Woodworth

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

In search for “realistic” bio-inspired computing models, we consider asynchronous spiking neural P systems, in the hope to get a class of computing devices with decidable properties. However, although the non-synchronization is known in general to decrease the computing power, in the case of using extended rules (several spikes can be produced by a rule) we obtain again the equivalence with Turing machines (interpreted as generators of sets of vectors of numbers). The problem remains open for the case of restricted spiking neural P systems, whose rules can only produce one spike. On the other hand, we prove that asynchronous spiking neural P systems, with a specific way of halting, using extended rules and where each neuron is either bounded or unbounded, are equivalent to partially blind counter machines and, therefore, have many decidable properties.
Original languageEnglish
Title of host publicationDNA Computing
Subtitle of host publication13th International Meeting on DNA Computing, DNA13, Memphis, TN, USA, June 4-8, 2007, Revised Selected Papers
PublisherSpringer
Pages246-255
Number of pages10
Volume4858
ISBN (Electronic)978-3-540-77962-9
ISBN (Print)978-3-540-77961-2
DOIs
Publication statusPublished - 2007

Fingerprint

Dive into the research topics of 'Asynchronous Spiking Neural P Systems: Decidability and Undecidability'. Together they form a unique fingerprint.

Cite this