global_dynamics_of_Cellular Automata元胞自动机的全局动力学The Global Dynamics ofCellular AutomataAN ATLAS OF BASIN OF ATTRACTION FIELDS OFONE-DIMENSIONAL CELLULAR AUTOMATAAndrew Wuenschesanta fe instituteSanta Fe, New Mexico, USAMike LesserInternational Ecotechnology Research CentreCranfield Institute of TechnologyBedford, MK43 OAL, United kingdomReferenceⅴ olume iSanta Fe instituteStudies in the Sciences of Complextywe orginal publisherADDISON-WESLEY PUBLISHING COMPANYThe Advanced Book programReading, Massachusetts Menlo Park, California New YorkParis Seoul Milan Mexico City TaipeuAp gDon Mills, Ontario Wokingham, England AmsBonnSydney Singapore Tokyo Madrid San Ju15dirwMio ouPublisher: Dauid MillerProduction Manager: Michael CironeDirector of Publications, Santa Fe Institute: Ronda K.Butier-villaPublications Assistant, Santa Fe Institute: Della L. UlibarriThe front cover shows a basin of attraction consisting of 8580 global states(about 26% of state space)converging onto anattractor cycle with period 120. The system parameters are n =5, rule 54461424, L= 15, seed singletonThe title page shows a basin of attraction which may be seen in the context of its basin of attraction field on page 203. Thesystem parameters are n= 5, code 53, L= 15, seed singletonThese and all similar graphics are examples of screen or printer output from the software included with the bookLibrary of Congress Cataloging-in-Publication DataWuensche, Andrew.The global dynamics of cellular automata: an atlas of basin ofattraction fields of one-dimensional cellular automata/AndrewWuensche, Mike Lesserp. cm -( Santa Fe Institute studies in the sciences ofcomplexity. Reference volumes; v 1)Includes bibliographical references(p. )and indexISBN0-20155740-11. Cellular automata. 2. State-space methods.3.Differentiabledynamical systems. I. Lesser, Mike. II. Title. IIl. SeriesQA2675c45W8319925113-dc2092-17543This volume was typeset using TEXtures on a Macintosh II computer Camera-ready output from a NEC Silentwriter 2 printerCopyright 1992 by Addison-Wesley Publishing Company, The Advanced Book Program, Jacob Way, Reading, MA 01867All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any formor by any means, electronic, mechanical, photocopying, recording, or otherwise, without the prior written permission of thepublisher. Printed in the United States of America. Published simultaneously in Canada.Jacket design by Hannus Design Associates123456789AL95949392First printing, July 1992About the santa Fe instituteThe Santa Fe Institute(SFI) is a multidisciplinary graduate research and teaching institution formed to nurtureresearch on complex systems and their simpler elements. a private independent institution, sfi was founded in 1984Its primary concern is to focus the tools of traditional scientific disciplines and emerging new computer resourceson the problems and opportunities that are involved in the multidisciplinary study of complex systems thosefundamental processes that shape almost every aspect of human life Understanding complex systems is critical torealizing the full potential of science, and may be expected to yield enormous intellectual and practical benefitsAll titles from the Santa Fe Institute Studies in the Sciences of Complexity(circa A D 950-1150 )and was drawn by Betsy ]oneg a Mimbres pottery designseries will carry the sFi logo; this imprint is based onSanta Fe Institute Editorial BoardJune 1991Dr, L.M. Simmons jr: ChairVice President, Academic Affairs, Santa Fe InstituteProfessor Kenneth]. arrowDepartment of Economics, Stanford UniversityProfessor w. Brian ArthurDean &z virginia Morrison Professor of Population Studies and Economics, Food Research InstituteStanford UniversityProfessor Michele boldrinMEDS, Northwestern UniversityDr David K. CampbellDirector, Center for Nonlinear Studies, Los Alamos National LaboratoryDr George A. CowanVisiting Researcher, Santa Fe Institute and Senior Fellow Emeritus, Los Alamos National LaboratoryProfessor Marcus W. FeldmanDirector, Institute for Population Resource Studies, Stanford UniversityProfessor Murray Gell-MannDivision of Physics Astronomy, California Institute of TechnologyProfessor John h. hollandDivision of Computer Science &z engineering, University of MichiganDr. Bela juleszHead, visual Perception Research, at& T Bell LaboratoriesProfessor Stuart KauffmanSchool of Medicine, University of PennsylvaniaDr Edward A. KnappPresident, Santa Fe InstituteProfessor Harold Morowitz, University Professor, George Mason UniversityDr. Alan s. PerelsonTheoretical Division, Los Alamos National LaboratoryProfessor David PinesDepartment of Physics, University of IllinoisProfessor Harry L SwinneyDepartment of Physics, University of TexasSanta Fe Institute Studies in the Sciences of ComplexityPROCEEDINGS VOLUMESVolume EditorTitleDavid pinesEmerging Syntheses in Science, 1987Alan s PerelsonTheoretical Immunology, Part One, 1988IIAlan s. PerelsonTheoretical Immunology, Part Two, 1988Gary D. Doolen et alLattice Gas Methods for Partial DifferentiaEquations, 1989Philip W. Anderson, Kenneth The Economy as an Evolving Complex System, 1988arrow david PinesⅵIChristopher G. LangtonArtificial Life: Proceedings of an InterdisciplinaryWorkshop on the Synthesis and Simulation ofiving Systems, 1988George I Bell &Computers and dNA, 1989Thomas G. marrVIlI Wojciech H. ZurekComplexity, Entropy, and the Physics of Information1990IXAlan s. PerelsonMolecular Evolution on Rugged LandscapesStuart A. KauffmanProteins, RNa and the Immune System, 1990Christopher G. Langton et aL. Artificial Life Il: Proceedings of the SecondInterdisciplinary Workshop on the Synthesisand Simulation of Living Systems, 1991XIJohn A. hawkinsEvolution of Human Languages, 1992Murray Gell-MannLECTURES VOLUMESVolume EditorTitleDaniel L. SteinLectures in the Sciences of Complexity, 1989Erica jen1989 Lectures in Complex Systems, 1990Daniel L. Stein lynn Nadel 1990 Lectures in Complex Systems, 1991LECTURE NOTES VOLUMESVolume ArTitleJohn Hertz, Anders Krogh, Introduction to the Theory of Neural Computation, 1990richard g. palmerGerard WeisbuchComplex Systems Dynamics, 1990REFERENCE VOLUMESVolume AuthorTitleAndrew WuenscheBasin of Attraction Fields of One-Dimensiony?The Global Dynamics of Cellular Automata: AlAtlas ofMike LesserCellular Automata, 1992