Registered: Apr 2006
Posts: 10

Hey everyone

I think I'm missing something obvious here in the mechanics simple CA but I am a little confused as to how to deal with the boundaries in writing CA programmes? (I dont have mathematica, but even if I did I would want to code it directly anyway - its a good way to really learn how it works).

Take for example a 5 wide "system" following rule 30.

00100
?111?
??0??
?????

You always need to know the state one further to the left or right than the boundary to determine behaviour on the boundary, and this unknown region grows.

The options I see are:

1) If you assume all cells outside the boundary are zero (or one) then this is easy to implement but can introduce some annoying noise in the system.

0_00100_0
0_01110_0
0_11001_0
0_10111_0
0_10100_0
etc...

An interesting implication of this is that just outside the boundaries the system follows different rules. For example consider the start of the 4th row which is 0_1. Presumably ALL cells to the left of the system should be zero, but this then implies that 00_1 should produce a zero in row 5 when under rule 30 it in fact produces a one.

2) You can wrap around so that the edges are next to each other - but this can also introduce annoying noise

00100
01110
11001
00111
11100
etc

Note after 3 steps this already has different results to option 1).

3) Start with additional initial conditions such that after n iterations it has shrunk to the size you wanted it in the first place by only calculating where you have all required data (an upside down triangle would result). This is a little computationally expensive however...

00000_00100_00000
?0000_01110_0000?
??000_11001_000??
???01_10111_10???
????1_00100_0????

After 3 steps this is different to 2) and after 4 steps it is different to both options above.

The above examples only start with a single black cell so i can see a few computational shortcuts since the "speed of light" is only one. However with random initial conditions you don't have this luxury

I found only a short discussion of this in NKS on page 866 which suggests using the wrap around method. However I notice in the majority of diagrammes in NKS the impact of the wrap around effect does not show. In many cases where a pyramid structure appears the system ends where the base of the triangle is as wide as the "system".

However in many examples (such as page 29 or 30) the expected behaviour of a wrap around system is not evident. This suggests to me the diagrammes may have been much larger originally and cut to show the relevant behaviour which is admittedly a sensible approach but then I assume this was done as option 3 above?

As I said, I'm sure I'm missing something rather obvious so any advice on the best way to deal with this in code (or in general) would be very much appreciated.

Cheers
Ian

Report this post to a moderator | IP: Logged

Registered: Aug 2003
Posts: 712

The usual ways are either to have an infinite background of uniform values, and track the pattern in the middle of it, or to wrap the boundary, called cyclic boundary conditions. The infinite background can be all 0, a typical default, but can also be any other cell value or a repeating block.

In the built in CellularAutomaton function, these are implemented by different forms for the initial condition argument, the second. (First is the rule specification, and third is steps).

So for example -


CellularAutomaton[30, {0,0,0,0,1,0,0,0,0}, 5] 


- is interpreted as cyclic boundary, since the initial condition argument is a flat list. Thus once the pattern grows beyond the initial block of zeros, it will not keep growing, nor import a fixed boundary of 0s, but will instead wrap.

But if you ask instead for -


CellularAutomaton[30, {{1}, 0}, 5] 


- you will get a single 1 cell in an infinite background of 0s. The function will track the locations that can be reached by the initial given the form of the rule, and return everything within that window. Thus for a 5 step range 1 rule, the output returned would be 11 wide. For 10 steps, 21 wide.

To get a repeating background that isn't all 0, you just put it where that 0 is now, a list for a repeating block. To get a wider initial in the midst of that repeating background, just lengthen that inner {1}. For example -


CellularAutomaton[30,{1,1,1,1,1,1},{0,0,1,0}, 20]


That says, start with 6 1s in a background of repeating 0,0,1,0 blocks. Since those make a definite structure, there will be a regular import, in effect, from the edges of the pattern - which will in general be different from step to step and different on the right side or the left, etc. All calculated as though the initial extends forever, but only the slice through it as wide as the {1,1,1,1,1,1} part could reach, shown.

Report this post to a moderator | IP: Logged