Biological neurons communicate via spike-trains, i.e. via sequences of stereotyped pulses (``spikes'') that encode information in their time-differences (``temporal coding''). In addition it is wellknown that biological neurons are quite ``noisy'', i.e. the precise times when they ``fire'' (and thereby issue a spike) depend not only on the incoming spike-trains, but also on various types of ``noise''.
It has remained unknown whether one can in principle carry out reliable digital computations with noisy spiking neurons. This article presents rigorous constructions for simulating in real-time arbitrary given boolean circuits and finite automata with arbitrarily high reliability by networks of noisy spiking neurons.
In addition we show that with the help of ``shunting inhibition'' such networks can simulate in real-time any McCulloch-Pitts neuron (or ``threshold gate''), and therefore any multilayer perceptron (or ``threshold circuit'') in a reliable manner. These constructions provide a possible explanation for the fact that biological neural systems can carry out quite complex computations within 100 msec.
It turns out that the assumption that these constructions require about the shape of the EPSP's and the behaviour of the noise are surprisingly weak.