A Brief History of Cellular AutomataPALASH SARKARIndian Statistical InstituteCellular automata are simple models of computation which exhibit fascinatinglycomplex behavior. They have captured the attention of several generations ofresearchers, leading to an extensive body of work. Here we trace a history ofcellular automata from their beginnings with von Neumann to the present day.The emphasis is mainly on topics closer to computer science and mathematicsrather than physics, biology or other applications. The work should be of interest toboth new entrants into the field as well as researchers working on particularaspects of cellular automata.Categories and Subject Descriptors: F.1.1 [Conputation by abstract devices]:Models of Computation; K.2 [Computing Milieux]: History of ComputingGeneral Terms: TheoryAdditional Key Words and Phrases: Cellular automata, cellular space,homogeneous structures, systolic arrays, tessellation automata1. INTRODUCTIONCellular automata were originally pro-posed by John von Neumann as formalmodels of self-reproducing organisms.The structure studied was mostly onone- and two-dimensional infinite grids,though higher dimensions were alsoconsidered. Computation universalityand other computation-theoretic ques-tions were considered important. SeeBurks [1970] for a collection of essayson important problems on cellular au-tomata during this period. Later, physi-cists and biologists began to study cellu-lar automata for the purpose ofmodeling in their respective domains. Inthe present era, cellular automata arebeing studied from many widely differ-ent angles, and the relationship of thesestructures to existing problems are be-ing constantly sought and discovered.Next, we would like to clarify thepurpose of this survey as compared toother related work. There is an excel-lent survey of CA by A.R. Smith III[Smith III 1976]. However, it is morethan twenty years old. There are alsotwo other surveys [Vollmar 1977; Ala-dyev 1974] which are quite old. Cur-rently, it is perhaps quite impossible tosurvey the whole of CA research. Thereis a good survey on computation theo-retic aspects of CA by Culik II et al.[1990]. There are also books on CA[Garzon 1995; Chaudhuri et al. 1997;Wolfram 1986] which cover specific top-ics of CA research. In this survey we tryto cover the major questions askedabout CA as opposed to the use of CA inAuthor’s address: Applied Statistics Unit, Indian Statistical Institute, 203 B.T. Road, Calcutta, India700035; email: [email protected] to make digital/hard copy of part or all of this work for personal or classroom use is grantedwithout fee provided that the copies are not made or distributed for profit or commercial advantage, thecopyright notice, the title of the publication, and its date appear, and notice is given that copying is bypermission of the ACM, Inc. To copy otherwise, to republish, to post on servers, or to redistribute tolists, requires prior specific permission and/or a fee.© 2000 ACM 0360-0300/00/0300–0080 $5.00ACM Computing Surveys, Vol. 32, No. 1, March 2000modeling of natural phenomena. We fo-cus on topics which are closer to com-puter science and mathematics ratherthan physics or other applications. Webelieve that such a survey has not beenpreviously attempted, and will prove tobe useful to both fresh entrants into thisfield and to experts working on particu-lar aspects of CA. However, we wouldlike to point out that any review of CAis bound to be incomplete. We have beenmotivated in choosing topics based onour knowledge and interest. The afore-mentioned surveys by A.R. Smith IIIand Culik II et al. have helped usgreatly in preparing this work. The bib-liography associated with this article isnot comprehensive, though we believethat there are sufficient links to almostall aspects of CA. Additional bibliogra-phies can be found in the books men-tioned above. An online bibliography onCA is also available athttp://alife.santafe.edu/alife/topics/cas/ca-faq/ca-faq.bibAt this point we would like to make afew remarks on the problem of trying towrite a history of any scientific topic. Achronological ordering of ideas is diffi-cult to adhere to, since an idea may beintroduced at some point in time, ispursued vigorously for a while, and maydisappear from the literature for quitesome time, only to be taken up again ata later point. There is almost no finalstatement on any idea. A thematicgrouping of topics is possible and ismostly used. However, in such an ap-proach one might have to include workfrom different decades under the samegroup, and this presents its own prob-lems. The scientific temper variesacross time, which leads to a distinctdifference in the approach to a problem.So even though the topic may be thesame, the method and questions mayvary considerably. In this paper we tryto take a chronological view of workdone in the area of cellular automataover the past forty years, and we orderthe topics based upon their first appear-ance in the literature. We have dividedthe work into three broad categories.—Classical: The themes which weremore or less influenced by the initialwork of von Neumann.—Modern: The themes which were in-fluenced by the work of Wolfram onone hand, and by developments ofother branches of computer science onthe other hand. In this part we re-strict ourselves to topics closer tocomputer science than physics.—Games: Apart from the Game of Lifeands-game we have also included theFiring Squad problem in this section.The problem formulation of the FiringSquad problem has more of the flavorof a game than a synchronizationproblem. Also, this problem somehowdoes not fit into any of the above twoclasses.In the rest of the article we abbreviateboth cellular automata and cellular au-tomaton by CA. We consider differentvarieties of CA, but the exact structuremeant will always be clear from thecontext.CONTENTS1. Introduction2. Classical2.1 Beginnings2.2 Variants of Cellular Automata2.3 Biological Connection2.4 Fault-Tolerant Computing2.5 Language and Pattern Recognition2.6 Invertibility, Surjectivity and Garden of Eden3. CA Games3.1 Firing Squad Problem3.2 Game of Life3.3s~s1! -Game4. Modern Research4.1 Empirical Study4.2 Classification of CA4.3 Limit Sets and Fractal Properties4.4 Dynamics of CA4.5 Computational Complexity4.6 Finite CA and its Applications5. ConclusionBrief History of Cellular Automata •81ACM Computing Surveys, Vol. 32, No. 1, March 20002. CLASSICAL2.1 BeginningsThe simplest
View Full Document
Unlocking...