MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Gravitons are presumed to change the shape of space-time, and if there are enough of them, perhaps even its topology. Does anyone know of any cellular automata that, say, change the neighborhood based on the density or topology of clumps of "on" cells, or similar?

[This question was first asked on the math-fun mailing list.]

share|cite|improve this question
Isn't all cellular 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
If I may guess Paul's intention, cellular automata generally have a fixed neighborhood size upon which the rules are based. But it is certainly conceivable to allow the neighborhood size to grow or shrink during the simulation depending on the density of live cells. Changing the topology on the fly is less clear to me, but perhaps neighbor-adjacency could be altered. – Joseph O'Rourke Jun 30 '10 at 20:57
Wolfram suggests something like this in "A New Kind of Science" when he vaguely outlines an almost-CA approach to a grand unified theory; his method seems to violate Bell's inequality, though. – Daniel Litt Jun 30 '10 at 21:12
@Joseph: ah! With your interpretation and re-reading the second sentence in the question, the answer makes more sense. But to simulate something like gravity, wouldn't the "affected" neighborhood by a clump change, rather than the "dependent" neighborhood (more mass gives longer range influence)? Then this rapidly leaves the realm of CA as each cell effectively has to check all other cells (not just neighboring ones) to know if their effects should be counted. On the other hand, changing the "dependent" neighborhood may be a good way to model some (not sure what) nonlinear effects. – Willie Wong Jul 1 '10 at 1:37
Perhaps the various "quantum cellular automata" models are relevant? For example, "Unitarity plus causality implies localizability," Pablo Arrighi, Vincent Nesme, Reinhard Werner, . – Joseph O'Rourke Jul 1 '10 at 1:38

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

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.)

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.