Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Cavaliere, M., Egecioglu, O., Ibarra, O.H., Woodworth, S., Ionescu, M., Păun, Gh.: Asynchronous spiking neural P systems. Tech. Report 9/2007 Microsoft Research - University of Trento, Centre for Computational and Systems Biology, http://www.cosbi.eu
Chen, H., Ionescu, M., Ishdorj, T.-O., Păun, A., Păun, Gh., Pérez-Jiménez, M.J.: Spiking neural P systems with extended rules: Universality and languages, Natural Computing (special issue devoted to DNA12 Conf.) (to appear)
Gutiérrez-Naranjo, M.A., et al.: Proceedings of Fifth Brainstorming Week on Membrane Computing, Fenix Editora, Sevilla (in press, 2007)
Ibarra, O.H., Păun, A., Păun, Gh., Rodríguez-Patón, A., Sosik, P., Woodworth, S.: Normal forms for spiking neural P systems. Theoretical Computer Sci. (to appear)
Ionescu, M., Păun, A., Păun, Gh., Pérez-Jiménez, M.J.: Computing with spiking neural P systems: Traces and small universal systems. In: Mao, C., Yokomori, T., Zhang, B.-T. (eds.) DNA Computing. LNCS, vol. 4287, pp. 32–42. Springer, Heidelberg (2006)
Ionescu, M., Păun, Gh., Yokomori, T.: Spiking neural P systems. Fundamenta Informaticae 71(2-3), 279–308 (2006)
Ionescu, M., Păun, Gh., Yokomori, T.: Spiking neural P systems with exhaustive use of rules. Intern. J. of Unconventional Computing (to appear)
Maass, W., Bishop, C. (eds.): Pulsed Neural Networks. MIT Press, Cambridge (1999)
Minsky, M.: Computation – Finite and Infinite Machines. Prentice-Hall, Englewood Cliffs (1967)
Păun, Gh.: Membrane Computing – An Introduction. Springer, Berlin (2002)
Păun, Gh.: Introduction to membrane computing. In: Ciobanu, G., Păun, Gh., Pérez-Jiménez, M.J. (eds.) Applications of Membrane Computing, Springer, Heidelberg (2006)
The P Systems Web Page, http://psystems.disco.unimib.it
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cavaliere, M., Egecioglu, O., Ibarra, O.H., Ionescu, M., Păun, G., Woodworth, S. (2008). Asynchronous Spiking Neural P Systems: Decidability and Undecidability. In: Garzon, M.H., Yan, H. (eds) DNA Computing. DNA 2007. Lecture Notes in Computer Science, vol 4848. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-77962-9_26
Download citation
DOI: https://doi.org/10.1007/978-3-540-77962-9_26
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-77961-2
Online ISBN: 978-3-540-77962-9
eBook Packages: Computer ScienceComputer Science (R0)