Monday, March 15, 2010

More on Cellular Automata

Hi again!
So, ages ago I talked about the possibility of using cellular automata to generate lace patterns. A key step in this is to interpret the cellular automaton as a collection of rules for interactions between chains of digits, travelling left or right, or remaining stationary.
On closer inspection it turns out this is rather more complicated than I'd expected. The problem is that these interpretations can be influenced by neighbouring digits, so:
001
-1-

looks like it should to be a left-travelling chain, but if the neighbouring digits are:
0010
0110

then we need to see this as a chain bifurcating into left-travelling and stationary chains. Worse, if it was
00110
01100

we would probably want to see this as two left-travelling chains running alongside each other.
Because of these problems, I think it is impossible to interpret general cellular automata as chains in this way -- what's needed is a non-local approach. What can be done is to come up with a procedure to read through the pattern and divide each of the `1' digits into chains travelling left, right, or remaining stationary (and some `orphan' digits left by themselves). This is then fairly straightforward to convert into a lace pattern.
I feel this is cheating a bit, it's not really in the spirit of cellular automata and there are a lot of arbitrary decisions to be made. There are further complexities I haven't dealt with -- how do you deal with chains bifurcating? Or colliding? So far my chains are just left hanging.

Still, it generates some very nice patterns with some interesting features. Mostly though I'm just enjoying the idea of computer-generated lace, there's something magical about putting in a set of logical rules and generating a pattern.
So, applying this to rule 30, generating the pattern starting from a single `1', I get something like this:


(not sure how that'll turn out, but it's just to give an impression)

So, this turns out to be rather more complicated than I'd expected, and very much less canonical than I'd hoped. It does produce viable patterns though, and makes me rather keen to try to elaborate this method.

Pictures of the finished shawl soon!
Hugh.

No comments: