Cellular automata as a paradigm for ecological mod

CellularAutomataasaParadigmforEcologicalModelingP.HogewegBioinfnmuticaPaduulaan8Utrecht,TheNetherlandsABSTRACTWereviewcellularautomataasamodelingformalismanddiscusshowitcanbeusedformodeling(spatial)ecologicalprocesses.Theimplicationsofthismodelingparadigmforecologicalobservationarestressed.Finallywediscusssomeshortcom-ingsofthecellular-automatonformalismandmentionsomeextensionsandgeneraliza-tionswhichmayremedytheseshortcomings.1.INTRODUCTIONEcologicaltheorycomprisestwodisparateparts:onepartisconcernedwithprocesses(e.g.populationdynamics),andtheotherpartisconcernedwithspatialpatterns(e.g.communityecology).Thetwopartshavelittleincommon:thedynamicmodelspresupposehomogeneityandimmediateinfor-mationtransferbetweenthedifferentpopulations(orcompartments)andshouldthereforebeconsideredaspointmodelsthatdonothaveanyspatialextension.Thespatialmodelsdonotusuallyincludedynamicalprocesses.Thetimehascometotryandweldthetwopartstogetherbydevelopingatheoryof“dynamicecomorphology”(orecomorphologicaldynamics).Inotherwords,wewilltrytoincorporatespatialstructureinourdynamicmodels.Thecellular-automatonformalism(andextensionsthereof)seemstobeasuitableoneforthispurpose.2.CELLULARAUTOMATA2.1.IntroductionandHistoricalBackgroundAcellularautomatonisdefinedasalargetesselationofidenticalfinite-stateautomata(cells).Eachautomatonisdefinedasatriplet:(1,g,W),APPLIEDMATHEMATICSANDCOMPUTATION27:81-100(1988)OP.Hogeweg.1988.8182P.HOGEWEGwhereIisthesetofinputs,Sisasetofstates(bothsetsbeingfinite),andWisthenext-statefunction,definedoninput-statepairs.Thesetofinputsisdefinedasordered(ornonordered)n-tuplesofthestatesofafinitesetof“neighboring”cells.Thus,inatwo-dimensionalcellularautomatonthisneighborhoodconsiststypicallyoffouroreightcells,i.e.theadjacentcellsinasquaretesselation(theseneighborhoodsareoftenreferredtoastheMooreandvonNeumannneighborhoodsrespectively).Typicallytheautomataaresimpleinthesensethattheyhaveveryfewstates(generallynotmorethantwo).Forasmallneighborhoodthenext-statefunctionthereforeconsistsofafairlysmallnumberofrules(e.g.fortheMooreneighborhoodandtwostatesitconsistsofatmost25rules).Thesimplecellularautomataasdefinedabovearecapableofsurprisinglycomplexbehavior-complexbothintheformalsense(capableofuniversalcomputation)andintheintuitivesense(theygeneratefascinatingpatterns).Cellularautomatawerefirstdefinedandstudiedinthe1940s(see[6,511).ThemotivebehindthatworkwastostudyautomatawhichwerecloserinstructuretoactualinformationprocessingsystemsthantheusualidealizedlogicalnetsorTuringmachines[6].Well-knownworkinthisperiodincludesVonNeumann’sworkon“self-reproduction”andUlam’sworkon“cellularauxology”(1962,reprintedin[6]),whichpioneeredtheheuristicuseofcomputers.Eversince,cellularautomatahaveknownlongperiodsofdormancypunctuatedwithsuddenperiodsofenthusiasmandnewresults.Theseperiodscanbelinkedtothespreadofcomputerhardware.Atthebeginningofthe1970swhencomputersbecamegenerallyavailable,cellularautomatabecamepopularmainlyasaresultofConway’s(see[17])gameofLife:averysimplee-state&neighborhoodcellularautomatoncapableofuniversalcomputation(seee.g.[69,51.Nowthathugeparallelprocessorshavebecomepossible(andareinfactbeingbuilt-e.g.theC.A.M.[SS,671,~1x1~5000[75],andtheConnectionMachine[25,26]),thereisarevivalofinterest,theemphasisbeingmainlyonthemodelingofphysicalprocesses(e.g.fluiddynamics[47,67,611.2.2.ElementaryCellular-AutomatonTheory:MethodologyandResultsInthissectionwegiveashort,nonexhaustivesurveyofcellular-automatontheory.Themoststrikingfeatureofcellularautomataisthesimplicityoftheruleswhichproducecomplicatedbehavior.Mostcellular-automatontheoryisconcernedwiththissingleissue.Forelucidatingitoneeithertriestofindthe(most)simpleroleswhichproduceacertainpredefinedbehavior,oroneobservesthebehaviorofapredefinedsetofcellularautomataandtriestoclassifythebehaviorrelativetothetransitionfunctions.ThetwoapproachesCellularAutomataforEcologicalModeling83areofcoursenotindependent:resultsofthesecondapproachdefinebehaviorpatternswhichcanbestudiedbythefirstapproach.Thebest-knownresultsstemmingfromthefirst(top-down)approacharesummarizedbelow.(1)Universalcomputation.Verysimplecellularautomataarecapableofuniversalcomputation.ThegameofLife[rules:iftwoofyoureightneighborsare“on”(state1)donotchange,ifthreeare“on”,turnon;otherwiseturnoff]isthebest-knownexample,butevensimplerrulesarepossible([2]withfourneighbors;[77-791withone-dimensionalcellularautomata).Universalcomputationinthecontextofsuchverysimpleandseemingly“natural’systemshasreceivedmuchattentionandinfactacquiresasignificancewhichisnotsoapparentinthemore“artificial”Turingmachines.Theultimatefateof“ones”isundecidableandcanonlybeobtainedbydirectsimulation.Onlyifapatternbecomesapparentinsuchasimulation(whichitmaynot)canoneextrapolate;otherwiseonehasto“letitliveitslife.”Inotherwords:generalpredictionscannotbemadeforsuchsimpleandentirelydeterminis-ticsystems.Whenthenotionof“irreduciblecomputation”(i.e.,theresultscannotbecomputedfasterthanbythecellularautomatonitself)iscombinedwiththisnotionofunpredictability,oldparadoxesa