On Wed, Jun 30, 2010 at 11:29 PM, Steve Witham <sw@tiac.net> wrote:

...

From: Mike Stay <metaweta@gmail.com>

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

Oh sure here's a dump of my refs and ideas to follow up on one day, forgive if this is all old hat to you:

Do you want your automaton to be quantish?  Because the way attraction works in QM is a quantish thing, and the graviton is a concept for fitting gravity into QM.  And yet, simulating a multiverse that branches at every spacetime point takes a lot of computer cycles.

Not at this point; I'm just interested in CAs that potentially change the shape or connectivity of their cells. I was imagining something like in the game of Go, where a group of stones has to be surrounded entirely to be removed from the board; in a CA, perhaps they could change state based on the proportion of perimeter to breathing room.

"Topological Quantum Field Theories" (TQFT) seem to be about a graph- structured spacetime built out of spinors.  With no particles other than the spinors that make up spacetime, but hey, they say it has something like gravity.  John Baez wrote a math-lite intro to TQFT but I can't immediately see it in the haystack of his TQFT stuff. Cobordisms are the new rubber sheet, man.

So, a TQFT is a monoidal functor from nCob to Hilb. Baez covers Fukuma, Hosono and Kawai's approach to constructing such a functor in weeks 6,7,8 of his Fall 2004 QG lecture notes: http://math.ucr.edu/home/baez/qg-fall2004/ Here's a pretty good paper that looks at TQFTs in the context of functional programming and linear logic: http://math.ucr.edu/home/baez/rosetta.pdf ;)

Try googling the phrases "graph rewrite", "graph rewrite/ing automata", "graph automata", "cellular graph automata."   http://en.wikipedia.org/wiki/Graph_rewriting

OK, thanks.

It's very interesting trying to design automata that reshape spacetime as they work, even if you're not being quantish, since you don't want to get into a situation where the next step from a point is sideways or backwards into already-calculated territory. You might get somewhere if you could figure out a non-arbitrary way for history to be rewritten, but that might just lead to brownean motion in state space that might be interesting theoretically but wouldn't push simulations ahead very fast.

But on the other hand, any model with a global timestep isn't relativistic, is it?  Although Ed Fredkin (for one) says you can have a regular fixed background grid and still have relativity.

That seems reasonable; I'd like to see a proof.

Have you read Verlinde's paper introduced here?   http://en.wikipedia.org/wiki/Gravity_as_an_entropic_force He introduces entropy force by explaining how entropy (and a heat bath) are what make rubber bands pull...and then goes on to entropy's effects on holographic representations... but why not just model a rubber sheet in a heat bath?

Oooh! Looks fun.

Note 14 from that wikipedia article is, http://arxiv.org/abs/1001.3808v1   "We point out that certain equations which, in a very recent   paper written by E. Verlinde, are postulated as a starting   point for a thermodynamical derivation of classical gravity,   are actually consequences of a specific microscopic model of   spacetime, which has been published earlier. "

Even an automaton with 1D of space, 1D of time, and gravity would be interesting.  You sort of want momentum, how would you get momentum?

Dunno.

(I've wondered whether it's possible to have a 1+1D automaton with a Lorentz transformation, ie a way to rotate the picture in space vs. time by some angle while preserving (in some sense) the history and automaton rules.  But that's special relativity.)

'T HOOFT, Gerard, A two-dimensional model with discrete general coordinate-invariance. Physicalia Maga zine 12 (special issue in honour of R. Brout's 60th birthday) (1990), 265-278. Eds. P. Nicoletopoulos and J. Orloff. If you google the title there are hints of a preprint around, I haven't got a copy.

OK; I knew he'd done CAs that were quantish (they behave like a quantum field if you zoom out far enough) but I didn't know he'd done anything on relativistic CA.

That's from the refs (which I seem to have) to "Invertible Cellular Autamata: A Review,"  by Tommaso Toffoli & Norman H. Margolus, which I don't have, but is in Physica D 45 (1990), a special issue reprinted as the book _Cellular Automata_: Theory and Experiment_, Howard Gutowitz MIT Press, 1991 ISBN 0262570866 and 9780262570862

another article in that book: SMITH, Mark, "Representation of geometrical and topological quantities in cellular automata."

Thanks! -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com