From: David Hillman (dhist1+@pitt.edu)
Date: Fri May 21 1993 - 22:07:54 UTC
In article <13594@tiglio.rl.ac.uk> arno@inf.rl.ac.uk (Arno Siebes) writes: >The second question, which is related to the first, what is >known about a Life-like system, with a finite grid as above, but >in which the topology can be changed (that is, cells can acquire >new neighbours and discard other)? Can't help with your first question (universal computation). As for changing "topology": some work has been done in this area. First, note that a change in grid structure need not be seen as a change in topology. One may, for example, triangulate a sphere in many different ways; all may be seen as discrete models of a sphere. Imagine an initial triangulation of a sphere in which, say, each vertex is colored black or white, and a local law in which the triangulation changes. The grid structure changes but the topology (sphere) remains the same. To distinguish the two cases, call the change in grid structure a change in geometry. Then, yes, laws exist in which the geometry changes over time; and laws also surely exist in which the topology changes over time (though I have no examples of one). Now much work has been done concerning ONE-dimensional cellular-automaton- like systems in which the geometry changes. These are L-systems. In one dimension there is not much way in which the geometry can change. One has a state of the universe consisting of a loop of cells. The geometry changes by changing the number of cells in the loop. It is easy to construct a local law which does this. L-systems typically work with strings instead of loops. Most work on L-systems concerns laws with neighborhood size one. These are non-interactive systems: a single cell at time t produces zero or more cells; the state at time t+1 is obtained by stringing these cells together in the obvious way. But there has also been work done in which the neighborhood size is bigger than one; these can have interactions and are thus more like your usual cellular automata. Extensions have been worked on also in higher dimensions: L-systems have been generalized in several ways to laws on arbitrary graphs, or to laws on specific sorts of 2-dimensional graphs. As far as I know, these extensions all involve laws which are NOT interactive (I might easily not know, however). Historically, the primary motivations for studying L-systems seem to be linguistic and biological: thus, e.g., a lot of emphasis on growth. One can easily have growth without having any interactions between the pieces of the universe. And it's easier not to have them. Hence, as they stand I assume that these higher-dimensional models do not behaviorally resemble typical higher-dimensional CAs. Many books have been written about L-systems, by (or edited by) Lindenmeyer (who invented them in the 1960s), Rozenberg, Salomaa and probably others Note one difficulty in higher dimensions: typically one wishes to have a finite set of allowed neighborhoods; one must construct the law in such a way that it guarantees that any allowed state at time t leads to an allowed state at time t+1 (one in which all neighborhoods are in this finite set). In the CA literature the only thread I know of addressing the question of changing geometries begins with an article called "Structurally Dynamic Cellular Automata" by Andrew Ilachinski and Paul Halpern in Complex Systems 1 (1987) 503-527. (There are several follow-up papers written or co-written by Halpern.) They discuss the problem in general and then offer an example in which there is a 2-D grid, the vertices are fixed over time but the edges can move around (thus the neighborhoods of the vertices change). Hope this helps. David Hillman dhist1+@pitt.edu
This archive was generated by hypermail 2.1.7 : Tue Oct 14 2003 - 21:44:14 UTC