Reversible spiking neural P systems

Abstract

Spiking neural (SN) P systems are a class of distributed parallel computing devices inspired by the way neurons communicate by means of spikes. In this work, we investigate reversibility in SN P systems, as well as the computing power of reversible SN P systems. Reversible SN P systems are proved to have Turing creativity, that is, they can compute any recursively enumerable set of non-negative integers by simulating universal reversible register machine.

Keywords

membrane computing / spiking neural P system / reversible computing model / universality / reversible register machine

References

[1] Landauer R. Irreversibility and heat generation in the computing process. IBM Journal of Research and Development, 1961, 5(3): 183-191

[2] Von Neumann J. Theory of self-reproducing automata. University of Illinois Press, 1966

[3] Bennett C. Logical reversibility of computation. IBM Journal of Research and Development, 1973, 17(6): 525-532

[4] Morita K, Yamaguchi Y. A universal reversible turing machine. In: Proceedings of the 5th International Conference on Machines, Computations, and Universality. 2007, 90-98

[5] Priese L. On a simple combinatorial structure sufficient for sublying nontrival self-reproduction. Journal of Cybernetics, 1976, 6: 101-137

[6] Fredkin E, Toffoli T. Conservative logic. International Journal of Theoretical Physics, 1982, 21(3): 219-253

[7] Toffoli T, Margolus N. Invertible cellular automata: a review. Physica D: Nonlinear Phenomena, 1990, 45(1): 229-253

[8] Morita K. Universality of a reversible two-counter machine. Theoretical Computer Science, 1996, 168(2): 303-320

[9] Leporati A, Zandron C, Mauri G. Reversible P systems to simulate fredkin circuits. Fundamenta Informaticae, 2006, 74(4): 529-548

[10] Alhazov A, Morita K. On reversibility and determinism in p systems. In: Proceedings of the 10th International Conference on Membrane Computing. 2009, 158-168

[11] Păaun G. Computing with membranes. Journal of Computer and System Sciences, 2000, 61(1): 108-143

[12] Ionescu M, Păun G, Yokomori T. Spiking neural P systems. Fundamenta informaticae, 2006, 71(2): 279-308

[13] Păun G, MARIO J, Rozenberg G. Spike trains in spiking neural P systems. International Journal of Foundations of Computer Science, 2006, 17(4): 975-1002

[14] Chen H, Freund R, Ionescu M, Pă un G, Pérez-Jiménez M. On string languages generated by spiking neural P systems. Fundamenta Informaticae, 2007, 75(1): 141-162

[15] Zhang X, Zeng X, Pan L. On string languages generated by spiking neural P systems with exhaustive use of rules. Natural Computing, 2008, 7(4): 535-549

[16] Păun A, Păun G. Small universal spiking neural P systems. BioSystems, 2007, 90(1): 48-60

[17] Pan L, Zeng X. Small universal spiking neural P systems working in exhaustive mode. IEEE Transactions on NanoBioscience, 2011, 10(2): 99-105

[18] Ishdorj T, Leporati A, Pan L, Zeng X, Zhang X. Deterministic solutions to QSAT and Q3SAT by spiking neural P systems with precomputed resources. Theoretical Computer Science, 2010, 411(25): 2345-2358

[19] Pan L, Păun G, Pérez-Jiménez M. Spiking neural P systems with neuron division and budding. Science China Information Sciences, 2011, 54(8): 1596-1607

[20] Zeng X, Zhang X, Pan L. Homogeneous spiking neural P systems. Fundamenta Informaticae, 2009, 97(1): 275-294

[21] Wang J, Hoogeboom H, Pan L, Paun G, Pérez-Jiménez M. Spiking neural P systems with weights. Neural Computation, 2010, 22(10): 2615-2646

[22] Pan L, Zeng X, Zhang X. Time-free spiking neural P systems. Neural Computation, 2011, 23(5): 1320-1342

[23] Pan L, Wang J, Hoogeboom H. Spiking neural P systems with astrocytes. Neural Computation, 2012, 24(3): 805-825

[24] Rozenberg G. Handbook of formal languages: word, language, grammar. Springer Verlag, 1997

[25] Păun G. Membrane computing: an introduction. Fundamentals of Computation Theory, 2003, 177-220

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg