Complexity and Emergence NotesBiologyComputer Science / Artificial SystemsJohn Holland – the “Father” of genetic algorithmsEarly Neural Network SimulationCheckersplayerGenetic algorithmsCellular Automata, Conway’s “Life”Demonstrates a surprising amount of emergence, including the ability to design a pattern that interacts so as to form a general-purpose computer. [Demo gliders.]TermsComplexity and Emergence NotesBiologyLife - entropy in reverse; matter natural tending toward increasing orderEntropy (and thermodynamics in general) rules static systems – dead systems. When there is an energy flux, the situation gets more complicated, literally.Consider water:In a stagnant pond, heat distributes evenly, motions are random, no discernible patterns or structures.In a moving river, complicated structures naturally emerge – eddies, vortices.In a boiling pot of water, hexagonal convection cells naturally emerge.Where does freezing fit in? Is it a different sort of emergence?Nature is full of self-organizing, chaotic, and emergent systems: Flocking, crystallization, autocatalytic loops, weather, atoms-molecules-cells-etc..., galaxies, ferns, ant coloniesJames Lovelock conjects that bottom-up systems dominate – Gaia Hypothesis (as demonstrated by Daisy World, a very nice agent-y simulation.) shows that algae are as significant as geology.Evolution* time != the observed world because there is not enough time. E.g. (random chemistry) * (12 billion years) != an enzymeHowever, when emergence is thrown into the equation, everything changes:e.g. (random chemistry) * (autocatalytic loops) * (t <<12 billion years) = enzymes and much moreComputer Science / Artificial SystemsGames – chess in particular. Chess has fewer then two dozen rules, yet, it is still not solved after many centuries of study. (Whereas tic-tac-toe is solved, though it does have over 50,000 legal configurations.) Go is even more extreme.John Holland – the “Father” of genetic algorithmsEarly Neural Network SimulationIn 1952 started out at IBM with the prototype of the first fully electronic digital calculator. It could store a few thousand numbers. Holland simulated a 512-neuron neural network model that demonstrated that reverberating assemblies could arise, cell assemblies. Inn the human CNS, these correspond to different environmental stimuli. CheckersplayerHis partner, Art Samuel, wrote a checkersplayer on the same hardware. It could learn, and it learned to beat him. Not a top-down system with a database of the best strategies, but a bottom-up system using a set of general strategic measures (pieces ahead, #kings, penetration) that were weighted for different general board configurations. The learning process was a matter of changing the weight of a strategy after observing its effectiveness. It also modeled its opponents by assuming they knew what it knew. This modeling actually allowed it to play against the “opponent” a few moves ahead and learn on the fly about the consequences of moves it was considering.Genetic algorithmsGenerate algorithms “at random” with this procedure:1. Generate a large population of random algorithms – literally randomly generated strings.2. Each algorithm operates on some piece of data.3. Evaluate each algorithm’s fitness – how “well” did they process the piece of data? (E.g. How quickly did they work? How correctly did they work? etc…)4. Algorithms are allowed to reproduce based on their fitness. Reproduction is a copying process that is sexual, and may involve mutation. E.g.:Take the first (random number) of characters from one parent and the complement from the other11001011 X 01010010 :11001+010 :11001010Introduce a mutation:110011105. Repeat 2-4 with successive populations. Observe increasing fitness (or not.)Cellular Automata, Conway’s “Life”Sanislaw Ulam comes up with cellular automata – a checkerboard where each cell has some finite set of states and those states evolve based on the states of local cells – as a way of modeling the physical universe.Von Neumann uses cellular automata to prove that self-reproducing machines are possible, that they don’t require an infinite regress of self-depictions.John Conway develops a simple, but very well known cellular automata system called “Life.” Each cell has two states: alive or dead (occupied or empty), and state evolution obeys these rules:1. If the cell is empty and exactly three of its eight neighbors are occupied, then it becomes occupied on the next time-step2. If a cell is occupied and two or three of its neighbors are occupied, it remains occupied, otherwise it becomes emptyDemonstrates a surprising amount of emergence, including the ability to design a pattern that interacts so asto form a general-purpose computer. [Demo gliders.]TermsArtificial Life - The life-like patterns emerging in cellular automata and related electronic arrays. These emergent patterns seem organic in the manner in which they move, grow, change their shape, reproduce themselves, aggregate, and die.Autopoeisis - A theory of what life is, developed by the Chilean scientists Humberto Maturana and Francisco Varela. A living organism is understood as a circular, autocatalytic-like process which has its ownsurvival as its main goal. The phenomena of self-organization is sometimes seen as an autopoeitic phenomena. Cellular Automata - Computer programs that are composed of a grid of "cells" connected to their neighboring cells according to certain "rules" of activity, e.g., a cell might be "on" if its four neighbor cells (east, west, north, and south) are also on. The entire array can self-organize into global patterns that may move around the screen. These emergent patterns can be quite complex although they emerge from very simple rules governing the connections among the cells.Chaos – A type of system behavior appearing random-like, yet is actually deterministic and is constituted by a "hidden" order or pattern. Chaos can be found in certain nonlinear dynamical systems when control parameters surpass certain critical levels. The emergence of chaos suggests that simple rules can lead to complex results. Such systems are constituted by nonlinear, interactive, feedback types of relationships among the variables, components, or processes in the system.Complexity - A description of the complex phenomena demonstrated in systems characterized by nonlinearinteractive components,