A New Kind of Science: The NKS Forum > Pure NKS > Interesting rule
Author
Franck Binard
University of Ottawa
Ottawa

Registered: Dec 2003
Posts: 17

Interesting rule

I have been looking at 2D moore neigh. CAs with range 1. The rules are 512 bit rules, next state is derived from previous 9 tiles. Bit i in the rule is for the ith 9 bit pattern, arranged from 000000000 to 111111111.

The 512 bit rule where the ith bit is set iff i mod 7 == 0 produces complicated patterns out of simple initial shapes (single bits). Straight lines will stay ordered, but will subdivide and act like waves. Block shapes will instantly become very complex by spreading and shifting patterns on every iteration.

I coded a simple implementation which can be opened here
esc to exit, 'z/x' to zoom in/out, left/right/up/down to translate, 'a' to stop evolution, f1 toggle full screen

In this case, the initial configuartion is a single bit positioned in the middle of the grid.

Attached are pictures of another simple configuration at different stages.
[These are now later in the thread]

__________________
Franck Binard
www.site.uottawa.ca/~fbinard

Last edited by Franck Binard on 12-21-2003 at 05:30 PM

Report this post to a moderator | IP: Logged

12-01-2003 03:45 AM
Jason Cawley
Wolfram Science Group
Phoenix, AZ USA

Registered: Aug 2003
Posts: 712

It would help if you gave the explicit, detailed form of the rule you are looking at...

Report this post to a moderator | IP: Logged

12-01-2003 10:21 AM
Franck Binard
University of Ottawa
Ottawa

Registered: Dec 2003
Posts: 17

Re: rule

The rule might be described in a NKS (but not sure as i don't have the book anymore).

I use the same notation as in NKS (using bits instead of diagrams)
Each block of 9 cells is centered at (i,j). The configuration for turning on the (i, j) cell is determined by the configuration of the
set of cells: {(r,s)| i-1<= r <=i+1, j-1<= s <= j+1}. Rules are coded over 512 bits (as there are 512 possible 9 bits configurations). The boundaries of the grid are considered to be 0 always.

For example, (in hexadecimal) rule 4000000000....
specifies a rule in which a cell lights only if the cell on its bottom right is set. rule 80000000... specifies a rule in which the cell lights when none of the cells on the tile on which it is built is on. .....001 will light only cells that are sitting on 9 turned on cells.

The rule i am looking at is obtained by the rule where the ith bit is lit iff (i mod 7 == 0) (the patterns are formed by cells that are turned off). By the way, the mod 5 and the mod 11 rules are also pretty interesting.

__________________
Franck Binard
www.site.uottawa.ca/~fbinard

Report this post to a moderator | IP: Logged

12-01-2003 03:47 PM
Franck Binard
University of Ottawa
Ottawa

Registered: Dec 2003
Posts: 17

Here are some more pics of a simple formation. In this case, the inital configuration is a 3x3 cube next to a 3 squares long vertical line.

Attachment: pics.zip

__________________
Franck Binard
www.site.uottawa.ca/~fbinard

Report this post to a moderator | IP: Logged

12-02-2003 01:36 PM
Todd Rowland
Wolfram Research
Maryland

Registered: Oct 2003
Posts: 115

The rule number for this 2D CA is Sum[2^(7 n), {n, 0, Quotient[512, 7]}] (154 digits).

Alternatively, one can use
CellularAutomaton[{1 - Sign[Mod[Flatten[].coef, 7]] &, {},{1, 1}}, init, k]
after defining the coefficients

coef7={4,2,1,4,2,1,4,2,1}

(i.e. from Flatten[Table[Mod[2^(3i-j),7],{i,3},{j,3}]]).

Unlike, the results in the last post, when one starts from an initial black cell on an unbounded grid, one gets a neat nested pattern. From the animation it is a bit hard to tell, but by looking at the slices it is apparent that it is a 2D version of rule 129. Also in the case of the 2D grid with the edges wrapped around as in a torus, the slices are the same as rule 129.

The interesting effect in fbinard's example comes from his boundary condition. The boundary cells are forced to be white cells on a finite grid. The reason this differs from the unbounded case is that the neighborhood of all white cells causes its center cell to become a black cell. So on an unbounded grid all the white cells turn black, and all black stays black. But here the boundary cells are always white, and that is a somewhat forced condition.

It appears to be quite formidable to attempt to predict the effects, so this is a type of NKS phenomenon, and even though there is forcing on the system from the outside, the specification is still simple.

For instance, look at the slice of this forced evolution compared to the evolution of rule 129 with its boundary also forced to be white cells. The case with rule 129 looks much more behaved.

Looking at the alternative rules of this type, one gets interesting behavior from a single black cell, even on the usual unbounded grid. Included in the attachment is the case for Mod[i,7]==1, where I substituted Flatten[].coef-1 in the code above.

The other pictures in the zip show this CA on an unbounded grid, and also with the boundary forced to be zero, in a similar manner to the way some 2D CA's are displayed in NKS, e.g. step by step on page 171 and looking at slices on page 175.

Here is the code I used to get the forced boundary picture in the case of rule 129.

NestList[CellularAutomaton[129, {#, 0}, 1, {All, {0, 114}}][[-1]] &, ReplacePart[Table[0, {115}], 1, 58], 119]

Attachment: mod7ca.zip

Report this post to a moderator | IP: Logged

02-06-2004 03:36 PM
Franck Binard
University of Ottawa
Ottawa

Registered: Dec 2003
Posts: 17

[NOTE: draft]

interesting rule

Looking at CA rules properties through genetic algorithm, following [Revisiting the Edge of Chaos: Evolving Cellular Automata to Perform Computations, genetic algorithm discovers particle based computation in CA - Mitchell, Hraber, Crutchfield Das as well as Packard and others]. Intent is to limit the size of the space for property search to rule space. in 2D, 2^512 for 1 sized neigh.

One of the questions that one might ask oneself, is what is it that makes a cellular automata interesting as opposed to not ?

While we generally understand Conway’s game of life to be interesting as soon as we look at it, there are many slight variations on the rules that we would immediately discard as being less interesting. But might not the same rules, applied in a different environment become interesting ?

As an example, let's (again) consider the game of life. If the rules are applied to an initially empty grid, is the game still interesting ? no. Because nothing happens therefore nothing interesting happens. What if the grid has only one lit cell ? Now, something happens, but only once. then nothing. And so, we get bored and move on. Thus, it is possible to make the game of life non interesting when the meta rule "and you will be allowed to light any configuration of cells at the start of the game" is not added to the game. However, the totalistic rules that fuel the game have nothing to do with the chosen initial configuration. In that sense, the elements of the game that are external to the rules of the game, elements such as the size of the grid, the border handling and the initial configuration of the game are all part of the environment in which the rule carries out its evolution. Yet, they can still make the difference between whether the game is interesting or not.

As an example of a non-interesting ca, consider rule 119 for 1-dimensional ca (described in NKS, pg 54). As it is shown in NKS, it appears a bit boring. A single lit pixel is the initial configuration, and the evolutions that are produced by the rule with this initial configuration are regular alternating rows of lit cells and rows of unlit cells. One thing that might be noticed about the rule as it is represented in the book, is that the product of its evolution looks exactly like the product of the evolution of rule 127. Yet the two rules are different. So one might ask: "what is the difference between the two rules ? where does it reside ?".

One way to answer the question would be to try different initial configurations and to follow the evolution of the 2 rules until we do see a difference. Since we are studying the rules themselves, there is no law that dictates that we need to start with a single lit cell. If the argument for the single lit cell is based on the simplicity of the initial configuration, then one might point out that both rules would produce the same behaviour if the initial configuration was an even more simple row of all unlit cells. At any rate, since the chosen initial configuration doesn't convey any sense of the information difference between the two rules, changing it until it does would be an appropriate way to find out where and how the two rules differ.
[HAVE TO FIND INITIAL CONFIG THAT DOES CONVEY THE DIFFERENCE].

Another way to find the difference between the two rules is to try to change the working of the rows in which the cells are placed. The environment that is used throughout the NKS book for the elementary rules is a row of cells. But there is an added specification to this environment: The row is a torus. It wraparounds. When a cell reaches a border, its immediate neighbour is the border cell on the other side of the row. This is a specification that is outside the scope of the rule. There is nothing in the rules that goes and gets that opposite cell in order to use it as a neighboring cell. The implementations of the rules do that. This is part of the environment in which the rule is applied. What happens to the evolution of rule 119 when we change that specification? Let’s stay that instead of having the cells placed in rows that are wraparound, we place them in rows that are terminated by cells that always remain unlit.
[WHAT HAPPENS ? STILL HAVE TO CHECK IT OUT. SHOULD PRODUCE A CA THAT HAS THE PROPERTY OF MEASURING THE SIZE OF THE ROW FOR ONE OF THE TWO RULES, AND SOMETHING DIFFERENT FOR THE OTHER ONE. ALSO DON'T FORGET TO SIMPLIFY INITIAL CONFIGURATION TO EMPTY ROW FOR BOTH RULE 119 AND 127]

In any case, both of the methods used above to differentiate the two rules require changes in the environments in which the rules evolve. Therefore, I argue any experiments designed to study the behaviour of any rule will involve nothing more than picking a set of appropriate environments in which to apply the rules. The rules themselves are never modified.

I propose that a fitness function that would evaluate rules for ‘interestingness’, would do so by studying the evolution of a rule in different environments. The elements of the environment being:

• the size of the grid,
• the border handling and
• the initial configuration.

Unfortunatly, there are an infinity of possible environments in which a given rule can be studied. How many of these should a fitness function consider ? Our search space is already (in 2D, moore-1) 2^512 big. Each of the rules, initially picked at random (and eventually crossed with one another) is then studied in e environments. The studying itself requires the evaluation of several evolution steps. What is the optimal e? We think it depends on the rule itself.

I furthermore propose that the chosen environments that the fitness function will use to study the rules be designed specifically based on the rule itself [more on this later]. In other words, not only should the fitness function evaluate the rule for "interestingness", it should also design environments based on the composition of the rule it is studying in order to conduct its evaluation experiments.

Looking at the ways the rules are constructed, and on the effect of each of the 512 bits of the rule on the evolution, we (with Etienne Vincent from the University of Ottawa) think we might have begun to see a pattern in the design of rule specific environments.

In the game of life, the state of each cell is specified by its range 1 moore neigh. As there are 512 possible different configurations for such a neigh., one could specify 2^512 different rules, one of which is the game of life. Of course, of the 2^512, only a small subset are totalistic (including the game of life), but there is no reason to assume that totalistic cas are the only one that are interesting. in fact, there is a plethora of examples in NKS that point to the contrary.

----------------------------
Fitness Function [incomplete].
Algorithm.
Devise a set of grids that are constrained in relation to rule.
for example (2D moore-1):

Given cell and 512 bit rule:

• if bit indicating that cell should light if neigh is completely unlit (half search space), evaluate 0-bordered totally empty (in the fashion of the rule described at beginning of post)

Apply rule to each grid and grade evolution of grid according to [WHAT]

evaluation criteria
So what are the criteria that would tag a rule as being an interesting rule?

• rarity. Noteworthy scarcity is interesting. We know that because we tend to be more interested by the combinations of patterns and rules that produce something unusual or unexpected in some respect. This is however especially true when the behavior has the potential to benefit us by solving a problem. As an example consider rule __ and __ in NKS. What makes them particularly interesting is that...

• emergent computation (or the appearance of). An evolution that reminds us of something of some other process is interesting.
For example, gliders, guns and spaceship are all examples of emergent computations, and the discovery that a rule has the potential to evolve such objects adds to its interestingness.

• the difficulty of predicting futur evolutions. the shorter the repeat length is, the less interesting the rule is. This goes back to the game of life example when started with an empty grid. Since the repeat rate is 1 from the beginning, the game gets boring rather quickly. It is already more interesting with a single lit cell since the first evolution offers some variety.

----------------------------
crossover function

----------------------------
mutation function

---------------------------------------------
Working with Etienne Vincent, we eventually found a rule that didn't require any initial conditions (ie, all initial bits unlit) in order to become (or to appear) complicated. As before, the complication is created from the border handling, but the rule then does the rest.

The 512 bit rule is based on the function:
ith bit = (i mod 3 == 2) OR (i mod 7 == 0)

A binary that illustrates the evolution of the rule can be opened here

i am trying to design a set of experiments that would facilitate the rating of rules by a fitness function for properties such as emergent computations independently of initial state. while evolution part of algorithm is random, the fitness function should be deterministic. Original idea was to evaluate a set of simple cell formation according to yet undecided list of criteria.

hoping this might lead to a good way to explore a rule and its properties independently of its initial state.

Franck Binard

__________________
Franck Binard
www.site.uottawa.ca/~fbinard

Last edited by Franck Binard on 02-23-2004 at 03:04 PM

Report this post to a moderator | IP: Logged

02-08-2004 07:18 PM

wolframscience.com  |  wolfram atlas  |  NKS online  |  Wolfram|Alpha  |  Wolfram Science Summer School  |  web resources  |  contact us