Maybe you mean something like stuff I've worked on?

http://arxiv.org/abs/hep-th/9805066

Don't know if it should be called a CA anymore, when it's not on a fixed lattice, but: suppose your space is a circle or line of cells made with 3 colors (call the colors a,b,c). The cells should be thought of in this case as having arrows on them so that all arrows point in the same direction. When we write down a product of colors, think of this as a row of cells with arrows going from left to right. When we write the cells in square brackets such as [abbc], think of it as a circle of cells (take abbc and join the end to the beginning in the obvious way). Here is an invertible function that changes the number of cells:

- replace all occurrences of ab with c and all occurrences of c with ab

So for instance if your space is a circle [ababcba] it becomes [ccabba]

Composing functions like this together can give something complicated. For instance if you do in this order:

- replace all ab's with ac's and vice versa
- replace all ab's with c's and vice versa
- do the permutation (acb) (i.e., change a to c, c to b and b to a)

as your law of evolution, and you start with [ab] as your initial circular state, in 183 steps you will return to [ab], having reached a width of 11 somewhere in the interim (see p. 14 of the above link for details). For many laws of evolution a small state typically evolves into states which get larger and larger, forever (like a big bang, except since the law is invertible you can also evolve it backwards in time, in which case it also gets larger and larger forever).

The same sort of thing can be done in higher dimensions, where the topology can also be made to change if you wish. Whether this relates in any important way to gravitons and general relativity, I don't know.

(Note that 1-d maps like the one described above are studied in symbolic dynamics, where they are called flow equivalence maps between subshifts of finite type.)

allcellular automata based on changes originating from "density" of on cells in the neighborhood of a cell? I apologize if I completely misunderstood your question, and would appreciate it if you clarify what you mean by "neighborhood", "density", and "topology". – Willie Wong Jun 30 '10 at 19:29