×

zbMATH — the first resource for mathematics

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.

MSC:
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
37J99 Dynamical aspects of finite-dimensional Hamiltonian and Lagrangian systems
PDF BibTeX XML Cite
Full Text: DOI
References:
[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)
[3] Collet, P.; Eckmann, J.P., Iterated maps on the interval as dynamical systems, () · Zbl 0711.35061
[4] Garzon, M.; Bothelho, F., Real computation with cellular automata, (), 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 Reading, MA · Zbl 0196.01701
[7] Koiran, P., Puissance de calcul des réseaux de neurones artificiels, ()
[8] M.L. Minsky, Computation: Finite and Infinite Machines (Prentice-Hall, Englewood Cliffs No. 1967). · 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, ()
[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, () · 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, () · 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.