Emergence Biology 361 = Computer Science 361 Bryn Mawr College Spring 2007

A schema for emergence as a big idea

• Simple interactions among simple things in lieu of a conductor (fully distributed systems) can create order (non-randomness)
• Simple interactions among simple things can create kinds of order unanticipated by an architect/designer
• ????? Simple things interacting in simple ways have consequences that cannot be characterized except by trying them out? .... "computational irreducibility"? (Turing machines, halting problem)
• ????? VERY simple things interacting in VERY simple deterministic ways can do anything ?
• ????? There are patterns/principles in emergence ?

The Wolfram approach to cellular automata

• Start by asking empirically what very simple things can do, developing intuitions about it
• Look systematically for patterns, draw inferences from those
• Explore, test inferences
• Repeat
• (don't get too distracted by what other people may have done/seen)

Simple 1-D deterministic cellular automata

• world of two state patches
• simple neighbor interaction rules
• starting condition
• iterative (each state of universe depends on previous state and unvarying set of deterministic rules)
• 256 possible rule sets

Four possible types of behavior?

1. uniform from most starting states (rule 250 from one cell)
2. simple repetitive patterns from most starting states (rule 90 from one cell)
3. chaotic ("random"?) from most starting states (rule 30 from one cell)
4. mix of chaotic and patterned from most starting states (rule 110 from one cell)

Similar for more complicated cellular automata/systems? (see three state CA)

• describes all possible "realities"?
• ours an unpredictable mix of chaos and pattern?
• rule sets that allow propagation of disturbances widely?
• "edge of chaos" - Langton (see also Bak, self-organized criticality and Stuart Kauffman)

Cellular automaton (universe) as computer?

• calculating mod2(x) - rule 132
• calculting multiples of 2 - rule 94
• calculating multiples of 3 - rule 62
• calculating multiples of 4 - rule 190
• calculating powers of 2 - rule 129

"Universality"

• "capable of emulating any other system [?] ... able to produce behavior as complex[?] as the behavior of any other system" (Wolfram, p 643)
  • Turing machine
  • Universal turing machine
  • Church-Turing thesis
  • a "universal" cellular automaton, able to emulate any cellular automaton by "programming" via initial conditions (Wolfram, Chapter 11, Section 3) - "more complicated[?] rules can always be emulated just be setting up appropriate initial conditions"
  • rule 110 is universal, computationally equivalent to a universal Turing machine (Wolfram, Chapter 11, Section 8)

Computational universe?

• "there is in the end no difference between the level of computational sophistication that is achieved by humans and by all sorts of other systems in nature and elsewhere" (Wolfram, p 844)
• McCulloch-Pitts (alternate)
• "in the end the Principle of Computational Equivalence encapsulates both the ultimate power and the ultimate weakness of science. For it implies that all the wonders of our universe can in effect be captured by simple rules, yet it shows that there can be no way to know all the consequences of these rules, except in effect just to watch and see how they unfold" (Wolfram, p 846)
• Digital Mechanics
• digital determinism"?

More "onion unpeeling" to come ...

• What is a "system"?
• What is "behavior as complex"?
• ????
• "a new kind of science"? adequate? complete?
• Do we need anything more than cellular automata to study emergence? If so, what? why?
• thoughts in on-line forum

Assignment due a week from Wednesday: an exploration/modification of one dimensional cellular automata (allowing arbitrary starting points? showing the edge of chaos?). Be sure to send me the .nlogo file, with commentary.

If you haven't already sent me two .nlogo files, with commentary and titles please do so.

• Talk about critique of Wolfram on Wednesday; any additional thoughts in current forum welcome before then
• Should have by Wednesday sent me three .nlogo files (modifications of Langton's ant, any Netlogo model, cellular automata) with comments (include attributions to original model). Updates fine.
• Should be completing reading of relevant book. On-line commentary ("create content", "blog entry") and presentations the week after spring break.

| Course Home Page | Complexity | Serendip Home |