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

From the forum more complex things (I'm thinking of humans in particular right now) don't compute or analyze certain problems with algorithms ... We often go with intuition or gut instincts, things that don't have rules. I don't see how we can be thought of as CA when we operate in very different ways from them ... Heather we can't just predict Jessica's behavior by rules (poll results). We have to see how those rules interact with other rules (major, motivation, amount of sleep) to really get a good idea of how Jessica will act ... So yes, I agree that rules, no matter how universal (and possibly because of how universal) they are cannot accurately predict things such as human behavior. There's too much else going on and that interaction is what generates the complexity ... Jessica when you boot up a computer game and fight against it's AI, the AI doesn't appear to be running algorithms - it might be dodging behind cover, shooting at you, running around, or running away. Yet it's still running an algorithm. Perhaps we just don't see or understand the algorithms that control us? ... Frank Maybe the situations that people are placed into are random, and the behavior is the result of CA and alogrithms. And if the behavior is said to be "wrong" then the machine/program or in this case, the human is punished, just the way the program was punished - someone posted about this earlier. Maybe it is the CA that is the program and it is just called nurture. But what about the times that humans make a mistake again even after the time that they are punished? Isn't it impossible for an algorithm to do that? ... Mansi I actually disagree that humans don't think about problems algorithmically ... So are there parts of the world which originate in CA but are no longer reducible to such? I feel the obvious answer is yes, but find myself hard pressed to give a clear example. Human emotions may be an arguable example. Certainly we can imagine the patterns of neurons and the levels of chemicals that create emotion in a physical sense emerging from CA in a very early stage of evolution. But isn't it also possible that the modern experience of love is constituted not by its origins in CA but in the cultural achievements which have shaped our ideal of love? If this is the case, it seems unlikely to me that the emotion remains something reducible to CA ... Alex it seems rather difficult to say that human behavior is derived from CA. There are just too many exceptions and intricacies. I was thinking that if the CA is allowed to run for a very large number of iterations, would its complexity increase, or would it stay at the same level of complexity? For CA to be the basis of life, it would have to evolve to higher complexities over time ... Shika the model never considers the possibility of an alternative action, which is something that somebody is always thinking of in the real world. And acutually, it is not rare that emergent phenomena arise from a group of people that come up with alternative ways of thinking or behaving ... Natsu but then is there really a purpose for higher-level creatures at all? Or are they just the by-products of increased complexity (read: CA iterations) where failure to possess fatal "flaws" does not reduce organisms to their more simplistic forms? ... Lauren I still don't see the crucial piece of information: how did life transition from Cellular Automata-like organisms to larger, multi-cellular organisms? And more importantly, how did those organisms develop consciousness? ... Sam even if he were to KNOW for certain that 1-D CAs are the "source" of all existence in the universe, I still feel it to be extremely important to study everything that has developed as a whole FROM those CAs. Perhaps in exploring the relationship of our modern world today to Cellular Automatons, we could further ourselves greatly (perhaps actually discovering the CA that spawned everything), but studying CAs exclusively is not the only way to go ... We would need to figure out the steps that got us where we are today in order to determine the pattern, and thus the "rules," that govern this emergent, deterministic system we live in. ... Frank maybe we can start believing in absolute truth again and find the empowering ideologies that we need now to save each other and our planet ... if we can base an economy on micro-decision making, it's about time we start thinking about designing more sustainable social systems and accept that order can arise from a localized distribution of power ... Rob

• What is "complexity"?
• Is there irreducibility?
• Where is learning? evolution?
• How does one get from the "simple" to the "complex"? the irreducible?
• Is the universe deterministic? computable?
• Are we?

Beyond universal Turing computability ...

• A taste of the direction: "garden of eden" patterns in cellular automata (alternate)
• Turing: the halting problem
  • Turing computable = anything that an appropriately programmed universal turing machine can compute
  • programs can be identified with whole numbers or finite strings (there are only a countably infinite number of them)
  • does that list include "halt" which takes a program and an input to it, generates yes if it halts (add two numbers), no if it doesn't (take a number, multiply by ten, repeat)?
  • presume it does, then the list also includes "trouble" which takes two strings as an input and halts with "yes" output iff halt (s,s) is no; if "halt" outputs no, "trouble" outputs yes
  • look at "halt" in the case of "trouble" as both inputs
    • if the output of "halt" in this case is "no", then "trouble" doesn't halt implying that "halt" is yes
    • if the output of "halt" in this case is "yes", then "trouble" halts and therefore "halt" is no
    • therefore "halt" can't exist
• Chaitin: omega in mathematics
• Godel: Inherent limits of rule-based systems
  • Consistency or completeness but not both
• There are always places you can't get to from here
• Making use of indeterminacy (irreversibility)

The non-computable: places you can't get to from here, except using indeterminacy?

An additional problem with CA's: dependence on observer, no actual "agents"

• CA as "computer" only with an observer
• "agents" within world only with observer
• "agent" = something with an internal set of instructions distinct from those of things it is interacting with?
• agents can do things that CA's can't? infer (rather than deduce) properties of worlds?

Assignment: create a model in which an agent infers properties of a world (notice that Langton's ant doesn't, it interacts with world which is changed by it but nothing in ant is changed by world), can be done individually or in groups, due after spring break

Will consider further directions from critique of CA's on Wednesday

From the forum i've been thinking about the different levels of social science research and how they parallel studying emergent systems ... even if we accept that complex structures emerge as the synthesis of smaller, simpler units, we still may find it useful to analyze such structures on different levels as different attributes of the system may be more evident on certain levels than on others ... Rob What if, in looking from a more 3-dimensional perspective, CAs function in layers where observers can only perceive the combined function of the outermost rule with the "invisible" rules present underneath. Like layers of paint in a masterpiece, it can be hard to see through to the most basic foundation without immediately observing how all the layers blend together. This blending can cloud the true nature of each level and lead the observer to see "randomness", where only the power of a super-observer would enable him or her to see that each piece logically fits together. Perception is inherently limiting, especially when science strives to be all-knowing ... Lauren So we talked about garden of eden patterns in the Game of Life. Some patterns have been found. But we who have found them exist outside of that Game - so my question is whether or not we would have been able to find them from within that system ... whether or not we'll ever be able to discover our own Garden of Eden patterns ... Frank Sounds like the halting problem. No turing machine can solve its own halting problem ... Sam This doesn't refute the idea that DNA might be the simple instructions that guide us, but it is an interesting point to keep in mind. Like all instructions, DNA needs "input" to function (see also) ... I think the reason people (such as myself) are resistant to the idea that humans operate under simple rules like CA is because of consciousness. We are aware and can come up with new ideas and change our psychical surroundings and social situations ... People are able to look outside their immediate situation and see how the world might be if something was changed and plan for the execution of that change. That is not possible with CA since it operates in an absolutely deterministic world ... Jessica Isn't it possible that some specific "Garden of Eden" pattern created the original consciousness which grew more complex but was able to reproduce itself in some form in all life? ... Alex

Back to original challenge (now, hopefully, with greater background/sophisitication)

The CA universe An external observer of the universe (or some part of it) may perceive "agents" but agents do not in fact exist except in the mind of the observer. The universe as it exists at any given time and as it changes over time can be understood without the concept of either indeterminacy or "agents" or "observers" having some distinction from the rest of the world.

Useful lessons

• Without planner or conductor, simple interactions among simple things can create both order and unpredictability
• Simple interactions among simple things can yield anything "computable"

Limitations

• Deterministic (and therefore there are things that can't be gotten to)
• Interpretable only by "observer"
• No actual "agents"
• No capacity to "infer" properties of a "world"

The larger picture, and future directions

Both conductors and planners/architects are themselves products of on ongoing process of emergence. So too are agents, the brain, meaning, purpose, science, and inquiry itself. All are (non-deterministically?) derivitive of properties and interactions that existed at earlier stages of emergence and that persist at lower levels of organization. Having come into existence, each becomes both an influence on lower levels of organization and an ingredient for the creation of new levels.

Agent-based models can do things (have properties?) that deterministic cellular automata do not. Agent-based models can be derived from suitable? cellular automata (deterministic?). Simple agent-based models are necessary and sufficient to generate (deterministically?) more complex agent-based models that in turn can do things that neither cellular automata nor simple agent-based models can do.

Elaboration

• "Model builders" are capable of "inductive reasoning", ie of making observations of the world, summarizing those observations, using them in future interactions with the world
• This in turn can give rise to "deductive reasoning", the effort to make sense of observations collected in terms of a set of simpler "first principles" the consequences of which can then be explored (and compared to observations of the world)
• Both inductive and deductive processes have limitations
  • Induction - inability to prove universals
  • Deduction - existence of things outside the realm of the "computable"
• This in turn can give rise to "abductive reasoning" (Charles Saunders Peirce)? The ability to recognize/use "stories" by arbitrarily altering their premises to see what new consequences might follow (eg non-Eucludian geometries)
• Somewhere in this sequence the notions of "self", "plans", "free will", and other important (and causally meaningful) cultural concepts emerge ... progressively?
  • Beginnings of "intention" or "purpose" from agent responding to/altering world
  • New properties with world altering agent?
  • Stil new properties with agents interacting with world and other agents? altering each other?

Questions to keep in mind in returning to agent-based models:

• How does one find/create (currently?) non-computable things?
• Is there actually a meaningful distinction between universes and universes including agents?
• Can agent-based models in fact do things that cellular automata cannot?
• Is change in agents ("learning") important for that?
• Are there simpler and more complex agent-based models?
• Can observers be incorporated in models?
• Can each of the levels be simulated? Showing that none require anything more than simple interactions of simple things?
• Can we begin to conceive ways of moving from one kind of model to the next? Does this require indeterminacy? irreversibility?

Start thinking about the kind of modelling project you want to be working on for the remainder of the course ...

Post conversation notes Story works very will with current definition of "computable" (turing) but actually transcends it because of Godel. Whatever is "computable" (ie deducible from first principles) at any given time is/will be necessarily limited and so the challenge will always be to go beyond that. "Deducibility" is "trimmed" version (see notes from evolit07), can be used to find new worlds (as per non-euclidian geometry), is always limited. Abductive "leap" always available and exists only for story tellers since only they can do both inductive and deductive reasoning, on which abduction depends. Need or do not need "self" for this?

| Course Home Page | Complexity | Serendip Home |