(Notes on a lunchtime discussion between Sean & Stephen, 2-July-2003)
Although Wolfram identifies a class of cellular automata that generate 'complex' structure there seems to a feeling that real-world systems have greater complexity that cannot evolve from the equivalent of a 110 rule operating on a cellular automata. What is it that helps to generate greater complexity? Ecologies and economies both show a HIERARCHY of nested structures. (E.g. molecules, organelles, cells, tissues, organs, individuals, populations, ecosystems; or employees, divisions, firms, national economies, global economies). Each level of organisation contains agents that can REPLICATE and/or die, and there may be VARIATION between agents in their responses to their environment, hence variation in replication and death rates. The rates at which processes occur generally slow down as one progresses up the hierarchy. In order to recognise levels in the hierarchy it is usually necessary for there to be some form of COMPARTMENTALISATION to define (even if quite loosely) the structures. In biology, these are typically membranes such as the mitochondrial membrane, the cell membrane, skin, reproductive incompatability (at the level of species). John Maynard Smith talks about [http://dannyreviews.com/h/Major_Transitions.html Major Transitions] in evolution that are typically accompanied by a new level of compartmentalisation followed by division of labour.
How to translate these ideas into cellula automata?
Here's our thoughts for a Hierarchical CA with compartmentalisation and different process rates (Is anyone aware of this being already developed??):
Define a fine resolution lattice (e.g. a million by a million pixels). Initialise (= the Big Bang). Apply some local rules for updating pixel-state based upon the eight neighbouring states. Iterate, say ten times, then aggregate the resulting pattern and view each 10x10 subunit of pixels as a new cell, with state 0 or 1 depending upon some threshold of occupancy or other renormalisation rule. The total arena is now 100,000 x 100,000. Apply the same (or different) local rules as at the finer scale. If a cell changes state all the fine-resolution cells also swap state. Now revert back to the finest scale and do ten more iterations etc, etc. Every 10^n fine-scale iterations the lattice will operate at level n in the hierarchy. Can we detect a relationship between fine-scale structure and coarse-scale structure?
Any takers?
Stephen Hartley
Is complexity Nothing But the behaviour seen in Class 4 automata? An interesting point raised by Ray Kurzweil (from the [http://www.kurzweilai.net/meme/frame.html?main=/articles/art0464.html full review]): :"Wolfram effectively sidesteps the issue of degrees of complexity. There is no debate that a degenerate pattern such as a chessboard has no effective complexity. Wolfram also acknowledges that mere randomness does not represent complexity either, because pure randomness also becomes predictable in its pure lack of predictability. It is true that the interesting features of a Class 4 automata are neither repeating nor pure randomness, so I would agree that they are more complex than the results produced by other classes of Automata. However, there is nonetheless a distinct limit to the complexity produced by these Class 4 automata. The many images of Class 4 automata in the book all have a similar look to them, and although they are non-repeating, they are interesting (and intelligent) only to a degree. Moreover, they do not continue to evolve into anything more complex, nor do they develop new types of features. One could run these automata for trillions or even trillions of trillions of iterations, and the image would remain at the same limited level of complexity. They do not evolve into, say, insects, or humans, or Chopin preludes, or anything else that we might consider of a higher order of complexity than the streaks and intermingling triangles that we see in these images." It seems to me (Marcus Frean) that Class 4 automata always show propagators of some sort and that this is what makes us see them as interesting. Propagators = solitons = patterns that conserve their form but move over time. But what's really so interesting about those?...
These are issues I am very interested in: The idea of compartmentalisation as a general phenomenom in evolutionary processes. However, I am very dubious about cellular-automata being able to produce the necessary kind of interactions for the kind of transitions that Maynard Smith and Szathmary consider in their book. Why? CA fails to differentiate between what I think are two importantly different properties: individuality and spatial location. Compartmentalisation requires the spatial aggregation of lower level individuals to form a higher level individual. Aggregation requires that individual and spatial location be separate distinguishable qualities. In CA being a cell (individual) is just being at a spatial location. How do you get around this in CA? Perhaps you can, but I doubt if what you end up with looks much like the traditional CA as you would have to track entities across cells (well, I can't think of another way...) Regarding your proposed CA: Note that what is important in the 'Major Transitions' is that the high level structure arises from the low level structure. Your CA above externally imposes the hierarchical structure rather than providing a means for it to emerge. The hard question is constructing a system that can evolve higher levels without directly programming these higher levels in. Note: I haven't read the Wolfram Book, I've just skimmed it and read some reviews, so maybe I'm off track. Brett Calcott
Is complexity Nothing But the behaviour seen in Class 4 automata? An interesting point raised by Ray Kurzweil (from the [http://www.kurzweilai.net/meme/frame.html?main=/articles/art0464.html full review]): :"Wolfram effectively sidesteps the issue of degrees of complexity. There is no debate that a degenerate pattern such as a chessboard has no effective complexity. Wolfram also acknowledges that mere randomness does not represent complexity either, because pure randomness also becomes predictable in its pure lack of predictability. It is true that the interesting features of a Class 4 automata are neither repeating nor pure randomness, so I would agree that they are more complex than the results produced by other classes of Automata. However, there is nonetheless a distinct limit to the complexity produced by these Class 4 automata. The many images of Class 4 automata in the book all have a similar look to them, and although they are non-repeating, they are interesting (and intelligent) only to a degree. Moreover, they do not continue to evolve into anything more complex, nor do they develop new types of features. One could run these automata for trillions or even trillions of trillions of iterations, and the image would remain at the same limited level of complexity. They do not evolve into, say, insects, or humans, or Chopin preludes, or anything else that we might consider of a higher order of complexity than the streaks and intermingling triangles that we see in these images." It seems to me (Marcus Frean) that Class 4 automata always show propagators of some sort and that this is what makes us see them as interesting. Propagators = solitons = patterns that conserve their form but move over time. But what's really so interesting about those?...
These are issues I am very interested in: The idea of compartmentalisation as a general phenomenom in evolutionary processes. However, I am very dubious about cellular-automata being able to produce the necessary kind of interactions for the kind of transitions that Maynard Smith and Szathmary consider in their book. Why? CA fails to differentiate between what I think are two importantly different properties: individuality and spatial location. Compartmentalisation requires the spatial aggregation of lower level individuals to form a higher level individual. Aggregation requires that individual and spatial location be separate distinguishable qualities. In CA being a cell (individual) is just being at a spatial location. How do you get around this in CA? Perhaps you can, but I doubt if what you end up with looks much like the traditional CA as you would have to track entities across cells (well, I can't think of another way...) Regarding your proposed CA: Note that what is important in the 'Major Transitions' is that the high level structure arises from the low level structure. Your CA above externally imposes the hierarchical structure rather than providing a means for it to emerge. The hard question is constructing a system that can evolve higher levels without directly programming these higher levels in. Note: I haven't read the Wolfram Book, I've just skimmed it and read some reviews, so maybe I'm off track. Brett Calcott
EResearch