Turing computability with neural nets. (English) Zbl 0749.68032
Summary: This paper shows the existence of a finite neural network, made up of sigmoidal neurons, which simulates a universal Turing machine. It is composed of less than \(10^ 5\) synchronously envolving processors, interconnected linearly. High-order connections are not required.
MSC:
| 68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |
References:
| [1] | Pollack, J. B., On connectionist models of natural language processing, (Ph.D. Dissertation (1987), Computer Science Dept, University of Illinois: Computer Science Dept, University of Illinois Urbana), (Available as MCCS-87-100, Computing Research Laboratory, NMSU, Las Cruces, NM) |
| [2] | Sun, G. Z.; Chen, H.-H.; Lee, Y.-C.; Giles, C. L., Turing equivalence of neural networks with second order connection weights, Proc. Int. Joint. Conf. Neural Networks (1991), Seattle |
| [3] | N. Alon, A.K. Dewdney and T.J. Ott, Efficient simulation of finite automata by neural nets, J.A.C.M.; N. Alon, A.K. Dewdney and T.J. Ott, Efficient simulation of finite automata by neural nets, J.A.C.M. · Zbl 0799.68138 |
| [4] | Franklin, S.; Garzon, M., Neural computability, (Omidvar, O. M., Progress In Neural Networks, Vol. 1 (1990), Ablex: Ablex Norwood, NJ), 128-144 |
| [5] | Marcus, C. M.; Westervelt, R. M., Dynamics of iterated-map neural networks, Phys. Rev. Ser. A, 40, 3355-3364 (1989) |
| [6] | Siegelmann, H. T.; Sontag, E. D., Neural nets are universal computing devices, (Report SYCON-91-08 (1991), Rutgers Center for Systems and Control, Rutgers University) |
| [7] | Berstel, J.; Reutenauer, C., Rational Systems and Their Languages (1988), Springer-Verlag: Springer-Verlag Berlin · Zbl 0668.68005 |
| [8] | Sontag, E. D., Mathematical Control Theory: Deterministic Finite Dimensional Systems (1990), Springer: Springer New York · Zbl 0703.93001 |
| [9] | Sontag, E. D., Remarks on interpolation and recognition using neural nets, (Lippmann, R. P.; Moody, J.; Touretzky, D. S., Advances in Neural Information Processing Systems 3 (1991), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 939-945 |
| [10] | Maass, W.; Schnitger, G.; Sontag, E. D., On the computational power of sigmoid versus Boolean threshold circuits, Proc. of the 32nd Annual Symp. on Foundations of Computer Science (1991) · Zbl 0835.68042 |
| [11] | Blum, L.; Shub, M.; Smale, S., On a theory of computation and complexity over the real numbers: NP completeness, recursive functions, and universal machines, Bull. A.M.S., 21, 1, 1-46 (1989) · Zbl 0681.03020 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
