Title: A Boundary between Universality and Non-universality in Extended Spiking Neural P Systems
Abstract: We solve the problem of finding the smallest possible universal spiking neural P system with extended rules. We give a universal spiking neural P system with extended rules and only 4 neurons. This is the smallest possible universal system of its kind. We prove this by showing that the set of problems solved by spiking neural P systems with 3 neurons is bounded above by NL, and so there exists no such universal system with 3 neurons (for any reasonable definition of universality). 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 is also the smallest possible universal system of its kind.
Publication Year: 2010
Publication Date: 2010-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 22
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot