Registered: Jul 2004
Posts: 1

I wrote a Java applet which I hope this forum will find interesting. The applet demonstrates how elementary cellular automata can be coarse-grained in space and time and is located at:
http://www.weizmann.ac.il/home/israeli/cgca.htm
It implements ideas from a recent publication by Nigel Goldenfeld and myself (Phys. Rev. Lett. 92, 074105 (2004)). A link to the paper can be found in the applet site. These ideas were already discussed in this forum under the thread "Pure NKS > Physical Review Letters paper on Course Graining"
(http://forum.wolframscience.com/sho...hp?threadid=253). In particular, Seth J. Chandler has posted there (post #4) a Mathematica implementation of our paper accompanied by clear explanations of the basic ideas.

I will be happy to hear any comments or suggestions.
Thanks,
Navot

Report this post to a moderator | IP: Logged

Registered: Aug 2003
Posts: 712

Look at rule 54 with multi-color size 6. It gives a 62 color coarse graining that brings out the phases in the background and particle-like faults between structures. The coarse grained critter looks like it might be programmable. Certainly there is a lot going on in rule 54, more than might first appear. This suggests looking at larger structures in rule 54 might help one see how one might program it.

It has a simple periodic background. From a simple initial that is all you get. But it can have regions with this background in different phases. As separators, there are right and left moving, minimalist "particles", which are simply offsets between phases of the background. (Thomas Coffee at this year's summer program at Brown pointed out the general relationship between particles and separated possible backgrounds, while working on structures in 110). Also vertical white triangle regions, which interact with these offsets, and "emit" them when they themselves shift.

I noticed how much there is in rule 54 when looking at sequences generated by the elementary CAs. 54 gives the most interesting series, if you just total 1s across each line. The reason is these background phases give a fluctuating series but that fluctuation changes in amplitude as the size of region in each phase walks around. While small scale class 3 randomness is also seen when those mostly cancel, corresponding to the regions dominated by the triangles.

Rule 54 is generally classified as a class 3 rule. And one of the main open problems in pure NKS is to prove any class 3 rule is universal. 54 is a good candidate, among the elementary CAs. One might also consider 3-4 color rules that have the same behavior with their first 2 colors, to give oneself more "wiggle room" for a universality proof. Some might quibble about whether is it "still" class 3. But one would be closer than we are now to a class 3 proof.

The more general point is that course graining can be seen as a kind of "transform" that highlights certain things going on in CAs and ignores - filters out others. Useful for analysis of their behavior, therefore. But it also shows that being able to course grain a CA does not mean the behavior seen will necessarily get simple. A 62 color range 1 rule showing class 4 looking behavior is by any standard a complex system.

Report this post to a moderator | IP: Logged