Revisão Bibliográfica: Autômatos Celulares
Theoretical Computer Science
Download 445.54 Kb.
|
- Navigate this page:
- Theoretical Computer Science
- Referências em Papel
- Fonte: http://www.santafe.edu/projects/evca/
- Title: Dynamics, Computation, and the "Edge of Chaos": A Re-Examination
Theoretical Computer ScienceVol: 244, Issue: 1-2, August 6, 2000 pp. 219-241 Title: Investigating topological chaos by elementary cellular automata dynamics Authors: Cattaneo, Gianpieroa; Finelli, Micheleb; Margara, Lucianob Affiliations: a. University degli Studi di Milano, Dipartimento di Scienze della Informazione, via Comelico 39, I-20135, Milano, Italy b. University of Bologna, Department of Computer Science, Mura Anteo Zamboni 7, I-40127, Bologna, Italy Abstract: We apply the two different definitions of chaos given by Devaney and by Knudsen for general discrete time dynamical systems (DTDS) to the case of elementary cellular automata, i.e., 1-dimensional binary cellular automata with radius 1. A DTDS is chaotic according to the Devaney's definition of chaos iff it is topologically transitive, has dense periodic orbits, and it is sensitive to initial conditions. A DTDS is chaotic according to the Knudsen's definition of chaos iff it has a dense orbit and it is sensitive to initial conditions. We enucleate an easy-to-check property (left or rightmost permutivity) of the local rule associated with a cellular automaton which is a sufficient condition for D-chaotic behavior. It turns out that this property is also necessary for the class of elementary cellular automata. Finally, we prove that the above mentioned property does not remain a necessary condition for chaoticity in the case of non elementary cellular automata. Publisher: Elsevier Science Language of Publication: English Item Identifier: S0304-3975(98)00345-4 Publication Type: Article ISSN: 0304-3975
pp. 219-241 Title: Investigating topological chaos by elementary cellular automata dynamics Authors: Cattaneo, Gianpieroa; Finelli, Micheleb; Margara, Lucianob Affiliations: a. University degli Studi di Milano, Dipartimento di Scienze della Informazione, via Comelico 39, I-20135, Milano, Italy b. University of Bologna, Department of Computer Science, Mura Anteo Zamboni 7, I-40127, Bologna, Italy Abstract: We apply the two different definitions of chaos given by Devaney and by Knudsen for general discrete time dynamical systems (DTDS) to the case of elementary cellular automata, i.e., 1-dimensional binary cellular automata with radius 1. A DTDS is chaotic according to the Devaney's definition of chaos iff it is topologically transitive, has dense periodic orbits, and it is sensitive to initial conditions. A DTDS is chaotic according to the Knudsen's definition of chaos iff it has a dense orbit and it is sensitive to initial conditions. We enucleate an easy-to-check property (left or rightmost permutivity) of the local rule associated with a cellular automaton which is a sufficient condition for D-chaotic behavior. It turns out that this property is also necessary for the class of elementary cellular automata. Finally, we prove that the above mentioned property does not remain a necessary condition for chaoticity in the case of non elementary cellular automata. Publisher: Elsevier Science Language of Publication: English Item Identifier: S0304-3975(98)00345-4 Publication Type: Article ISSN: 0304-3975
Fonte: http://www.santafe.edu/projects/evca/Title: Revisiting the Edge of Chaos: Evolving Cellular Automata to Perform ComputationsAuthors: Melanie Mitchell, Peter T. Hraber, and James P. Crutchfield Reference: Complex Systems, 7:89-130, 1993 SFI working paper: 93-03-014 Abstract: We present results from an experiment similar to one performed by Packard (1988), in which a genetic algorithm is used to evolve cellular automata (CA) to perform a particular computational task. Packard examined the frequency of evolved CA rules as a function of Langton's lambda parameter (Langton, 1990), and interpreted the results of his experiment as giving evidence for the following two hypotheses: (1) CA rules able to perform complex computations are most likely to be found near ``critical'' lambda values, which have been claimed to correlate with a phase transition between ordered and chaotic behavioral regimes for CA; (2) When CA rules are evolved to perform a complex computation, evolution will tend to select rules with lambda values close to the critical values. Our experiment produced very different results, and we suggest that the interpretation of the original results is not correct. We also review and discuss issues related to lambda, dynamical-behavior classes, and computation in CA. The main constructive results of our study are identifying the emergence and competition of computational strategies and analyzing the central role of symmetries in na evolutionary system. In particular, we demonstrate how symmetry breaking can impede the evolution toward higher computational capability.
Reference: In G. A. Cowan, D. Pines, and D. Meltzer (eds.), Complexity: Metaphors, Models, and Reality, Santa Fe Institute Studies in the Sciences of Complexity, Proceedings Volume 19, 497-513, Addison-Wesley, 1994. SFI working paper: 93-06-040 Abstract: In this paper we review previous work and present new work concerning the relationship between dynamical systems theory and computation. In particular, we review work by Langton (1990) and Packard (1988) on the relationship between dynamical behavior and computational capability in cellular automata (CA). We present results from an experiment similar to the one described in Packard (1988), that was cited there as evidence for the hypothesis that rules capable of performing complex computations are most likely to be found at a phase transition between ordered and chaotic behavioral regimes for CA (the "edge of chaos"). Our experiment produced very different results from the original experiment, and we suggest that the interpretation of the original results is not correct. We conclude by discussing general issues related to dynamics, computation, and the "edge of chaos" in cellular automata.
Fonte: Citeseer: http://citeseer.nj.nec.com Referências Principais: Directory: pub -> docs -> vonzuben pub -> Asilomar Conference on Circuits, Systems & Computers, Pacific Grove, ca, November 1978, pp. 55 58 pub -> Forthcoming meetings and conferences pub -> Harmonised compatibility and sharing conditions for video pmse in the 7 9 ghz frequency band, taking into account radar use docs -> A dragon in the tube vonzuben -> Revisão Bibliográfica: Learning Vector Quantization 28/04/2003 vonzuben -> Revisão bibliográfica redes neurais recorrentes docs -> Updated March 2017 Registration Quick Reference Card for Employees/Associates Download 445.54 Kb. Share with your friends:
|