资源描述：
《Computation in Cellular Automata A Selected Review.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、ComputationinCellularAutomata:ASelectedReviewMelanieMitchellSantaFeInstitute1399HydeParkRoadSantaFe,NM87501U.S.A.email:mm@santafe.eduInT.Gramss,S.Bornholdt,M.Gross,M.Mitchell,andT.Pellizzari,NonstandardComputation,pp.95–140.Weinheim:VCHVerlagsgesellschaft,1
2、998.1IntroductionCellularautomata(CAs)aredecentralizedspatiallyextendedsystemsconsistingoflargenumbersofsimpleidenticalcomponentswithlocalconnectivity.Suchsystemshavethepotentialtoper-formcomplexcomputationswithahighdegreeofefficiencyandrobustness,aswellastom
3、odelthebehaviorofcomplexsystemsinnature.ForthesereasonsCAsandrelatedarchitectureshavebeenstudiedextensivelyinthenaturalsciences,mathematics,andincomputerscience.Theyhavebeenusedasmodelsofphysicalandbiologicalphenomena,suchasfluidflow,galaxyformation,earthquak
4、es,andbiologicalpatternformation.Theyhavebeenconsideredasmathematicalobjectsaboutwhichformalpropertiescanbeproved.Theyhavebeenusedasparallelcomputingdevices,bothforthehigh-speedsimulationofscientificmodelsandforcomputationaltaskssuchasimageprocessing.Inaddit
5、ion,CAshavebeenusedasabstractmodelsforstudying“emergent”coopera-tiveorcollectivebehaviorincomplexsystems.(Forcollectionsofpapersinalloftheseareas,see,e.g.,Burks,1970a;Fogelman-Soulie,Robert,andTchuente,1987;Farmer,Toffoli,andWolfram,1984;Forrest,1990;Gutowit
6、z,1990;Jesshope,Jossifov,andWilhelmi,1994;andWolfram,1986.)InthischapterIwillreviewselectedtopicsrelatedtocomputationinCAs.Thepresentationwillassumeanelementaryknowledgeofthetheoryofcomputation,includingformal-languagetheoryandcomputability.ACAconsistsoftwo
7、components.Thefirstcomponentisacellularspace1:alatticeofNidenticalfinite-statemachines(cells),eachwithanidenticalpatternoflocalconnectionstoothercellsforinputandoutput,alongwithboundaryconditionsifthelatticeisfinite.LetΣdenotethesetofstatesinacell’sfinitestatem
8、achine,andk=
9、Σ
10、denotethenumberofstatespercell.Each1CAterminologydiffersamongdifferentauthors.Theterminologyinthischapterwillbeconsistentwithmostmodernwork.1Ruletablef:neighborhood:00000101001110010111011
