ARTIFICIAL CHEMISTRIES ARTIFICIAL CHEMISTRIES WolfgangBanzhafandLidiaYamamoto TheMITPress Cambridge,Massachusetts London,England ©2015MassachusettsInstituteofTechnology Allrightsreserved.Nopartofthisbookmaybereproducedinanyformbyanyelectronicormechanicalmeans(including photocopying,recording,orinformationstorageandretrieval)withoutpermissioninwritingfromthepublisher. MITPressbooksmaybepurchasedatspecialquantitydiscountsforbusinessorsalespromotionaluse.Forinformation, [email protected] ThisbookwassetinNewTimesRomanusingtheLaTeX—Memoirclass. PrintedandboundintheUnitedStatesof America. LibraryofCongressCataloging-in-PublicationData Banzhaf,Wolfgang,1955— Artificialchemistries/WolfgangBanzhafandLidiaYamamoto. Includesbibliographicalreferencesandindex. ISBN978-0-262-02943-8(hardcover:alk. paper)1. Biochemistry. 2. Molecularevolution. 3. Chemistry,Physicaland theoretical.4.Evolution(Biology)5.Life—Origin.I.Yamamoto,Lidia.II.Title. QD415.B242015 572—dc23 2014046071 10 9 8 7 6 5 4 3 2 1 artificial,a.,contrivedbyartratherthannature:”artificialflowers”; http://www.thefreedictionary.com/artificial,accessed2014 Madeorproducedbyhumanbeingsratherthanoccurringnaturally,typicallyasa copyofsomethingnatural. https://www.google.ca,accessed2014 chemistry,n.,abranchofphysicalsciencethatstudiesthecomposition,structure, propertiesandchangeofmatter,[fromGreek:χημ(cid:4)ια], http://en.wikipedia.org/wiki/Chemistry,accessed2014 Theinvestigationofsubstances,theirpropertiesandreactions,andtheuseofsuch reactionstoformnewsubstances. http://www.oxforddictionaries.com/definition/english/chemistry,accessed2014 CONTENTS Preface xi I Foundations 1 1 Introduction 3 2 BasicConceptsofArtificialChemistries 11 2.1 ModelingandSimulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2 ChemistryConcepts. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3 GeneralStructureofanArtificialChemistry . . . . . . . . . . . . . . . . . . . . . 25 2.4 AFewImportantDistinctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.5 TwoExamples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.6 FrequentlyUsedTechniquesinACs . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3 TheMatrixChemistryasanExample 45 3.1 TheBasicMatrixChemistry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.2 TheSimplestSystem,N=4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.3 TheSystemN=9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.4 SystemswithLargerN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 4 ComputingChemicalReactions 63 4.1 FromMacroscopictoMicroscopicChemicalDynamics. . . . . . . . . . . . . . 63 4.2 StochasticReactionAlgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 4.3 SpatialandMulticompartmentalAlgorithms . . . . . . . . . . . . . . . . . . . . 71 4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 II LifeandEvolution 75 5 TheChemistryofLife 77 5.1 WhatIsLife? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 5.2 TheBuildingBlocksofLife . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 5.3 TheOrganizationofModernCells . . . . . . . . . . . . . . . . . . . . . . . . . . 93 5.4 MulticellularOrganisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 5.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 viii CONTENTS 6 TheEssenceofLife 111 6.1 AMinimalCell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 6.2 OriginofLife . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 6.3 ArtificialChemistryContributionstoOriginofLifeResearch. . . . . . . . . . . 130 6.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 7 Evolution 139 7.1 Evolution:TamingCombinatoricstoImproveLife . . . . . . . . . . . . . . . . . 140 7.2 EvolutionaryDynamicsfromanACPerspective . . . . . . . . . . . . . . . . . . 141 7.3 ArtificialChemistriesforEvolution . . . . . . . . . . . . . . . . . . . . . . . . . . 154 7.4 SummaryandOpenIssues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 8 ComplexityandOpen-EndedEvolution 159 8.1 Evolution:SteeringSelf-OrganizationandPromotingInnovation . . . . . . . . 159 8.2 CoevolutionaryDynamicsinEcologies . . . . . . . . . . . . . . . . . . . . . . . 161 8.3 RobustnessandEvolvability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 8.4 ComplexityGrowth . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 8.5 TowardOpen-EndedArtificialEvolution . . . . . . . . . . . . . . . . . . . . . . . 175 8.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 III ApproachestoArtificialChemistries 179 9 RewritingSystems 181 9.1 LambdaCalculus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 9.2 Gamma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184 9.3 TheChemicalAbstractMachine . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 9.4 ChemicalRewritingSystemonMultisets . . . . . . . . . . . . . . . . . . . . . . 187 9.5 Psystems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 9.6 MGS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 9.7 OtherFormalCalculiInspiredbyaChemicalMetaphor . . . . . . . . . . . . . . 193 9.8 L-SystemsandOtherRewritingSystems . . . . . . . . . . . . . . . . . . . . . . . 193 9.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194 10 AutomataandMachines 195 10.1 FiniteStateAutomata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196 10.2 TuringMachines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 10.3 VonNeumannMachines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198 10.4 CellularAutomata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200 10.5 ExamplesofArtificialChemistriesBasedonTuringMachines . . . . . . . . . . 202 10.6 ArtificialChemistriesBasedonvonNeumannMachines . . . . . . . . . . . . . 207 10.7 ArtificialChemistriesBasedonCellularAutomata . . . . . . . . . . . . . . . . . 215 10.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 11 Bio-inspiredArtificialChemistries 225 11.1 String-BasedArtificialChemistries . . . . . . . . . . . . . . . . . . . . . . . . . . 225 11.2 Lock-and-KeyArtificialChemistries . . . . . . . . . . . . . . . . . . . . . . . . . 234 11.3 Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240 11.4 SpatialStructuringandMovementinArtificialChemistries . . . . . . . . . . . 248 11.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254 CONTENTS ix IV OrderConstruction 255 12 TheStructureofOrganizations 257 12.1 BasicDefinitions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259 12.2 Generators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262 12.3 BringingOrderintoOrganizations . . . . . . . . . . . . . . . . . . . . . . . . . . 263 12.4 NoveltyandInnovation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265 12.5 ExamplesoftheStaticsofOrganizations . . . . . . . . . . . . . . . . . . . . . . . 266 12.6 HowtoCalculateClosedandSelf-MaintainingSets . . . . . . . . . . . . . . . . 270 12.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273 13 TheDynamicsofOrganizations 275 13.1 Flows,StoichiometryandKineticConstants . . . . . . . . . . . . . . . . . . . . 275 13.2 ExamplesoftheDynamicsofOrganization . . . . . . . . . . . . . . . . . . . . . 277 13.3 ObservingOrganizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282 13.4 ProbabilisticNotionsofClosureandSelf-Maintenance . . . . . . . . . . . . . . 283 13.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285 14 Self-OrganizationandEmergentPhenomena 287 14.1 ExamplesofSelf-OrganizingSystems. . . . . . . . . . . . . . . . . . . . . . . . . 288 14.2 ExplanatoryConceptsofSelf-Organization . . . . . . . . . . . . . . . . . . . . . 289 14.3 TheEmergenceofPhenomena . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295 14.4 ExplanatoryConceptsofEmergence . . . . . . . . . . . . . . . . . . . . . . . . . 298 14.5 EmergenceandTop-DownCausation . . . . . . . . . . . . . . . . . . . . . . . . 304 14.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306 15 ConstructiveDynamicalSystems 307 15.1 Novelty,Innovation,Emergence. . . . . . . . . . . . . . . . . . . . . . . . . . . . 307 15.2 BirthProcessesattheSameLevel . . . . . . . . . . . . . . . . . . . . . . . . . . . 309 15.3 TheEmergenceofEntitiesonaHigherLevel . . . . . . . . . . . . . . . . . . . . 317 15.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319 V Applications 321 16 ApplicationsofArtificialChemistries 323 16.1 RobotsControlledbyArtificialChemistries . . . . . . . . . . . . . . . . . . . . . 324 16.2 ACsforNetworking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330 16.3 LanguageDynamicsandEvolution . . . . . . . . . . . . . . . . . . . . . . . . . . 334 16.4 MusicCompositionUsingAlgorithmicChemistries . . . . . . . . . . . . . . . . 338 16.5 ProofSystems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339 16.6 ArtificialChemistryandGeneticProgramming . . . . . . . . . . . . . . . . . . . 340 16.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344 17 ComputingwithArtificialChemistries 345 17.1 Principlesofimplementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346 17.2 SearchandOptimizationAlgorithmsInspiredbyChemistry . . . . . . . . . . . 355 17.3 DistributedAlgorithmsUsingChemicalComputing . . . . . . . . . . . . . . . . 358 17.4 InSilicoSimulationofWetChemicalComputing. . . . . . . . . . . . . . . . . . 366 17.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372