I decided to build a piece of software that allowed me to study the properties of Cellular Automata in a visual way. The first step was to build something that just prints the evolution of the Automaton to the terminal, according to specific rules.
This is the output for the Rule Corresponding to the famous Game Of Life (rule 23/3). I can specify a different rule from the terminal, a different size and a different probability of occupation of a given cell in the first generation.
Let's look at the rule called Stains (rule 2345/45678), with a probability of occupation of 0.1, and a board with 15x25 cells.
Notice it stopped at a point in time. The reasone why it stopped is it recognised the current state of the Automaton had already occurred before (let's say the Automaton is stable when this happens).
The interface allows us to run until stability in a fairly intuitive way:
while(!B.isStable()){
B.setNext();
std::cout << B;
}It is interesting to see how many steps until stability we need. The question here is: for a given probability of occupation and a given rule, how many steps does the automaton need until it reaches a state that it had already been in before? My initial guess would be a Gaussian distribution around a peak that was centered around some value that increased with the size of the board. I was.. uh... wrong.
Let's see the results for several rules.
Parameters:
- p = 0.6
- size = 10x10
- number of experiments = 1E4
The data was acquired using 2D_stability.cpp, and the histograms were made using the script GNU_steps_to_stability in the directory gnuplot_scripts/. All of the histograms have the same bin width, which is not ideal, but is good enough to give us an idea of how each rule behaves in terms of number of steps til stability.
We can now choose to focus on one of the rules and run the experiment with a higher number of tests. I chose rule LongLife (5/345) because it's not clear what the distribution looks like in the previous case.
Here is the result for 100x as many experiments. This took about 15 minutes to compute in my machine (with an Intel Core i7 2.4GHz).
The only intuition I had for the results was that the number of steps til stability should drop to zero when the probability was too close to 0 or 1. I decided to run a simulation to see how the average #steps to stability changes with the initial probability of occupation.
The results were obtained using the source file sts_occupation.cpp with the following parameters:
- 0 <= p <= 1
- size = 8x8
- number of experiments = 1E6
The idea is to run a number of simulations for each probability of occupation (0 <= p <= 1) and calculate the average number of steps to stability.
These are some of the most interesting results:
These images were produced using the script gnuplot_scripts/GNU_average_steps_to_stability_vs_prob.
It's time for some cool 3D plots. We'll now see how the number of steps to stability evolves with both the probability of occupation and the size of the grid. We will consider a squared NxN grid, with 1 <= N <= 9 and 0 <= p <= 1.
The previous result for Assimilation (4567/345) looks like a superposition of two peaks. Let's see if that's true by running the experiment for other grid sizes.