On the Computational Power of Asynchronous Axon Membrane Systems

Axon membrane systems, also called axon P systems, are a group of neuron system inspired neural computing devices. The system are designed by the mimic of the way axon (connecting neurons in central nerves systems) processing impulse signals passing along it. In the systems, all the 'computing units' are aligned one after another along the axon, achieving a linear topological structure. It was known that synchronous axon P systems can compute the families of Turing computable sets of both natural numbers and recursive functions. However, the computational power of asynchronous axon P systems is still open. In this paper, we investigate the computational power of asynchronous axon P systems, where the nonsynchronization is induced by either the node's asynchronously spiking (working in asynchronous mode) or the randomly assigned time consumption for each time spiking of the nodes (working in time-free mode). As results, it is proved that axon P systems working in either asynchronous or time-free mode are Turing universal as number generators, which indicates that the nonsynchronization will not reduce the computation power of axon P systems. It is worth noting that it needs $O(n)$ spikes to encode natural number $n$ in asynchronous axon P systems, but it needs $O(n^2)$ spikes in Turing universal synchronous axon P systems. These results partially answer an open problem left in [IEEE NNLS 26(11): 2816-29, 2015], and may also provide some hints on designing novel learning strategies by imposing computation tasks on the synapses of neural networks models.