|
NeuroCOLT
Technical Report NC-TR-94-021
On
the Computational Complexity of Networks of Spiking Neurons
Wolfgang
Maass
Institute for Theoretical Computer Science
Technische Universitaet Graz
Klosterwiesgasse 32/2
A-8010 Graz
Austria
Abstract
We investigate the computational power of a formal model for networks
of spiking neurons. It is shown that simple operations on phase-differences
between spike-trains provide a very powerful computational tool that
can in principle be used to carry out highly complex computations
on a small network of spiking neurons. We construct networks of spiking
neurons that simulate arbitrary threshold circuits, Turing machines,
and a certain type of random access machines with real valued inputs.
We also show that relatively weak basic assumptions about the response-
and threshold-functions of the spiking neurons are sufficient in order
to employ them for such computations. Furthermore we prove upper
bounds for the computational power of networks of spiking neurons
with arbitrary piecewise linear response-and threshold-functions,
and show that they are with regard to real-time simulations computationally
equivalent to a certain type of random access machine, and to recurrent
analog neural nets with piecewise linear activation functions. In
addition we give corresponding results for networks of spiking neurons
with a limited timing precision, and we prove upper and lower bounds
for the VC-dimension and pseudo-dimension of networks of spiking neurons.
Download Compressed
Postscript
|