Preface ........................................................ xi
I Foundations .................................................. 1
1 Introduction ................................................. 3
2 Basic Concepts of Artificial Chemistries .................... 11
2.1 Modeling and Simulation ................................ 11
2.2 Chemistry Concepts ..................................... 15
2.3 General Structure of an Artificial Chemistry ........... 25
2.4 A Few Important Distinctions ........................... 31
2.5 Two Examples ........................................... 33
2.6 Frequently Used Techniques in ACs ...................... 38
2.7 Summary ................................................ 43
3 The Matrix Chemistry as an Example .......................... 45
3.1 The Basic Matrix Chemistry ............................. 46
3.2 The Simplest System, N = 4 ............................. 50
3.3 The System N = 9 ....................................... 55
3.4 Systems with Larger N .................................. 59
3.5 Summary ................................................ 61
4 Computing Chemical Reactions ................................ 63
4.1 From Macroscopic to Microscopic Chemical Dynamics ...... 63
4.2 Stochastic Reaction Algorithms ......................... 65
4.3 Spatial and Multicompartmental Algorithms .............. 71
4.4 Summary ................................................ 73
II. Life and Evolution ......................................... 75
5 The Chemistry of Life ....................................... 77
5.1 What Is Life? .......................................... 79
5.2 The Building Blocks of Life ............................ 80
5.3 The Organization of Modern Cells ....................... 93
5.4 Multicellular Organisms ............................... 100
5.5 Summary ............................................... 109
6 The Essence of Life ........................................ 111
6.1 A Minimal Cell ........................................ 111
6.2 Origin of Life ........................................ 119
6.3 Artificial Chemistry Contributions to Origin of Life
Research .............................................. 130
6.4 Summary ............................................... 136
7 Evolution .................................................. 139
7.1 Evolution: Taming Combinatorics to Improve Life ....... 140
7.2 Evolutionary Dynamics from an AC Perspective .......... 141
7.3 Artificial Chemistries for Evolution .................. 154
7.4 Summary and Open Issues ............................... 157
8 Complexity and Open-Ended Evolution ........................ 159
8.1 Evolution: Steering Self-Organization and Promoting
Innovation ............................................ 159
8.2 Coevolutionary Dynamics in Ecologies .................. 161
8.3 Robustness and Evolvability ........................... 165
8.4 Complexity Growth ..................................... 169
8.5 Toward Open-Ended Artificial Evolution ................ 175
8.6 Summary ............................................... 177
III. Approaches to Artificial Chemistries ..................... 179
9 Rewriting Systems .......................................... 181
9.1 Lambda Calculus ....................................... 182
9.2 Gamma ................................................. 184
9.3 The Chemical Abstract Machine ......................... 186
9.4 Chemical Rewriting System on Multisets ................ 187
9.5 P systems ............................................. 188
9.6 MGS ................................................... 191
9.7 Other Formal Calculi Inspired by a Chemical Metaphor .. 193
9.8 L-Systems and Other Rewriting Systems ................. 193
9.9 Summary ............................................... 194
10 Automata and Machines ...................................... 195
10.1 Finite State Automata ................................. 196
10.2 Turing Machines ....................................... 197
10.3 Von Neumann Machines .................................. 198
10.4 Cellular Automata ..................................... 200
10.5 Examples of Artificial Chemistries Based on Turing
Machines .............................................. 202
10.6 Artificial Chemistries Based on von Neumann Machines .. 207
10.7 Artificial Chemistries Based on Cellular Automata ..... 215
10.8 Summary ............................................... 222
11 Bio-inspired Artificial Chemistries ........................ 225
11.1 String-Based Artificial Chemistries ................... 225
11.2 Lock-and-Key Artificial Chemistries ................... 234
11.3 Networks .............................................. 240
11.4 Spatial Structuring and Movement in Artificial
Chemistries ........................................... 248
11.5 Summary ............................................... 254
IV. Order Construction ........................................ 255
12 The Structure of Organizations ............................. 257
12.1 Basic Definitions ..................................... 259
12.2 Generators ............................................ 262
12.3 Bringing Order into Organizations ..................... 263
12.4 Novelty and Innovation ................................ 265
12.5 Examples of the Statics of Organizations .............. 266
12.6 How to Calculate Closed and Self-Maintaining Sets ..... 270
12.7 Summary ............................................... 273
13 The Dynamics of Organizations .............................. 275
13.1 Flows, Stoichiometry and Kinetic Constants ............ 275
13.2 Examples of the Dynamics of Organization .............. 277
13.3 Observing Organizations ............................... 282
13.4 Probabilistic Notions of Closure and Self-
Maintenance ........................................... 283
13.5 Summary ............................................... 285
14 Self-Organization and Emergent Phenomena ................... 287
14.1 Examples of Self-Organizing Systems ................... 288
14.2 Explanatory Concepts of Self-Organization ............. 289
14.3 The Emergence of Phenomena ............................ 295
14.4 Explanatory Concepts of Emergence ..................... 298
14.5 Emergence and Top-Down Causation ...................... 304
14.6 Summary ............................................... 306
15 Constructive Dynamical Systems ............................. 307
15.1 Novelty, Innovation, Emergence ........................ 307
15.2 Birth Processes at the Same Level ..................... 309
15.3 The Emergence of Entities on a Higher Level ........... 317
15.4 Summary ............................................... 319
V. Applications ............................................... 321
16 Applications of Artificial Chemistries ..................... 323
16.1 Robots Controlled by Artificial Chemistries ........... 324
16.2 ACs for Networking .................................... 330
16.3 Language Dynamics and Evolution ....................... 334
16.4 Music Composition Using Algorithmic Chemistries ....... 338
16.5 Proof Systems ......................................... 339
16.6 Artificial Chemistry and Genetic Programming .......... 340
16.7 Summary ............................................... 344
17 Computing with Artificial Chemistries ...................... 345
17.1 Principles of implementation .......................... 346
17.2 Search and Optimization Algorithms Inspired by
Chemistry ............................................. 355
17.3 Distributed Algorithms Using Chemical Computing ....... 358
17.4 InSilico Simulation of Wet Chemical Computing ......... 366
17.5 Summary ............................................... 372
18 Modeling Biological Systems ................................ 373
18.1 Folding Algorithms .................................... 374
18.2 Basic Kinetics of Bio molecular Interactions .......... 379
18.3 Biochemical Pathways .................................. 383
18.4 Modeling Genetic Regulatory Networks .................. 391
18.5 Cell Differentiation and Multicellularity ............. 396
18.6 Morphogenesis ......................................... 398
18.7 Summary ............................................... 403
19 Wet Artificial Chemistries ................................. 405
19.1 Artificial Building Blocks of Life .................... 405
19.2 Synthetic Life and Protocells ......................... 411
19.3 Chemical and Biochemical Computation .................. 417
19.4 In Vivo Computing with Bacteria and Other Living
Organisms ............................................. 431
19.5 Ethical Issues ........................................ 435
19.6 Summary ............................................... 437
20 Beyond Chemistry and Biology ............................... 439
20.1 Mechanical Self-Assembly .............................. 439
20.2 Nuclear and Particle Physics .......................... 442
20.3 Economic Systems ...................................... 444
20.4 Social Systems ........................................ 446
20.5 Summary ............................................... 448
VI. Conclusions ............................................... 449
21 Summary and Perspectives ................................... 451
21.1 Some Common Criticisms of the Artificial Chemistry
Approach .............................................. 451
21.2 Delimiting the Borders of the Field ................... 453
21.3 Main Features of Artificial Chemistries ............... 456
21.4 Conclusion ............................................ 459
Further Reading ............................................... 461
Appendix: Setting up Your Own Artificial Chemistry System ..... 465
The PyCellChemistry Package ................................... 465
Writing Your Own Artificial Chemistry in Python ............... 468
Further Resources ............................................. 478
Bibliography .................................................. 481
Author Index .................................................. 531
Subject Index ................................................. 545
|
