16 May 2009

Cellular Automata and Dynamic Emergence in Humphreys "Synchronic and Diachronic Emergence"


by Corry Shores
[Search Blog Here. Index-tags are found on the bottom of the left column.]

[Central Entry Directory]
[Emergentism, Entry Directory]


Paul Humphreys
"Synchronic and Diachronic Emergence"
Mind and Machines Dec. 2008


Abstract


Humphreys will contrast diachronic and synchronic emergence. He then discusses the historical aspect of Bedau's weak emergence. He argues that weak emergence is about token states and not types. Humphreys concludes by evaluating the weakness of weak emergence and discussing the lack of a unifying account for diachronic and synchronic emergence.


Introduction


Diachronic emergence differs from synchronic.

Diachronic emphasizes a novel phenomena's emergence across duration.

Synchronic stresses the lower level properties' and objects' coexistence with novel higher level ones.

Humphreys will argue:

1) Maybe someday we will be able to conceptualize a general sense of emergence that encompasses both diachronic and synchronic emergences. However, right now the two types of emergence are conceptually distinct. So for example, we know that the idea of synchronic emergence does not comply with diachronic; for, we cannot even say that synchronic emergences actually produce an emergence, because a historical development is always needed to produce the conditions for a synchronic emergence. So we might have two identical states, with only one being emergent, because its diachronic development provided for it.

2) There is a sort of emergence that we may characterize as "weak." Bedau offers this definition,
Weak emergence is the view that a system’s macro properties can be explained by its micro properties but only in an especially complicated way. (2008)
Humphreys says that the weak emergence account can explain a lot about diachronically emergent computational forms. But it can explain more if we were to add some of his suggestions.

3) To explain 'pattern emergence,' we need a satisfactory account of conceptual emergence. Humphrey's will only here discuss the philosophical implications.


Pattern Emergence


Pattern emergence
involves the appearance in a system of novel structure that results from the temporal evolution of the system. Pattern emergence is a common phenomenon in computational models such as agent based simulations and cellular automata, and it is widely agreed within the complexity theory literature that these patterns count as examples of emergent phenomena.
Humphrey's will use examples of pattern emergence in his argument. They are cellular automata with a spatial structure. He uses models rather than real world phenomena, because models are simpler to handle. These examples will also help us deal with the sociological notion of methodological individualism. Emergences from patters begin from the bottom up. So we are not concerned with a centralized 'top down' set of laws or rules that govern individuals' behavior.


Cellular Automata


Humphrey's illustrates weak emergence with a cellular automaton (CA). His example is two dimensional, so I will begin with an simpler one dimensional version. Cellular automata are little living abstract machines. They appear as patterns of squares that change according to a finite set of rules. Their space is a grid. In our one-dimensional version, it is a row of squares.


We apply transformation rules to the squares in that row, and place the changes in a new row below it.

So let's begin with this row, with just one darkened square in it.



We see that the black square has two neighbors: a white square on either side.



The other white squares have white neighbors.



We will go through each square, and depending on the contents of the neighborhood, we will transform the center block in the following row according to these rules. [Click to enlarge]



So we begin with the first neighborhood, and we see that we transform the white center block into another white block.



Now we have this for the next row so far:



And we do the same for the next neighborhood.



Now our second row is:



The next neighborhood has a black box on the one end, so we transform the center block to a dark one.



Now we have



Same for the original darkened box for the first row:


Which gives us



We continue this process for the rest of the row, and we obtain the full second row.



Now we repeat the procedure, this time only attending to the contents of the second row. We then obtain for the third row:


And then for the fourth row:



And next



Now notice the white "T" shape in the lower right side in the image below. This will appear as a triangle, and many more such triangles of various sizes will show as we continue the process.


Also, we presume from the beginning that the grid extends infinitely, so our picture above may continue expanding outward. The patterns that emerge from this automata are pseudo-random. Nonetheless, the character of its randomness emerges as the iterations proliferate. [Credits for the following images are given below. Click to enlarge. Thank you sources. Image 1]






[3]



[4], [This needs to be clicked to see what is going on, it's large.]



Humphrey has us consider a more complex two dimensional example. We are to imagine that
Over a wide range of initial states of the CA, appropriate updating rules can produce randomly distributed arrays of colored cells, stable patterns that persist across time, and dynamic patterns that evolve over time.
We are to suppose that the given transformation instructions will eventually produce the following form [5]:


To arrive at this form, we presumably had to carry-out the transformation operations many many times. What is important is that we cannot deduce that this form will come about merely by knowing the initial conditions. We always need to know the formation's preceding step, and its preceding step, and so on until we arrive back at the starting situation. Astronomers, however, can predict the next solar eclipses without needing to know the sun's positions in between eclipses. Such predictions are computationally "compressible," where cellular automata are "incompressible."
I shall examine weak emergence in detail in a moment, but the essence of the idea is that a state of a system is weakly emergent just in case that state can be produced only through a step-by-step simulation of the system. In other words, the process that leads up to the state is computationally incompressible. In yet other words, unlike the prediction of future solar eclipses for which the computational difficulty of prediction is almost independent of how far into the future the eclipse will take place, predictions of future states of computationally incompressible systems must run through each of the intermediate time steps between the initial state and the predicted state. Letting the computational model work out its own development is thus the only effective way to discover how the system’s states evolve. The philosophical motivation for accepting this criterion as capturing a certain kind of emergence draws on the philosophical tradition that emphasizes the essential unpredictability of emergent phenomena. (emphasis mine)


Properties of Pattern Emergence


For there to be emergence, something must emerge from something else. The bow-tie pattern above emerged from the pattern of its rule-based re-iterations. If instead we made a stamp with that image, and stamped it on paper, we would not say that the formation emerged on the paper.
It is another token of the same pattern, but that token is not emergent because it is generated instantaneously.
This example tells us three things:

1) Pattern emergence is largely a "historical" phenomenon: "whether an instance of a pattern is emergent or not depends essentially upon the process that generated it." Thus we cannot look at the synchronic elements of some formation and determine whether or not it is emergent.

2) It cannot be synchronic, because that means we can look at a formation and determine the emergence. It also means that two of the same formations would bring about the same emergence. But we see that both the stamp and the automata have the same formation, but the stamp did not result from a pattern emergence.

3) If we looked at the two identical bow-tie patterns, one from automata, the other from an ink-stamp, and if we say there is the same formation, we are dealing with a type of formation. But we saw that in the one instance there was pattern emergence, but in the other instance there was not. Hence, "pattern emergence is about tokens or instances of patterns, not about types."


Weak Emergence


So we see with the automata that there are lower level circumstances and higher level properties. We call the lower level circumstances micro-facts and the higher level we call the macro-level. On the micro-level of cellular automata, there are only squares. So the property of being "bow-tie shaped" can only occur on the macro-level. We call such a property that can only appear on the higher level a nominally emergent property. We obtained it only by running the simulation that re-iterated the transformation rules. And we may characterize the individual square on the micro-level only in terms of its location and such intrinsic traits as it being black or white. The macro-level entity then is the aggregate of all the micro-constitutent states taken together along with their spatial relations. Because the whole of the macro-level structure can be reduced to the conglomeration of the micro-level states and locations, we call such a system a "locally reducible system."

Humphreys then defines weak emergence as (citing Bedau):
Assume that P is a nominally emergent property possessed by some locally reducible system S. Then P is weakly emergent if and only if P is derivable from all of S’s micro facts but only by simulation.’
We need to run the simulation, because the pattern must be computationally incompressible. Hence the bow-tie structure exemplifies weak emergence.

For the most part, this definition captures the sorts of emergences found in dynamical systems theory and in complexity theory. However, to fully apply, we need to supplement it in two ways.

1) We need to distinguish end states that are non-random from those which have "predicates picking out genuine macro-level properties."

1a) If the pattern begins random and ends random, that does not qualify as a novel emergence. For, even though each random pattern on its own is unique, all random patterns are of the type "random." So nothing is new when random transitions to random.

1b) If the pattern begins structured and ends ordered, then here also there would not be an emergence. For, we consider emergences to result from self-organization. But a turn to chaos is a self-disorganization. One thing that makes emergences so interesting is that they defy the Second Law of Thermodynamics (entropy). So we will not consider a random outcome from an ordered beginning to be emergent. It must have structure to be emergent. But there is a continuum between order and chaos, structure and random, so there is no clear way to make this distinction.

2) Maintaining the automata in a perpetually random state is not difficult to achieve. So we should not devalue the concept of weak emergence by including such cases.

Hence Humphreys offers this revised definition for weak emergence:
P is a non-random property of the system S that is distinct from any property possessed by the initial state of S.


Micro-stable and Micro-dynamic Patterns


Humphreys says that synchronic features are neither sufficient nor necessary conditions for pattern emergence.

Broadly speaking, there are two types of pattern emergences.

1) Micro-stable patterns.
Micro-stable patterns emerge when the computational process no longer develops because it has reached a stable non-random pattern which the transformation principles no longer alter. Our bow-tie pattern is such a case where there was a terminal form that maintained its exact shape.

2) Micro-dynamic patterns.
Micro-dynamic patterns emerge when a non-random pattern emerges, and that pattern itself cycles invariantly, on account of the transformation substitutions falling into a consistent pattern. To view a micro-dynamic pattern, scroll to the bottom of this page, and run the simulator.

We may distinguish three sub-types of micro-dynamic patterns.

2a) Recirculating autonomy
The micro-dynamic pattern exhibits recirculating autonomy if its same consistent parts cycle around in a constant pattern. We see this for example when we heat a fluid between two hot plates. Inter-locking columns of circulating fluid cycle in their cellular regions. These are calledBénard convection cells. [6]











Animation can be found here.

Another example of recirculating autonomy is Couette flow. This comes-about when we place a fluid between two concentric rotating cylinders that are moving at different speeds. "Vortex rolls form when the velocity gradient exceeds a critical value."











In recirculating stability, a structure emerges that consists of a fixed collection of entities, and this structure remains constant while the micro-level entities undergo dynamic cycling across duration.

2) Transient autonomy
In transient autonomy, the macro-structure emerges and persists. But unlike recirculating autonomy where the micro-entities remained the same while changing location, in transient autonomy the micro-constituents are continually substituted by the same type of entity. We may see this in river flows, for example, where the ripples repeat, but always with new water molecules. [14]



3) Equivalent class autonomy
Equivalent class autonomy occurs when the macro-level pattern is sustained by the cycling of lower level entities that are of the same general type. for example, if our river ripples came to be replaced by wine, beer, broth, etc.

Hence there are two roles for micro-process dynamics in pattern formation and perpetuation.
A) Bringing about the initial formation of the structured pattern. This role is important when considering pure diachronic emergence.
B) The persistence of the pattern while the micro-dynamics continue. This role draws upon both diachronic and synchronic emergence, because the stability of the cycling dynamics suggests a trans-temporal 'synchronic' form that manifests dynamically.

For these cycling patterns, again, see the animation at the bottom of this page. Humphreys offers an example where we begin with a random distribution of values [15]



and after 500 iterations, a spiral pattern emerges [16]



Humphreys then wonders if we can characterize this formation as "spiral" as though there were something about it to make it different from any other spatial pattern of cells.


Pattern Emergence and Supervenience


Consider if the bow-tie were a different color. Would it be the same pattern? It's not clear what our criteria will be for distinguishing patterns.
If I am correct about the role that this kind of pattern persistence plays in diachronic emergence, then whether the criteria for pattern identity turn out to be objective, subjective, pragmatic, or based on some other ground, that feature will automatically carry over to computational diachronic emergence itself.



Humphreys, Paul. "Synchronic and Diachronic Emergence." Minds and Machines. Vol.18, Number 4, December, 2008, pp.431-442.
More information and online text available at:


Image credits:

[1], [3]

[2]
(The Author writes: Wolfram's "A New Kind of Science." ... The first 50 iterations of Rule 30 are shown on page 25 of Wolfram's book.)

[4]
http://commons.wikimedia.org/wiki/File:Rule_30_2000Generations.gif

[5], [15], [16]
Humphreys, Paul. "Synchronic and Diachronic Emergence." Minds and Machines. Vol.18, Number 4, December, 2008, pp.431-442.

[6]

[7]
Schematic drawing of a Rayleigh-B\'enard cell. The red-shaded areas of the cell show regions of hot fluid, while the blue areas indicate cold fluid. Adapted from L. Kadanoff, Physics Today 54, 34 (2001).

[8]

[9]

[10]

[11], [12]

[13]

[14]



No comments:

Post a Comment