Chaotic neural nets, computability, and undecidability: Toward a computational dynamics
1995; Wiley; Volume: 10; Issue: 1 Linguagem: Inglês
10.1002/int.4550100106
ISSN1098-111X
Autores Tópico(s)Chaos control and synchronization
ResumoInternational Journal of Intelligent SystemsVolume 10, Issue 1 p. 41-69 Article Chaotic neural nets, computability, and undecidability: Toward a computational dynamics Gianfranco Basti, Gianfranco Basti Pontifical Gregorian University, P.zza della Pilotta 4, I-00184 Rome, Italy Also INFN—National Institute for Nuclear Physics, Section of Rome II, I-00133 Rome, Italy and INO—National Institute for Optics, I-50125 Arcetri, Florence, Italy.Search for more papers by this authorAntonio L. Perrone, Antonio L. Perrone Dept. of Physics, II Univ. of Rome “Tor Vergata”, Via della Ricerca Scientifica 1, I-00133 Rome, Italy Also INFN—National Institute for Nuclear Physics, Section of Rome II, I-00133 Rome, Italy and INO—National Institute for Optics, I-50125 Arcetri, Florence, Italy.Search for more papers by this author Gianfranco Basti, Gianfranco Basti Pontifical Gregorian University, P.zza della Pilotta 4, I-00184 Rome, Italy Also INFN—National Institute for Nuclear Physics, Section of Rome II, I-00133 Rome, Italy and INO—National Institute for Optics, I-50125 Arcetri, Florence, Italy.Search for more papers by this authorAntonio L. Perrone, Antonio L. Perrone Dept. of Physics, II Univ. of Rome “Tor Vergata”, Via della Ricerca Scientifica 1, I-00133 Rome, Italy Also INFN—National Institute for Nuclear Physics, Section of Rome II, I-00133 Rome, Italy and INO—National Institute for Optics, I-50125 Arcetri, Florence, Italy.Search for more papers by this author First published: 1995 https://doi.org/10.1002/int.4550100106Citations: 7 AboutPDF ToolsRequest permissionExport citationAdd to favoritesTrack citation ShareShare Give accessShare full text accessShare full-text accessPlease review our Terms and Conditions of Use and check box below to share full-text version of article.I have read and accept the Wiley Online Library Terms and Conditions of UseShareable LinkUse the link below to share a full-text version of this article with your friends and colleagues. Learn more.Copy URL Abstract In this article we intend to analyze a chaotic system from the standpoint of its computation capability. to pursue this aim, we refer to a complex chaotic dynamics that we characterize via its symbolic dynamics. We show that these dynamic systems are subjected to some typical undecidable problems. Particularly, we stress the impossibility of deciding on a unique invariant measure. This depends essentially on the supposition of the existence of a fixed universal grammar. the suggestion is thus of justifying a contextual redefinition of the grammar as a function of the same evolution of the system. We propose on this basis a general theorem for avoiding undecidable problems in computability theory by introducing a new class of recursive functions on different axiomatizations of numbers. From it a series expansion on n algebraic fields can be defined. In such a way, we are able to obtain a very fast extraction procedure of unstable periodic orbits from a generic chaotic dynamics. the computational efficiency of this algorithm allows us to characterize a chaotic system by the complete statistics of its unstable cycles. Some examples of these two techniques are discussed. Finally, we introduce the possibility of an application of this same class of recursive functions to the calculus of the absolute minimum of energy in neural nets, as far as it is equivalent to a well-formed formula of a first-order predicate calculus. © 1995 John Wiley & Sons, Inc. Reference 1 C. Argnes and M. Raseti “Undecidability of the word problem and chaos in symbolic dynamics,” II Nuouo Cimento, 106, 879– 907 (1991). 2 A. A. Markov, “On the impossibility of certain algorithms in the theory of associative systems,” Doklady Akademii Nauk S. S. S. R., 55, 587– 590 (1947). 3 E. L. Post, “Recursive unsolvability of a problem of Thue,” The J. Symbolic Logic, 12, 1– 11 (1947). 4 I. Niven, H. S. Zuckerman, and H. L. Montgomery, An Introduction to the Theory of Numbers, Wiley, New York, 1991. 5 M. Davis, Computability and Unsolvability, McGraw-Hill, New York, 1958. 6 G. Basti and A. Perrone, Teorema di Computabilita Dinamica per Macchine Finite, Internal Report Dept. of Physics, Unv. of Rome “Tor Vergata”, ROM2 F/92/01, Roma, 1992. 7 G. Basti and A. Perrone, “A theorem of computational effectiveness for a mutual redefinition of numbers and processes,” Proceedings of Int. Symp. on Information Physics (ISKIT'92), Iizuka, Japan, July 12-15, 1992, Kyushu Institute of Technology Press, Iizuka, 1992, pp. 122– 133. 8 S. C. Kleene, Introduction to Metamathematics, North-Holland Amsterdam, 1980.8 9 E. Mendelson, Introduction to Mathematical Logic, Princeton University Press, Princeton, NJ, 1964. 10 H. Rogers Jr., Theory of Recursive Functions and Effective Computability, MIT Press, Cambridge MA, 1988.2 11 K. Gödel, Über formal unentsheidbare Sätze der Principia Mathematica und verwandter Systeme, I, Mh. Math. Phys., 38, 173– 198 (1931). 12 P. J. Cohen, Set Theory and the Continuum Hypothesis, the Benjamin Cummings Publishing Company, Inc., New York, 1966. 13 M. Clavelli, E. De Giorgi, M. Forti, and V. M. Tortorelli, “ A self-reference oriented theory for the Foundations of Mathematics,” In Analyse Mathematique et applications—Contributions en l'honneur de Jacques-Louis Lions, Gauthier-Villars, Paris, 1988, pp. 67– 115. 14 R. Smullyan, Theory of Formal System, Princeton University Press, Princeton, NJ, 1962. 15 H. D. Ebbinghaus, H. Hermes, F. Hirrzebruch, M. Koecher, K. Mainzer, J. Neukirch, A. Prestel, and R. Remmert, Numbers, Springer, New York, Heidelberg, 1990. 16 R. Artuso, “Scale e cicli in dinamiche caotiche,” Ph.D. Thesis, Univ. of Milan, 1992. 17 D. Auerbach, P. Cvitanović, J. P. Eckmann, G. Gunaratne, and I. Procaccia, Phys. Rev. Lett., 58, 2387 (1987). 18 K. Pawelzik and H. G. Schuster, Phys. Rev. A, 43, 1808 (1991). 19 N. H. Packard, J. P. Crutchfield, J. D. Farmer, and R. S. Shaw, Phys. Rev. Lett., 45, 712 (1980). 20 J. P. Eckmann and D. Ruelle, Rev. Mod. Phys., 57, 617 (1985). 21 F. T. Arecchi, G. Basti, S. Boccaletti, and A. L. Perrone, “Adaptive recognition of a chaotic dynamics,” submitted to Phys. Rev. Lett., 1993. 22 L. M. Pecora and T. L. Carrol, Phys. Rev. Lett., 64, 821 (1990). 23 G. Basti, P. Cocciolo, and A. Perrone, “ Controlling chaotic systems by mutual redefinition of space and dynamics,” In State-of-the-Art Mapping, B. Huberty et al. (Eds.), Orlando FL, April 13-15 1993, SPIE Proceedings Series, 1943, Washington, 1993, in press. 24 W. S. McCulloch and W. H. Pitts, “A logical calculus of the ideas immanent in nervous activity,” Bull. of Math. Biophys., 5, 115– 133 (1943). 25 G. Pinkas, “Symmetric neural networks and propositional logic satisfiability,” Neural Computation, 3, 282– 291 (1991). 26 S. I. Amari, Neural Networks, 6, 161 (1993). 27 E. B. Baum and D. Haussler, Neural Computation, 1, 151 (1989). 28 A. L. Blum and R. L. Rivest, Neural Networks, 5, 117 (1992). 29 A. L. Perrone, P. Castiglione, G. Basti, and R. Messi, “Dynamic definition of net topology for parallel architectures. an outlook of computational dynamics.” to be published in Progr. of Theor. Phys., (1993). 30 A. Perrone, G. Basti, and A. Chiavoni, “ A neural module for real time simultaneous discrimination and locking on different temporal series in noisy environment,” In Applications of Artificial Neural Networks III, S. K. Rogers (Ed.), Orlando FL, April 21-24, 1992, SPIE Proceedings Series, 1709, Washington, 1992, pp. 926– 936. 31 M. L. Minsky and S. A. Papert, Perceptrons, expanded edition, MIT Press, Cambridge, MA, 1988. Citing Literature Volume10, Issue11995Pages 41-69 ReferencesRelatedInformation
Referência(s)