Todd Rowland
Wolfram Research
Maryland
Registered: Oct 2003
Posts: 103 |
Walls in Rule 73
Rule 73 has {0,1,1,0} as a static structure, regardless of the neighboring cells, which serve as walls (A). These walls effectively divide up space into separate regions, preventing information transfer between them, as discussed on p.699. The text suggests that if any run of consecutive blacks cells is odd then no walls will form. The conditions are a bit more complicated than that though, as demonstrated by {1,0,0,0,0,1} (C).
Also, the notes on p.885 and p.954 suggest that any even-length run of black cells will lead to a wall, or a structure which prevents information transfer, but it is also actually more complicated. For instance, {1,1,1,1} forms a growing cyclic pattern (B), which is a fairly common pattern for rule 73, and an example of information transfer can be seen by comparing graphics (E) and (F).
What is true is that if the runs of black cells and the runs of white cells are all of odd length, then no walls will form. The basic reason we can talk about rule 73 in this way is that it acts on runs of same color cells in a local way, without interference from the neighboring runs. After one step, a sequence of n black cells, delimited by white cells, becomes a black cell followed by n-2 white cells followed by a black cell. After one step, a sequence of n white cells, delimited by black cells, becomes a white cell followed by n-2 black cells followed by a white cell. When n==1, the cell becomes a white cell in either case. So if all the runs of white and black are odd, then on the next step all of the runs of black are odd. To see that the runs of white cells are odd, it suffices to check all possible cases. There is a unique degenerate case where an even run of whites is produced. It has to have a wrap-around boundary, and a sequence of alternating white and blacks (so the total length has to be even also). But in that case, the evolution reduces to alternating all white and all black. No structures {0,1,1,0} form in that degenerate case (D).
From the above analysis, it is clear that any run of black cells of length 4n+2 or any length of white cells of length 4n will produce a wall in its center after 2n steps, as can be checked by running those initial conditions.
The text on p.699 suggests that wall formation might play a role in universal behavior of rule 73. It seems like wall formation is an irreducible property in general, which is a good sign for universality. For instance, note the wall formation in graphic (F), which depends on the information transferred, compared with graphic (E) which has no walls.
Todd Rowland has attached this image:
Report this post to a moderator | IP: Logged
|
04-05-2004 04:35 PM
