Cellular Automata Modeling of Chemical Systems A textbook and laboratory manual Lemont B. Kier, PhD ProfessorofMedicinalChemistry SeniorFellow,CSBC VirrginiaCommonwealthUniversity USA Paul G. Seybold, PhD ProfessorofChemistry WrightStateUniversity ExternalFellow,CSBC VirrginiaCommonwealthUniversity USA Chao-Kun Cheng, PhD AssociateProfessorofComputerScience FFFellow,CSBC VirrginiaCommonwealthUniversity ApublicationoftheCenterfortheStudyofBiologicalComplexity VirrginiaCommonwealthUniversity RichmondVirginia USA AC.I.P.CataloguerecordforthisbookisavailablefromtheLibraryofCongress. ISBN-10 1-4020-3657-4(HB) ISBN-13 978-1-4020-3657-6(HB) ISBN-10 1-4020-3690-6(e-book) ISBN-13 978-1-4020-3690-3(e-book) PublishedbySpringer, P.O.Box17,3300AADordrecht,TheNetherlands. www.springeronline.com (cid:1)C 2005Springer PrintedintheNetherlands. Contents Preface vii 1. ModelingNature 1 2. CellularAutomata 9 3. WaterasaSystem 39 4. SolutionSystems 57 5. DynamicAqueousSystems 73 6. Water-SurfaceEffects 87 7. First-OrderChemicalKinetics 109 8. Second-OrderChemicalKinetics 125 9. AdditionalApplicationsinChemicalKinetics 139 10. UseoftheCASimProgram 157 Index 169 Preface Over the past two decades there has been a significant growth in the use of computer-generatedmodelstostudydynamicphenomenainthenature.These studies have ranged over many of the fields of human endeavor. For example, insect behavior is a target for dynamic models; automobile traffic is another. Thesociologistshavepickeduponthepossibilitiesaffordedbycomputermod- elstostudydynamicsystems.Inthephysicalandbiologicalsciences,dynamic computermodelshavebeenusedtostudyavarietyofphenomena.Somestudies inchemistryhaveappearedintheliterature,butthefieldissovastthatonlya smallareahasbeenconsideredforcomputermodeling.Inourviewchemistry is ripe for studies utilizing this paradigm. The study of chemistry is usually focused on changes; we establish a structure, a form, but it is of real interest wwwhen we consider how and to what it is transformed. Laboratory studies in schoolsintroducethestudenttosimpleprocessesthatalwayswork.Morecom- plex transformations are difficult to set up as experiments; they often do not “work”andsothedidacticvalueofsuchexperiencesismarginal. Itisourpurposeinthisbooktoexploreandrevealhowsomecomputermod- elsmightenrichthepracticalexperiences,traditionallycarriedoutin“wet”labs. We pursue this goal using one of the modeling schemes that was developed a halfcenturyago:cellularautomata.Therecordofcellularautomataasamodel- ingparadigmisrevealedintheliterature.Wehaveusedcellularautomatainour research for a decade, modeling solution and kinetic phenomena of chemical systems. We feel that this approach can bring new meaning to experimental chemistry in the form of in silico experiments. This book is dedicated to that objective. Thebookisorganizedintothreesections.Inthefirstsectionweintroduce the student to some of the concepts that are fundamental to an understanding of chemical phenomena. These include a look at the subject of complexity. Imbedded in these concepts are general chemical phenomena such as self- organization,emergentproperties,andlocalinteractions.Thissectionsetsthe stage for a look at some of the modeling techniques used to explore complex systems. In the second section we present a brief overview of some currently used dynamicmodelingmethodsbeforeintroducingcellularautomata.Afterabrief history of this method we describe the ingredients that drive the dynamics exhibited by cellular automata. These include the platform on which cellular automataplaysoutitsmodeling,thestatevariablesthatdefinetheingredients, andtherulesofmovementthatdevelopthedynamics.Eachstepinthissection is accompanied by computer simulation programs carried on the CD in the backofthebook. WWWith this background the student is then equipped to witness what has been done in chemistry using cellular automata models. These studies are accompanied by unfinished studies and challenges, “what if” ideas for the student.Thelaboratoryinageneralchemistrycourseisanidealplacetousethis approach since it brings to the student views of many phenomena, previously difficult to visualize. As an adjunct to experimental work in the lab, it opens up a new level of understanding. It may even pique interest in pursuing new theoreticalinvestigationsinchemistry. Atanearfinalstageofwritingthisbook,wehadagoldenopportunitytotest themodelingexercises.SevenstudentsintheIntegratedLifeSciencesgraduate programattheVirginiaCommonwealthUniversitywereaskedtoreadthetext and to perform many of the examples and studies. Their experiences were of immensevaluetousinfinalizingthemanuscript.Wewanttoacknowledgethem and thank them for their efforts. They are Xiangrong Kong, Julie Naumann, JeanNelson,AntoineNicolas,ElizabethProm,AlexanderTulchinsky,andCarl Zimmerman.WealsowanttothankYingjinCuiforherhelpincreatingsomeof thefigures.TheauthorsthankMarcoTomassiniforearly,helpfulreviewsofthe manuscript.WethankEnguangZhaoforhishelpinpreparingtheJavaversion oftheCAprogram.Finallyweacknowledgethescholarlyclimateandencour- agementgiventousattheCenterfortheStudyofBiologicalComplexityatthe VirginiaCommonwealthUniversity. LemontB.Kier PaulG.Seybold Chao-KunCheng Chapter 1 MODELING NATURE Thechess-boardistheworld;thepiecesarethephenomenaoftheuniverse; the rules of the game are what we call the laws of Nature. The player on the othersideishiddenfromus.Butweknowthathisplayisalwaysfair,just,and patient. But also we know to our cost, that he never overlooks a mistake, or makesthesmallestallowanceforignorance. —ThomasHuxley It is the role, and the privilege, of a scientist to study Nature and to seek to unlock her secrets. To unlock these secrets, a certain process is customarily taken. Normally, the scientific process starts with observations; the scientist observes some part of the natural world and attempts to find patterns in the behaviorsobserved.Thesepatterns,whentheyareuncoveredoutofwhatmay otherwise be a quite complicated set of events, are then called the “laws” of behavior for the particular part of nature that has been scrutinized. But the processdoesnotstopthere.Scientistsarenotcontentmerelytoobservenature andcatalogherpatterns—theyseekexplanationsforthepatterns.Thepossible explanationsthatscientistsproposetaketheformofhypothesesandtheories— “models”—about how things work behind the scenes of outside appearance. Thisbookisaboutonesuchtypeofmodelandhowitcanbeusedtounderstand thepatternsofchemistry. Butwhatdowemeanbya“model”?Amodelisasubstitute,usuallygreatly simplified,forwhattheearlyquantumphysicistscalledtheDingansich—the “thing itself,” the real thing. The mathematician Jacob Bronowski spoke of models as metaphors, likenesses that we snatch from the larger world of eye and ear and touch. [1] A model should simulate or imitate the real system and display in some revealing way its most important or interesting features; wwwherepossibleitshouldcapturetheessenceofthesystemwithoutbeingoverly cumbersomeorcomplicated.SciencewriterGeorgeJohnson[2]hasdescribed thenatureofasuccessfulsimulation: 2 Chapter1 The mark of a good simulation is that it separates the essential from the incidental,cuttingthroughwhatisdeemedirrelevantdetailtogetattheheart oftheproblem. Many models in the physical sciences take the form of mathematical rela- tionships, equations connecting some property with other parameters of the system. Some of these relationships are quite simple, e.g., Newton’s sec- ond law of motion, which says that force = mass × acceleration: F = ma. Newton’s gravitational law for the attractive force F between two masses m 1 andm alsotakesarathersimpleform 2 F = Gm m /r2 1 2 wwwherer2isthesquareofthedistanceseparatingthemassesandGisaconstant thatrationalizestheunits.Butmanymathematicalrelationshipsaremuchmore complicated and rely on the techniques of calculus to describe the rates of changeofthequantitiesinvolved.Anexampleisthebasicequationofquantum theory,theSchro¨¨dingerequation,whichtakesthemoreformidableform(itis notnecessaryheretodwellonthemeaningsofthesymbols): (cid:1) (cid:2) −hhh–2 ∂2 ∂2 ∂2 + + ψ +Vψ = Eψ 2m ∂x2 ∂y2 ∂z2 Inchemicalkinetics,onefindslinkedsetsofdifferentialequationsexpressing the rates of change of the interacting species. Overall, mathematical models have been exceedingly successful in depicting the broad outlines of an enor- mously diverse variety of phenomena in nature. Some scientists have even commentedinsurpriseathowwellmathematicsworksindescribingnature.So successfulhavethesemathematicalmodelsbeenthattheirusehasspreadfrom thehardsciencestoareasasdiverseaseconomicsandtheanalysisofathletic performance[3]. Inothercases,modelstakeamorepictorialform.Intheearlyatomicmodels, anatomwasfirstpicturedbyJ.J.Thomsonasa“plumpudding,”withnegative electrons(the“plums”)embeddedinaspread-outpositivecharge(thepudding), andthenlaterbyErnestRutherfordandNielsBohrasaplanetarysystemwitha tinypositivecoresurroundedbycirclingelectrons,amodelcalledthe“nuclear atom.”Today,withinquantumtheory,thenuclearatompicturehasbeenfurther transformedintoonewithapositivenucleussurroundedbyacloudofelectron probabilities.Inbiology,thedoublehelixmodelofthestructureofthegenetic material DNA proposed by James Watson and Francis Crick in 1953 led to an explosion of studies in the field of molecular genetics. Charles Darwin’s model of evolution by means of natural selection pictures species composed of a collection of individuals with a variety of different traits interacting with theirenvironments.Individualswithsometraitsarebettersuitedtosurviveand 1.ModelingNature 3 reproduce, thereby passing on these traits to their offspring. Over time new traitsareintroducedthroughmutations,environmentsgradually(orsometimes rapidly)change,andnewformsdevelopfromtheoldones.Themodernmodel of the human brain envisions regions devoted to different functions such as sight,motormovements,andhigherthoughtprocesses.Ingeology,thetectonic platemodeloftheEarthpicturesexpansivecontinentalplatesmovinggradually overtheplanet’ssurfacegeneratingearthquakesastheymeetandslideoverone another.Andinpsychology,theFreudianapproachpictureshumanbehavioras resulting from the actions of invisible components of the mind termed the id, theego,andthesuperego. Thekeyfeatureofsuccessfulmodelsisthattheyproduceresultsconsistent with the experimental observations. Successful models capture the essential featuresofthesystemsofinterest,andtheycustomarilygobeyondthissimple reproduction to predict new features of the systems that may have previously escapednotice.Inthislattercase,thepredictionsprovideanimportantmeans fortestingthevalidityofthemodels. Atthispoint,itishelpfultodissectmodelsintotheirmostsignificantparts sothatwecanstartfromacommonbasis. 1.1. The system Studiesinchemistryoranyrealmofsciencecommonlyconsistofaseries ofdirectedexaminationsofpartsofnature’srealmcalledsystems.Asystemis anidentifiablefragmentoftheworldthatisrecognizableandthathasattributes thatonecanidentifyintermsofformand/orfunction.Wecangiveexamplesat anylevelofsizeandcomplexityandinessentiallyanycontext.Indeed,adogis asystematapetshow;whereasthehumanheartisasystemtothecardiologist; atumorcellisasystemtothecancerspecialist;astarorplanetorgalaxyisa systemtoanastronomer;amoleculeoracollectionofmoleculesisasystemto achemist;andanatomorgroupofatomsisasystemtoaphysicist.Asystem is,then,whateverwefocusourattentionuponforstudyandexamination. 1.2. States of the system A system is composed of parts that can be recognized and identified. As timegoesby,asystemunderstudymayacquiredifferentattributesasaresultof changesamongitsparts,andovertimeitsappearanceorfunctionmaychange. Eachofthedifferentstagesthroughwhichthesystempassesinitsevolutionis calledastateofthesystem.Adoggrowsoldovertime,passingthroughstages recognized in general terms as puppy, dog, old dog, and, finally, dead dog. A heartmaychangeitspatternofcontractions,goingfromnormaltotachycardia 4 Chapter1 to ventricular fibrillation, each of which we categorize as a different state of functioning. A solution of ethyl acetate in water may slowly decompose to mixturesofethylacetate,aceticacid,andethanol,throughasequenceofstates characterizedbytheirdifferentcompositions.Watermaystartasasolid(ice), become a cool liquid, then a warmer liquid, and finally appear as a vapor at highertemperature,passingthroughthesedifferentstagesasitismelted,heated, andvaporized.Werefertoeachsetofconditionsforthepresentpurposesasa “state.”Itisthevariousstatesofthesystemthatwefocusattentionuponwhen westudyanysystem. 1.3. Observables Our studies require us to analyze and describe the changes that occur in the systems we are interested in that evolve with time. To accomplish this analysis properly, we need to record specific features that characterize what is occurring. The features assigned for this purpose are termed observables. For example, we distinguish the puppy from the old dog by the changes in its physical appearance and its behavior. The changes in a heart’s rhythm are recordedonspecialchartsmonitoringelectricalsignals.Thechangesoccurring in a solution of ethyl acetate in water can be characterized by changes in the solution’sacidity,byspectroscopicreadings,orbydetectionoftheodorofacetic acid. To be as precise as possible in a scientific investigation, it is necessary to assign numerical values to the characteristics that distinguish one state of asystemfromanother.Thestateofasystemisstudiedthroughdetectionand recordingofitsobservables. 1.4. Interactions Thepartsofasystemnaturallyinteractwithoneanother,andthefascinating andoftencomplexevolutionsofnaturalsystemsdependcruciallyonthenature oftheseinteractions.Theinteractionssupplythedrivingforcesforthechanges that we observe in the systems. In addition, we can change the behavior of a system by introducing new elements or ingredients. Intrusions of this kind producenewinteractions,whichinturnalterthesystem.Bycarefullychoosing theaddedfactorsandinteractions,wecandevelopnewpatternsofobservables that may be revealing. Interaction with your dog might include exercising to increasehisrunningstamina,whichinturnwillleadtoanew,improvedsetof health-related(state)indicators.Electricalstimulationofafibrillatingheartcan introduceinteractionsthatleadtotheconversionoftheheartfromthefibrillating statetoanormal,healthystateofperformance.Heatingtheethylacetatesolution will eventually complete the hydrolysis reaction and distill away the resulting 1.ModelingNature 5 ethanol leaving a solution of acetic acid. The interactions introduced and the accompanyingchangesinthesystems’observablesproduceinformationabout thenatureofthesystemsandtheirbehaviorsunderdifferentconditions.With enoughobservables,wemaybeabletopiecetogetherareasonabledescription, amodel,forhowthesystemoperates. 1.5. Back to models From a carefully selected list of experiments with a system, we can evoke certain conclusions. The mosaic of information leads us to piece together a description of the system, what is going on inside it, the relationships among its states, and how these states change under different circumstances. In the case of our dog, the exercise tests may lead us to theorize that the dog is in goodorpoorhealth.Withtheheart,theelectricalimpulsesthatwerecordcan reveal a pattern of changes (observables) that we theorize belong to a healthy (or diseased) heart. By subjecting the solution of hydrolyzing chemicals to fractionaldistillationandchemicalanalysis,wemaytheorizethatweoriginally hadasystemofwaterandethylacetate. We can arrive at our theories in two main ways. In the first, as illustrated earlier,wesubjectasystemtoexperimentalperturbations,tests,andintrusions, therebyleadingtopatternsofobservablesfromwhichwemayconcoctatheory ofthesystem’sstructureandfunction.Analternativeapproach,madepossible bythedramaticadvancesthathaveoccurredintheareaofcomputerhardware in recent times, is to construct a computer model of the system and then to carryoutsimulationsofitsbehaviorunderdifferentconditions.Thecomputer “experiments”canleadtoobservablesthatmaybeinterpretedasthoughthey werederivedfrominteractions. 1.6. Simulations It is important to recognize the different concepts conveyed by the terms “model”and“simulation,”eventhoughthesetermsaresometimesusedinter- changeably.Asnotedabove,amodelisageneralconstructinwhichtheparts ofasystemandtheinteractionsbetweenthesepartsareidentified.Themodel is necessarily simpler than the original system, although it may itself take on a rather complicated form. It consists of ingredients and proposals for their interactions. Simulationsareactiveimitationsofrealthings,andtherearegenerallytwo differenttypesofsimulationswithdifferentaims.Inoneapproach,asimulation ismerelydesignedtomatchacertainbehavior,ofteninaverylimitedcontext. Thus, a mechanical noisemaker may simulate a desired sound and does so