On The Computational Power Of Neural Nets

This paper deals with the simulation of Turing machines by neural networks. Such networks are made up of interconnections of synchronously evolving processors, each of which updates its state according to a "sigmoidal" linear combination of the previous states of all units. The main result states that one may simulate all Turing machines by nets, in linear time. In particular, it is possible to give a net made up of about 1,000 processors which computes a universal partial-recursive function. (This is an update of Report SYCON-91-08; new results include the simulation in linear time of binary-tape machines, as opposed to the unary alphabets used in the previous version.) Key words: neural networks, Turing machines Research supported in part by US Air Force Grant AFOSR-91-0343. Rutgers Center for Systems and Control November ON THE COMPUTATIONAL POWER OF NEURAL NETS 3 Hava T. Siegelmann, Department of Computer Science Eduardo D. Sontag, Department of Mathematics Rutgers University..