On the computational power of neural nets

ABSTRACT

This paper deals with finite networks which consist of interconnections of synchronously evolving processors. Each processor updates its state by applying a “sigmoidal” scalar nonlinearity to a linear combination of the previous states of all units. We prove that one may simulate all Turing Machines by rational nets. In particular, one can do this in linear time, and there is a net made up of about 1,000 processors which computes a universal partial-recursive function. Products (high order nets) are not required, contrary to what had been stated in the literature. Furthermore, we assert a similar theorem about non-deterministic Turing Machines. Consequences for undecidability and complexity issues about nets are discussed too.

REFERENCES

• 1: Noga Alon , A. K. Dewdney , Teunis J. Ott, Efficient simulation of finite automata by neural nets, Journal of the ACM (JACM), v.38 n.2, p.495-514, April 1991 [doi>10.1145/103516.103523]
• 2: Jean Berstel, Jr. , Christophe Reutenauer, Rational series and their languages, Springer-Verlag New York, Inc., New York, NY, 1988
• 3: L, Blum, M. Shub, and S. Smale, "On a theory of computation and complexity over the real numbers: NP completeness, recursive functions, and universal machines," Bull. A.M.S. 21(1989): 1-46.
• 4: S. Franklin, M. Garzon, "Neural computability," in Progress In Neural Networks, Vol 1)(O. M. Omidvat, ed.), Ablex, Norwood, NJ, (1990): 128-144.
• 5: M. Garzon, S. Franklin, "Neural computability II," in Proc. 3rd Int. Joint Conf. Neural Networks (1989): I, 631-637.
• 6: C.L. Giles, D. Chen, C.B. Miller, H.H. Chen, G.Z. Sun, Y.C. Lee, "Second-order recurrent neural networks for grammatical inference," Proceedings of the International Joint Conference on Neural Networks, Seattle, Washington, IEEE Publication, col. 2 (1991): 273-278.
• 7: R. I-Iartley, H. Szu, "A comparison of the computational power of neural network models," in Proc. IEEE Conf. Neural Networks (1987): III. 17-22.
• 8: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 9: S.C. Kleene, "Representation of events in nerve nets and finite automata," in Shannon, C.E., and J. McCarthy, eds., Automata Studies, Princeton Univ. Press 1956: 3-41.
• 10: Wolfgang Maass , Georg Schnitger , Eduardo D. Sontag, On the computational power of sigmoid versus boolean threshold circuits (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.767-776, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185447]
• 11: C.M. Marcus, tLM. Westervelt, "Dynamics of iterated-map neural networks," Phys. Rev. Ser. A 40(1989): 3355-3364.
• 12: W.S. McCulloch, W. Pitts, "A logical calculus of the ideas immanent in nervous activity," Bull. Math. Biophys. 5(1943): 115-133.
• 13: Marvin Lee Minsky, Computation: Finite and Infinite Machines, Prentice-Hall, Inc., Upper Saddle River, NJ, 1967
• 14: J.B. Pollack, On Connectionist Models of Natural Language Processing, Ph.D. Dissertation, Computer Science Dept, Univ. of Illinois, Urbana, 1987.
• 15: J.H. Reif, J.D. Tygar, A. Yoshida "The computability and complexity of optical beam tracing," Proe. of the 31st Annual Syrup. on Foundations of Computer Science (1990): 106-114.
• 16: R. Schwarzschild, E.D. Sontag, "Algebraic theory of sign-linear systems," in Proceedings of the Automatic Control Conference, Boston, MA, June (1991): 799-804.
• 17: C.E. S annon, ~ universal turing machine with two internal states," in Shannon, C.E., and J. Mc- Carthy, eds., Automata Studies, Princeton Univ. Press 1956: 157-165.
• 18: H.T. Siegelmann, E.D. Sontag, "Analog computation, neural networks, and circuits," submitted.
• 19: Eduardo D. Sontag, Mathematical control theory: deterministic systems, Springer-Verlag New York, Inc., New York, NY, 1990
• 20: Eduardo D. Sontag, Feedforward nets for interpolation and classification, Journal of Computer and System Sciences, v.45 n.1, p.20-48, Aug. 1992 [doi>10.1016/0022-0000(92)90039-L]
• 21: G.Z. Sun, H.H. Chen, Y.C. Lee, and C.L. Giles, "Turing equivalence of neural networks with second order connection weights," in Int. Jt. Conf. Neural Nets, Seattle, 1991:II,357-.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Connectionism and neural nets

General Terms:
Theory, Verification