Computability with low-dimensional dynamical systems. (English) Zbl 0821.68053

Summary: It has been known for a short time that a class of recurrent neural networks has universal computational abilities. These networks can be viewed as iterated piecewise-linear maps in a high-dimensional space. In this paper, we show that similar systems in dimension two are also capable of universal computations. On the contrary, it is necessary to resort to more complex systems (e.g., iterated piecewise-monotone maps) in order to retain this capability in dimension one.


68Q05 Models of computation (Turing machines, etc.) (MSC2010)
37J99 Dynamical aspects of finite-dimensional Hamiltonian and Lagrangian systems
Full Text: DOI


[1] 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. Amer. Math. Soc., 21, 1, 1-46 (1989) · Zbl 0681.03020
[2] Bothelho, F.; Garzon, M., On dynamical properties of neural networks, Complex Systems, 5, 4, 401-403 (1991) · Zbl 0765.58012
[3] Collet, P.; Eckmann, J. P., Iterated maps on the interval as dynamical systems, (Progress in Physics, Vol. I (1980), Birkhäuser: Birkhäuser Boston) · Zbl 0711.35061
[4] Garzon, M.; Bothelho, F., Real computation with cellular automata, (Boccara, N., Proc. Workshop on Cellular Automata and Cooperative Systems (1993), Kluwer: Kluwer Dorchet, MA), 191-202 · Zbl 0851.68081
[5] Garzon, M.; Franklin, S. P., Neural computability II, Proc. 3rd Int. Joint Conf. on Neural Networks, Vol. 1, 631-637 (1989), Washington, DC
[6] Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0196.01701
[7] Koiran, P., Puissance de calcul des réseaux de neurones artificiels, (Ph.D. Thesis (1993), Ecole Normale Supérieure de Lyon)
[8] M.L. Minsky, Computation: Finite and Infinite Machines; M.L. Minsky, Computation: Finite and Infinite Machines · Zbl 0195.02402
[9] Moore, C., Unpredictability and undecidability in dynamical systems, Phys. Rev. Lett., 64, 20, 2354-2357 (1990) · Zbl 1050.37510
[10] Moore, C., Generalized shifts: unpredictability and undecidability in dynamical systems, Nonlinearity, 4, 199-230 (1991) · Zbl 0725.58013
[11] Preston, C., Iterates of Piecewise Monotone Mappings on an Interval, Vol. 1347, (Lecture Notes in Mathematics (1988), Springer: Springer Berlin) · Zbl 0684.58002
[12] Richardson, D., Tessellation with local transformations, J. Comput. System Sci., 6, 373-388 (1972) · Zbl 0246.94037
[13] Siegelmann, H. T.; Sontag, E. D., On the computational power of neural nets, (SYCON Report 91-11 (1991), Rutgers University) · Zbl 0826.68104
[14] Siegelmann, H. T.; Sontag, E. D., Turing computation with neural nets, Appl. Math. Lett., 4, 6, 77-80 (1991) · Zbl 0749.68032
[15] Siegelmann, H. T.; Sontag, E. D., On the computational power of neural nets, Proc. 5th ACM Workshop on Computational Learning Theory (1992)
[16] Weihrauch, K., Computability, (EATCS Monographs on Theoretical Computer Science (1987), Springer: Springer Berlin) · Zbl 0611.03002
[17] Zeigler, E. D., Every discrete input machine is linearly simulatable, J. Comput. System Sci., 161-167 (1973) · Zbl 0258.94036
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.