# Emergent Systems 2002-03 Forum

Comments are posted in the order in which they are received, with earlier postings appearing first below on this page. To see the latest postings, click on "Go to last comment" below.

 first meeting Name: Paul GrobsteinDate: 2002-10-08 19:09:00 Link to this Comment: 3216

Nice start. A couple of thoughts:

This levels of organization issue is a significant one. How does one get from one level to another? My guess is that persuading people of the importance of the "emergence" perspective requires showing that it is not just "simple" things that yield emergent properties but successfully more complex ones. In addition, there's an important conceptual question here, what is meant by different levels of complexity? How do they emerge? Where does the discreteness come from? Old questions, maybe with possibility of some new rephrasings, new answers? See From the Head to the Heart, and refs therein.

I think its significant from several perspectives that "emergence" is invariably(?) linked to loss of order (through the second law of thermodynamics ... see Life and the Second Law. This linkage is frequently ignored in emergence illustrations, which may be not only misleading but a fundamental problem. Perhaps the emergence of successive levels of organization requires this coupling?

Steven Johnson's Emergence (Simon and Schuster, 2000) is quite good both on the history of concepts and some of the broader implications of "distributed systems" ideas.

 What is a "level"? Name: Doug BlankDate: 2002-10-11 17:05:23 Link to this Comment: 3265

What is an emerged level? Real-world examples include:
• a V in the sky, from the interactions of flying geese
• intelligence, from the interactions of neurons
• cities, from the interactions of people
• life, from the interactions of chemicals
• chemistry, from the interactions of atoms and subatoms
and one sim-world example that we seen so far:
• a glider, from the interactions of rules of a cellular automata
In what sense are these levels "real", and in what sense are they just observed patterns?

I'd like to propose a distinction between levels such as the glider and the V, and the rest of the examples. It seems that the glider and the V really are just observed patterns and don't add anything to the system. Let's call these "weakly emergent" levels. On the other hand, the other levels do add something to the system (the whole is greater than the sum of the parts). Let's call these "strongly emergent" levels.

What do they "add"? It seems that there is feedback from one level to levels of organization below. The feedback can be seen in the form of additional constraints, or maybe in terms of additional information (in the technical sense). (I have more to say about information theory, but I hope we can talk about later)

 some intersections Name: Paul GrobsteinDate: 2002-10-16 20:43:34 Link to this Comment: 3274

There is a new SciSoc Graduate Ideas working group which discussed, at its first meeting, Johnson's Emergence. A number of interesting issues arose, including the significance of thinking about emergent systems in political and moral contexts. In addition to looking in on that conversation, people in this group might be interested in future meetings of that one.

And here's a bit from Ted Wong, sent to the listserv and potentially more generally significant:

In the current issue of Science, Melanie Mitchell reviews Stephen Wolfram's new book "A New Kind of Science" and discusses what's new and what's just arrogance.

http://www.sciencemag.org/content/current/ (Go to "Book Reviews.")

Ted

There is also a review of Wolfram's book by the physicist Steven Weinberg in the current New York Review of Books at http://www.nybooks.com/articles/15762.

 emergence: life and death Name: Paul GrobsteinDate: 2002-11-29 12:52:13 Link to this Comment: 3907

Ted provided some useful information through our listserv, as follows:

Anne expressed some concern about the trend. I replied:

Calm down. Interesting issue, hope we can get the group to it:

DEATH is an ESSENTIAL element of "emergence'

1. Second law of thermodynamics
2. Some VERY interesting theory/ongoing story-telling about "Maxwell's Demon"

Might be worth picking up on this theme next semester.

 Poetry emerges from sheep behavior Name: Ted WongDate: 2002-12-05 15:18:27 Link to this Comment: 3983

A story on this morning's Morning Edition describes a public art project in England in which artist Valerie Laws, a writer, has written a different word on each of fifteen sheep. As the sheep arrange and rearrange themselves according to whatever rules sheep follow, poetry emerges occasionally (presumably). Laws says that she's interested in exploring connections between quantum mechanics and literature. In an article in The Daily Telegraph, Laws lists the commonalities: "randomness, the influence of the observer and the observed, and duality."

If you have the RealPlayer player, you can hear the story here.

 Someone please point out my error. Name: Wong's DemDate: 2002-12-06 17:14:16 Link to this Comment: 3992

So this morning Paul said some things about how biological evolution is the ultimate example of emergence, of a complex system, of increasing oranization and therefore a reduction in (local) entropy.

But is it? Maybe evolution is better described as an increase in local entropy.

Imagine some plant propagule has blown onto some oceanic island. It and its immediate progeny are maladapted to their environment: they flower too early in the spring, their leaves are too thick and overheat too quickly, they're too tall and spindly for how windy the island is. Over time, the population evolves, and the plants are better and better suited to the island. The photoperiodism of flowering is calibrated to th local daylength-tempreature (or -moisture) relation. The leaves are thinner for more locally appropriate heat exchange. They're shorter and bushier.

It seems to me (and the issues are all confusing enough to me that I fully expect someone to point out where I'm wrong) that as the population became more adapted to the environment, information was lost. Relative to the adapted plants, the ancestral plants had high information. (This, of course, using information in the sense that if I say to you, "Bob Dole is my transsexual twin sister," I'm conveying more information than if I say, "Hi, it's cold out," because it's more improbable and hence more surprising.) On that island, the ancestral plants are improbable. Nothing about them mirrors anything about the island environment. In contrast, the adapted plants could be said to say something about the environment. Given the environment, you could predict traits in the adapted plants much more easily than you could predict the ancestral traits. Adaptation has caused the population to be more like the environment. After adaptation, there are fewer different things in the world.

Or, think about it like Maxwell's hot and cold rooms. The ancestral population and the island environment are like hot and cold rooms, while the adapted population is like some room that's just warm.

Or, imagine that you've done a principal-component analysis, trying to quantify how many things there are in the world. After adaptation, the plant traits are closer to being colinear with the environmental variables. Fewer things in the world, though not by an integer amount.

So evolution works by decreasing the number of different things, by decreasing the number of differently temperatured rooms in Maxwell's Demon's house. Mutation increases information in the genome, and selection decreases it. Maladaptation is high information, and adaptation cleanses the genome of it. Like diffusion, adaptive evolution is an entropy-increasing process.

Right?

 Re: Someone please point out my error. Name: Doug BlankDate: 2002-12-11 09:48:06 Link to this Comment: 4045

Wong's Demon speculates that an organism that adapts to a new environment has lost information about previous environments. To make this concrete, let's assume that the size and complexity of the genome didn't change, it just got rearranged. Viewed in this manner, one wouldn't normally describe the organism as loosing information, because the information content has stayed the same. It just contains different information.

On the other hand, the population has lost information. These brings up an import point about talking about information: it is always relative to a context to give it meaning (the same point can be made about intelligence and emergence, which is why I think all three are related. But more on that later).

Wong's Demon further admitted:

(This, of course, using information in the sense that if I say to you, "Bob Dole is my transsexual twin sister," I'm conveying more information than if I say, "Hi, it's cold out," because it's more improbable and hence more surprising.) It appears that the above statement is true only if the information is "true". Uttering random statements would be surprising, but only meaningful in some context where they were true (or "useful" if the idea of truth is worrisome).

The idea of the population as a whole loosing information seems like an appropriate thing to say. And would make sense the way we normally think of evolution as a "search mechanism". As John Holland pointed out, evolutionary systems balance exploring unknown regions of the search space, with exploiting known (good) regions of the search space. So to say we are trading some information so that we can concentrate the search in particular areas would seem to be correct.

So evolution works by decreasing the number of different things, by decreasing the number of differently temperatured rooms in Maxwell's Demon's house. Mutation increases information in the genome, and selection decreases it. Maladaptation is high information, and adaptation cleanses the genome of it. Like diffusion, adaptive evolution is an entropy-increasing process.

Right?

I don't think so. It decreases information across the population in exchange for a systematically organized population that is fine-tuned to optimize the balance between exploitation and exploration. But I think that Wong's Demon shows that "information content" does not equal "complexity". Complexity being that thing that is increasing.

Right?

 on complex systems and social organization Name: Paul GrobsteinDate: 2003-02-19 10:24:06 Link to this Comment: 4670

****************
Date: Wed, 12 Feb 2003 03:32:19 -0000
To:
Subject: EMERGENCE: Power laws and blogging
From: "Douglas S. Blank"

Emergeneers,

An interesting article on the statistics of "blogging" (web logs):

"Power Laws, Weblogs, and Inequality"

-Doug
******************

Interesting indeed. Anne and I had quick go at this in conversation this morning, would be worth more talking through collectively ...

Question, in essence, is what "power law" behavior of complex systems might mean in social/cultural realm. Parenthetically, its noteworthy (for language group?) that technical term for nature of distribution of perturbation sizes in complex systems (most/all?) resonates for some people with social issue of "power' and its distribution, in sense of inequity.

General argument of paper, if I'm understanding it correctly, is that thinking of social organization as complex system implies that almost any characteristic of individuals (wealth, popularity, "power") will be distributed as a power law, implying the inevitability of substantial "inequity". Furthermore, the range of distribution ("amount of inequity") will necessarily increase as the population size increases.

On the face of it, this has a "fatalistic" character to it, and it is, at a minimum, an argument for keeping social systems small (an inference that one might well reach for other reasons, cf. Small is Beautiful). But ...

1- The analysis presumes that one WANTS to be wealthiest, or most popular, or most powerful. Many people (myself included) don't, for quite coherent reasons (the costs of being any of the above, among other things what my son calls the "budweiser effect").

2- The analysis presumes that a social "objective" is to eliminate "inequity". For me at least the objective isn't necessarily to eliminate inequity but rather to assure that distributions remain fluid so that individuals are not locked into particular places in them.

3- The analysis strongly depends on the presumption that interactions among individuals are such that particular choices made by some individuals bias other individuals to make the same choice (the "PC effect"). This is akin to ant stigmergy, noticing high concentrations of pheromones inclines ants to move along the same path. In fact, some people noticing a prevalence of individual choices to go in one direction use that as a cue to move in some other direction (yours truly?).

Bottom line:

I don't think fixed inequities are an inevitable outcome of complex systems in the social realm. On the other hand, the analysis does suggest the value of encouraging people to recognize in themselves inherent (?) biases toward following the stories of other people and do more striking out on their own.

 emergent democracy Name: Timothy BuDate: 2003-02-21 16:38:22 Link to this Comment: 4741

Steven Johnson writes in his weblog today (20 February) about a project to think about the relationship between emergence and democratic practice. A description of the project can be found at http://joi.ito.com/static/emergentdemocracy.html.

 webology Name: pgrobste@bDate: 2003-02-21 16:52:21 Link to this Comment: 4742

There's an interesting similarity between some of the above ("We must make spectrum open and available to the people, resist increasing control of intellectual property, and resist the implementation of architectures that are not inclusive and open. We must encourage everyone to think for themselves, question authority and participate actively in the emerging weblog culture as a builder, a writer, a voter and a human being with a point of view, active in their local community and concerned about the world") and Serendip's "evolving web principles" as, for example:

The interactivity of the Web is perhaps its most important characteristic. For the first time in human history, it is becoming possible for all humans to play an active role in world-wide cultural and intellectual interchange.

See also The Place of the US in the World Community, a Serendip forum area:

... to tell and listen to each others' stories, to commit ourselves anew to finding new ways to tell our collective human story in a way from which no one feels estranged

 How the Protesters Mobilized Name: Anne DalkeDate: 2003-02-24 10:35:53 Link to this Comment: 4784

See also the article in yesterday's NYTimes, "How the Protesters Mobilized" which describes the emergence of protest movements via the web, and adds a new term to our lexicon:

"Social theorists have a name for these types of decentralized networks: heterarchies. In contrast to hierarchies, with top-down structures, heterarchies are made up of previously isolated groups that can connect to one another and coordinate. "

Yours in the (emerging) struggle,
Anne

 universality proof for rule 110 Name: Kris TappDate: 2003-02-24 19:31:12 Link to this Comment: 4791

(originally posted to emergence listserv, Monday, 24 February 2003)

Hi folks,

I mentioned at the end of my talk that Matthew Cook recently proved that RULE 110 is computationally universal. I just obtained a copy of his proof. Now that Wolfram's book is published, he's allowing Cook (who formerly worked for Wolfram and is currently a grad student at UCLA) to distribute his proof. Cook's theorem is ground breaking, and is the core fact supporting the philosophy that Wolfram develops in his text.

Would anyone like a copy? It's 40 pages, and seems to be very carefully written with lots of background and motivational explanations and pictures. Would anyone like to work though the proof together? I think that, if we're willing to skip some of the messier details, it would be a reasonable project. Perhaps it would be a good project to involve students in, with the goal of hiring a group of students to do a summer project deciding whether rule 30 is universal. Maybe this question is too large to solve in a single summer, but we could ask the experts their opinion on this.

Please let me know your level of interest,

Kris

 Complex Systems - Matthew Cook - Rule 110 Name: Genaro JuaDate: 2004-12-19 13:00:52 Link to this Comment: 12003

Finally the demonstration that Rule 110 is universal made by Matthew Cook and presented in a conference at the Santa Fe Institute in 1998, has been published in Complex Systems.

\bibitem{kn:Cook04} Matthew Cook, Universality in Elementary Cellular Automata,'' {\em Complex Systems}, Volume 15, Number 1, pp. 1-40, 2004.

We shall give a small revision and general commentaries with regard of this result.

Universality in Rule 110 provides important results both in computation and cellular automata theory.

Thus there is a Turing machine that emulates the behavior of Rule 110 (apparently developed by David Eppstein), the formulation of the cyclic tag systems and its construction in Rule 110.

1. New cyclic tag machines

Cook offers a demonstration using tag systems taking as basis the results of Cocke-Minsky (1964), and extending them to cyclic tag systems.

Cyclic tag systems and their universality are originally developed by Cook. This way the cyclic tag systems are interesting by their own right because they represent a new mechanism to realize computations, therefore they must be independently analyzed.

We can see some antecedents in circular machines by Arbib (1969), and the universal circular Post machines by Kudlek-Rogozhin (2001).

A pair of productions is propose (N -> $, Y -> YY) and (N ->$, Y -> YN) where \$ represents the empty word. Then depending on the initial value in the tape, the production system must be aligned in the evolution space of Rule 110.

The system starts with a Y in the tape, and the problem of determining if this machine has a periodic behavior or disappear, is undecidable. Analogously to the results by Post (1936) there are several an interesting open questions:

Can we demonstrate if the problem is undecidable or partially undecidable?, or intractable?

The cyclic tag systems can find a solution to all problems for u, and v > = 3?.

Cook 's machine belongs to some of universal circular Post machines of Rogozhin?.

2. Construction in Rule 110

In a similar way that Life, the construction is based on collisions among gliders. In this particular case, periodic blocks of gliders work both as operators and data.

This construction is very impressive and also very sensitive to initial conditions. It has three important parts in the evolution space of Rule 110.

a) Periodic blocks arriving from the left.

These blocks are formed by packages of A^4 gliders representing operators, they must transform the periodic blocks arriving from the right. The transformed values represent data in the tape of the cyclic tag system.

The distances in each package of gliders are doubled or tripled with regard of the blocks coming from the right, in order to get a correct operation.

b) Data in the tape.

The initial datum is restricted to initiate with Y in the Cook's system. Data are represented by blocks of C2 gliders (four gliders in different phases). The difference between the data representing Y or N is the distance between the two internal C2 gliders of each block.

Each data in the tape is erased by a leader (block of E and E- gliders).

c) Periodic blocks arriving from the right.

They represent two important parts. In the initial condition they are blocks (of E- gliders) without transforming. When the leader finds a Y in the tape, the blocks without transforming are firstly transformed into groups of four E- gliders. In the opposite case all the blocks are erased until finding the following leader.

-----------------------

If you wish to find Cook's paper by Google (or another tool in Internet) using key words like: universality cellular automata, Rule 110, cyclic tag systems, Matthew Cook Rule 110, etc.

Peculiarly no search will lead you at Cook's paper in Complex Systems !

-genaro

| Serendip Forums | About Serendip | Serendip Home |

Send us your comments at Serendip

© by Serendip 1994- - Last Modified: Tuesday, 27-May-2014 14:31:05 EDT