- ▪H. T. Siegelmann, E.D. Sontag, "On the computational power of neural nets", J. Computer System Sciences, vol. 50, no. 1, pp. 132–150, 1995. doipdfmachine learning · analog computing · theory of computing · neural networks · computational complexity · super-Turing computation
Abstract
This paper deals with finite size networks which consist of interconnections of synchronously evolving processors. Each processor updates its state by applying a "sigmoidal" function to a rational-coefficient linear combination of the previous states of all units. We prove that one may simulate all Turing Machines by such nets. In particular, one can simulate any multi-stack Turing Machine in real time, and there is a net made up of 886 processors which computes a universal partial-recursive function. Products (high order nets) are not required, contrary to what had been stated in the literature. Non-deterministic Turing Machines can be simulated by non-deterministic rational nets, also in real time. The simulation result has many consequences regarding the decidability, or more generally the complexity, of questions about recursive nets.
- ▪H.T. Siegelmann, E.D. Sontag, "Analog computation via neural networks", In Proc.\ 2nd Israel Symposium on Theory of Computing and Systems (ISTCS93)\/, IEEE Computer Society Press, 1993, 1993.
- ▪H.T. Siegelmann, E.D. Sontag, "On the computational power of neural nets", In COLT '92: Proceedings of the fifth annual workshop on Computational learning theory, pp. 440–449, 1992. doi
- ▪H.T. Siegelmann, E.D. Sontag, "Some results on computing with neural nets", In Proc.\ IEEE Conf.\ Decision and Control, Tucson, Dec.\ 1992, IEEE Publications, 1992, pp. 1476–1481, 1992.