Article

Computing with continuous-time Liapunov systems

Authors:

Pekka OrponenAuthors Info & Claims

STOC '01: Proceedings of the thirty-third annual ACM symposium on Theory of computing

Pages 722 - 731

https://doi.org/10.1145/380752.380878

Published: 06 July 2001 Publication History

Abstract

We establish a fundamental result in the theory of computation by continuous-time dynamical systems, by showing that systems corresponding to so called continuous-time symmetric Hopfield nets are capable of general computation. More precisely, we prove that any function computed by a discrete-time asymmetric recurrent network of n threshold gates can also be computed by a continuous-time symmetrically-coupled Hopfield system of dimension 18n+7. Moreover, if the threshold logic network has maximum weight w_{\max} and converges in discrete time t^*, then the corresponding Hopfield system can be designed to operate in continuous time Θ(t^*/ε), for any value 0<ε<0.0025 such that w_{\max}2^{3n}\leq\ε 2^{1/ε}.

The result appears at first sight counterintuitive, because the dynamics of any symmetric Hopfield system is constrained by a Liapunov, or energy function defined on its state space. In particular, such a system always converges from any initial state towards some stable equilibrium state, and hence cannot exhibit nondamping oscillations, i.e. strictly speaking cannot simulate even a single alternating bit. However, we show that if one only considers terminating computations, then the Liapunov constraint can be overcome, and one can in fact embed arbitrarily complicated computations in the dynamics of Liapunov systems with only a modest cost in the system's dimensionality.

In terms of standard discrete computation models, our result implies that any polynomially space-bounded Turing machine can be simulated by a family of polynomial-size continuous-time symmetric Hopfield nets.

References

[1]

{1} E. Asarin and O. Maler. On some relations between dynamical systems and transition systems. In Proceedings of the 21st International Colloquium on Automata, Languages, and Programming (Jerusalem July), volume 820 of LNCS, pages 59-72. Springer-Verlag, Berlin, 1994.

Digital Library

[2]

{2} J. L. Balcázar, J. Díaz, and J. Gabarró. Structural Complexity, volume I. Springer-Verlag, Berlin, 2nd edition, 1995.

Digital Library

[3]

{3} J. L. Balcázar, R. Gavaldà, and H. T. Siegelmann. Computational power of neural networks: A characterization in terms of Kolmogorov complexity. IEEE Transactions of Information Theory, 43:1175-1183, 1997.

Digital Library

[4]

{4} M. Branicky. Analog computation with continuous ODEs. In Proceedings of the Workshop on Physics and Computation Phys Comp'94 (Dallas, TX, November), pages 265-274. IEEE Computer Society Press, Los Alamitos, CA, 1994.

[5]

{5} M. Casey. The dynamics of discrete-time computation, with application to recurrent neural networks and finite state machine extraction. Neural Computation, 8:1135-1178, 1996.

Digital Library

[6]

{6} M. A. Cohen and S. Grossberg. Absolute stability of global pattern formation and parallel memory storage by competitive neural networks. IEEE Transactions on Systems, Man, and Cybernetics, 13:815-826, 1983.

[7]

{7} R. M. Golden. Mathematical Methods for Neural Network Analysis and Design. The MIT Press, Cambridge, MA, 1996.

Digital Library

[8]

{8} E. Goles and S. Martínez. Exponential transient classes of symmetric neural networks for synchronous and sequential updating. Complex Systems, 3:589-597, 1989.

[9]

{9} S. Haykin. Neural Networks: A Comprehensive Foundation. Prentice-Hall, Upper Saddle River, NJ, 2nd edition, 1999.

Digital Library

[10]

{10} J. J. Hopfield. Neural networks and physical systems with emergent collective computational abilities. In Proceedings of the National Academy of Sciences, volume 79, pages 2554-2558. 1982.

[11]

{11} J. J. Hopfield. Neurons with graded response have collective computational properties like those of two-state neurons. In Proceedings of the National Academy of Sciences, volume 81, pages 3088-3092. 1984.

[12]

{12} J. J. Hopfield and D. W. Tank. "Neural" computation of decisions in optimization problems. Biological Cybernetics, 52:141-152, 1985.

Digital Library

[13]

{13} B. G. Horne and D. R. Hush. Bounds on the complexity of recurrent neural network implementations of finite state machines. Neural Networks, 9:243-252, 1996.

Digital Library

[14]

{14} P. Indyk. Optimal simulation of automata by neural nets. In Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science (Munich, March), volume 900 of LNCS, pages 337-348. Springer-Verlag, Berlin, 1995.

[15]

{15} P. Koiran, M. Cosnard, and M. Garzon. Computability with low-dimensional dynamical systems. Theoretical Computer Science, 132:113-128, 1994.

Digital Library

[16]

{16} M. Lepley and G. Miller. Computational power for networks of threshold devices in an asynchronous environment. Unpublished manuscript, Department of Mathematics, Massachusetts Institute of Technology, 1983.

[17]

{17} W. Maass and P. Orponen. On the effect of analog noise in discrete-time analog computations. Neural Computation, 10:1071-1095, 1998.

Digital Library

[18]

{18} C. Moore. Unpredictability and undecidability in physical systems. Physical Review Letters, 64:2354-2357, 1990.

[19]

{19} C. Moore. Finite-dimensional analog computers: flows, maps, and recurrent neural networks. In Proceedings of the 1st International Conference on Unconventional Models of Computation (Auckland, January). Springer-Verlag, Berlin, 1998.

[20]

{20} S. Omohundro. Modelling cellular automata with partial differential equations. Physica, 10D:128-134, 1984.

[21]

{21} P. Orponen. The computational power of discrete Hopfield nets with hidden units. Neural Computation, 8:403-415, 1996.

Digital Library

[22]

{22} P. Orponen. The computational power of continuous time neural networks. In Proceedings of the 24th SOFSEM Seminar on Current Trends in Theory and Practice of Informatics (Milovy, Czech Republic, November), volume 1338 of LNCS, pages 86-103. Springer-Verlag, Berlin, 1997.

Digital Library

[23]

{23} P. Orponen. A survey of continuous-time computation theory. In D.-Z. Du and K.-I. Ko, editors, Advances in Algorithms, Languages, and Complexity, pages 209-224. Kluwer Academic Publishers, Dordrecht, 1997.

[24]

{24} I. Parberry. Circuit Complexity and Neural Networks. MIT Press, Cambridge, MA, 1994.

Digital Library

[25]

{25} H. T. Siegelmann. Neural Networks and Analog Computation: Beyond the Turing Limit. Birkhäuser, Boston, MA, 1999.

Digital Library

[26]

{26} H. T. Siegelmann and E. D. Sontag. Analog computation via neural networks. Theoretical Computer Science, 131:331-360, 1994.

Digital Library

[27]

{27} H. T. Siegelmann and E. D. Sontag. Computational power of neural networks. Journal of Computer System Science, 50:132-150, 1995.

Digital Library

[28]

{28} H. M. Stoll and L.-S. Lee. A continuous-time optical neural network. In Proceedings of the IEEE International Conference on Neural Networks (San Diego, CA, July), volume II, pages 373-384. 1988.

[29]

{29} J. ¿íma. On the computational power of continuous-time symmetric Hopfield nets. Technical Report V-815, Institute of Computer Science, Academy of Sciences of the Czech Republic, Prague, 2000.

[30]

{30} J. ¿íma and P. Orponen. A continuous-time Hopfield net simulation of discrete neural networks. In Proceedings of the 2nd NC'2000 International ICSC Symposium on Neural Computing (Berlin, May), pages 36-42. ICSC Academic Press, Wetaskiwin (Canada), 2000.

[31]

{31} J. ¿íma and P. Orponen. Exponential transients in continuous-time Liapunov systems. In Proceedings of the 11th ICANN'2001 Conference on Artificial Neural Networks (Vienna, August). Springer Verlag, Berlin, 2001. To appear.

[32]

{32} J. ¿íma, P. Orponen, and T. Antti-Poika. On the computational complexity of binary and analog symmetric Hopfield nets. Neural Computation, 12:2965-2989, 2000.

Digital Library

[33]

{33} J. ¿íma and J. Wiedermann. Theory of neuromata. Journal of the ACM, 45:155-178, 1998.

Digital Library

Cited By

Fountas NKrimpenis AVaxevanidis NDavim J(2012)Single and Multi-objective Optimization Methodologies in CNC MachiningStatistical and Computational Techniques in Manufacturing10.1007/978-3-642-25859-6_5(187-218)Online publication date: 2012
https://doi.org/10.1007/978-3-642-25859-6_5
Durand-Lose J(2005)Abstract geometrical computationProceedings of the First international conference on Computability in Europe: new Computational Paradigms10.1007/11494645_14(106-116)Online publication date: 8-Jun-2005
https://dl.acm.org/doi/10.1007/11494645_14
Šíma JOrponen P(2003)Continuous-time symmetric Hopfield nets are computationally universalNeural Computation10.1162/08997660332119213015:3(693-733)Online publication date: 1-Mar-2003
https://dl.acm.org/doi/10.1162/089976603321192130
Show More Cited By

Index Terms

Computing with continuous-time Liapunov systems

Recommendations

Exponential transients in continuous-time Liapunov systems

We consider the convergence behavior of a class of continuous-time dynamical systems corresponding to so-called symmetric Hopfield nets studied in neural networks theory. We prove that such systems may have transient times that are exponential in the ...
Finite-Time Stability and Stabilization for Continuous Systems with Additive Time-Varying Delays

This paper is centered on the problem of delay-dependent finite-time stability and stabilization for a class of continuous system with additive time-varying delays. Firstly, based on a new Lyapunov---Krasovskii-like function (LKLF), which splits the ...
Delay-dependent Stabilization Conditions of Controlled Positive Continuous-time Systems

The stabilization problem for a class of linear continuous-time systems with time-varying non differentiable delay is solved while imposing positivity in closed-loop. In particular, the synthesis of state-feedback controllers is studied by giving ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '01: Proceedings of the thirty-third annual ACM symposium on Theory of computing

July 2001

755 pages

ISBN:1581133499

DOI:10.1145/380752

Copyright © 2001 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 July 2001

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC01

Sponsor:

SIGACT

STOC01: 33rd ACM Symposium on Theory of Computing

Hersonissos, Greece

Acceptance Rates

STOC '01 Paper Acceptance Rate 83 of 230 submissions, 36%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
18
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Fountas NKrimpenis AVaxevanidis NDavim J(2012)Single and Multi-objective Optimization Methodologies in CNC MachiningStatistical and Computational Techniques in Manufacturing10.1007/978-3-642-25859-6_5(187-218)Online publication date: 2012
https://doi.org/10.1007/978-3-642-25859-6_5
Durand-Lose J(2005)Abstract geometrical computationProceedings of the First international conference on Computability in Europe: new Computational Paradigms10.1007/11494645_14(106-116)Online publication date: 8-Jun-2005
https://dl.acm.org/doi/10.1007/11494645_14
Šíma JOrponen P(2003)Continuous-time symmetric Hopfield nets are computationally universalNeural Computation10.1162/08997660332119213015:3(693-733)Online publication date: 1-Mar-2003
https://dl.acm.org/doi/10.1162/089976603321192130
Šı́ma JOrponen P(2003)Exponential transients in continuous-time Liapunov systemsTheoretical Computer Science10.1016/S0304-3975(03)00310-4306:1-3(353-372)Online publication date: Sep-2003
https://doi.org/10.1016/S0304-3975(03)00310-4
Sima JOrponen P(2001)Exponential Transients in Continuous-Time Symmetric Hopfield NetsArtificial Neural Networks — ICANN 200110.1007/3-540-44668-0_112(806-814)Online publication date: 17-Aug-2001
https://doi.org/10.1007/3-540-44668-0_112

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents