CELLULAR AUTOMATA AND APPLICATIONS

CELLULARAUTOMATAANDAPPLICATIONSGAVINANDREWS1.IntroductionThispaperisastudyofcellularautomataascomputationalprogramsandtheirremarkableabilitytocreatecomplexbehaviorfromsimplerules.Weexamineanumberofthesesimpleprogramsinordertodrawconclusionsaboutthenatureofcomplexityseenintheworldanddiscussthepotentialofusingsuchprogramsforthepurposesofmodeling.TheinformationpresentedwithinisinlargeparttheworkofmathematicianStephenWolfram,aspresentedinhisbookANewKindofScience[1].Section2beginsbyintroducingone-dimensionalcellularautomataandthefourclassicationsofbehaviorthattheyexhibit.Insections3and4theconceptofcomputationaluniversalitydiscoveredbyAlanTuringintheoriginalTuringmachineisintroducedandshowntobepresentinvariouscellularautomatathatdemonstrateClassIVbehav-ior.Theideaofcomputationalcomplexityasitpertainstouniversalityanditsimplicationsformodernsciencearethenexamined.Insection12GAVINANDREWS5wediscussthechallengesandadvantagesofmodelingwithcellularautomata,andgiveseveralexamplesofcurrentmodels.2.CellularAutomataandClassificationsofComplexityTheone-dimensionalcellularautomatonexistsonaninnitehori-zontalarrayofcells.Forthepurposesofthissectionwewilllookattheone-dimensionalcellularautomata(c.a.)withsquarecellsthatarelimitedtoonlytwopossiblestatespercell:whiteandblack.Thec.a.'srulesdeterminehowtheinnitearrangementofblackandwhitecellswillbeupdatedfromtimesteptotimestep.Again,forthepurposesofthissection,wewilllookatc.a.'swhoserulesareupdatedbasedonanearestneighborscheme.Thismeansthattodeterminethestateofacellinpositionpattimestept+1,wewilllookatthestatesofcellsinpositionp1,p,andp+1allintimestept.Foreachoftheeightpossiblepatternsofwhiteandblackcells,thestateofcellpattimestept+1ischosenaseitherblackorwhite.SeeFigure1fortheeightpossibleinputpatterns,aswellasonepossibleoutput.Inallthereare256dierentpossibleoutputs.CELLULARAUTOMATAANDAPPLICATIONS3Figure1.Alongthetoparetheeightpossiblepatternsofthree,two-statecells.Theyaredisplayedinthecon-ventionallefttorightorderinthisgure.Thebottomisonepossiblesetofoutputs.Inall,thereare256dierentpossibleoutputs.ThisimageisscannedfromWolfram[1],page53.ToanalyzethebehavioroftheseprogramsWolframdevelopedanamingconvention,astandardinitialconditionandmethodofview-ingtheresultsofmultipleiterationsatonce.Tonamethebasicone-dimensionalc.a.'sdescribedabove,ahierarchywasgiventoeightpos-siblepatternswithblack-black-blackonthefarleftandwhite-white-whiteonethefarright.Eachcombinationwasmadetorepresentaplaceinthebinarynumberingsystem.Black-black-blackforexamplewasrepresentsthe27thplace.Assigningthevalueofzerotowhiteandonetoblackgiveseachofthepossiblearrangementsofupdatingscenariosabinarynumberthatrangesfrom0to255inbaseten.SeeFigure2forseveralexamplesofthisnamingscheme.Theinitialconditionsforalltherules,0-255consistofoneblackcellwithraysofwhitecellsextendingtoinnityonbothsides.Toviewmultipleiterationsatonce,eachtimestepisplacedbelowthepreviousonewiththepositionsofeachcellunchanging,forexampleseeFigure3.Thiscreatesatwo-dimensionalimageofmultipleiterationsofac.a.4GAVINANDREWSFigure2.Thesearetherstthreerulesandthelastone.Thesequenceofzerosandonesarebinarynumberswiththeirbasetenequivalentlabeledtotherightofeachsequence.Wolfram,page53.allowingforanalysisofbehavior.Itshouldbenotedthatthemaximumrateoftraveloftheblacksquareinthemiddleisonelateralsquareperiteration.Wolframclassiesthebehaviorobservedinthesec.a.'sinfourdis-tinctclasses.TherstisClassI,whichcontainssimplerepeatingbehavior.Thiscanrangefromasingleverticalordiagonalline(theinitialconditionsremain)asinrules100andrule106,oraseriesofalternatingallwhiteandallblackiterationsasinrules119and21.SeeFigure3,images(a)and(b)ofrule106and119respectivelyforexamplesofClassIbehavior.ThebehavioriseasilyrecognizableasCELLULARAUTOMATAANDAPPLICATIONS5(a)(b)(c)Figure3.Aboveare16iterationsofrules106,119,and126.Rule106and119areexamplesofClassIbehavior,and126isoneofClassIIbehavior.Wolfram,page54.containingrepetitiveelementsofequalsizethatencompassthewholeprogram.Approximately86%ofthe256basicc.a.'sareofthisclass.Thesecondclassofbehavior,ClassII,ischaracterizedbyc.a'sthathavenestedpatterns.Anestedpatternisacongurationthatrepeatsitselfonaneverincreasingscale.Thatis,smallerscalerepresentationsofaselectedregionoccurwithintheregionitself.Approximately9%ofthebasicc.a.'sareofthisclass.SeeFigure3,(c)foranimageofaClassIInestedpatterninrule126.ClassIIIbehavioriscompletelyrandom.Thec.a.'sinthisclasshaveshapesthatrepeatthemselves,buttheirlocationandfrequencyisrandom.Thisclasscontainsabout4%ofthebasicc.a.'s.Thenalclass,ClassIVbehavior,isacombinationofClassIbehav-iorandClassIIIbehavior.Thesec.a.'sexhibitacomplexcombinationofrepeatingpatternsandrandombehavior.SeeFigure4foranexam-ple.Thereareonly4outofthe256basicc.a.'sthatexhibitthisbehav-ior,andallfourareessentiallythesamewhenweconsiderblack-white6GAVINANDREWSFigure4.Aboveisanimageof150iterationsofrule110anditsupdatingrules.Wolfram,page32.symmetryandleft-rightsymmetry.Twoofthemaremirrorimagesofeachother,ippedovertheverticalaxisplacedat