## Celular automata – generating chaos with simple rules

Consider a matrix having $n$ lines and $2n+1$ columns. The contents of the matrix is filled with 0 or 1 based on the following rules:
1. First line is full of zeros except the central element (position $n$ for 0 based index as in C++, C#, Java etc, and position $n+1$ for Matlab, Pascal etc) wich is 1. For $n = 3$ the first line will be: 0 0 0 1 0 0 0
2. The line $k+1$ is computed based on line $k$. Each element is computed based on the three upper neighbours. Thus for each combination of the possible values for upper neighbours we need to specify a value: 0 or 1
000 -> $a_1$
001 -> $a_2$
010 -> $a_3$
011 -> $a_4$
100 -> $a_5$
101 -> $a_6$
110 -> $a_7$
111 -> $a_8$
where $a_1, a_2,...,a_8$ can be 0 or 1.The array $\overline{a_8...a_1}$ is the base 2 representation of a number between 0 and 255.
For simplicity the first elements of each row are always set to 0 because for those elements only two out of three upper neighbours are known.

Based on this rule different patterns can be generated. For example if $\overline{a_8...a_1}=90$ and $n = 261$ the following pattern is generated:

Here is the Matlab code for generating patterns:

function [] = automata()
n = 261;
m_in = zeros(n, 2*n+1);
rule = [0, 0, 0, 1, 1, 1, 1, 0]; %rule 30
%rule = [0, 1, 0, 1, 1, 0, 1, 0]; %rule 90
m_out = generate(m_in, rule);
imshow(1 - m_out);
%---------------------------------------------------------------------
function [o] = generate(m, rule)
problemSize = size(m, 1);
%starting alue
m(1, problemSize+1) = 1;
mid = problemSize+1;
%for each row
for row = 2:problemSize-1
%for each column
for col = mid -(row-1) : mid +(row-1)
i1 = m(row-1, col-1);
i2 = m(row-1, col);
i3 = m(row-1, col+1);
%based on te values from the previous row
%and based in the rule generate the values in
%current row
n = i1*4+i2*2+i3;
m(row, col) = rule(8-n);
end
end
o=m;

A particular interesting pattern is generated by rule 30. This is how it looks for $n = 261$:

Compared to other rules, a chaotic pattern is generated (see the right side of the result). Rule 30 shows that using simple evolution rules, and starting from something basic (a single value of 1 in this case) something complex can be generated.
This lead to the following idea: what if the universe was generated in a similar way; A simple initial state and a simple rule that evoluates  in time and lead to the complexity that we see around?

Source:  Stephen Wolfram, “A New Kind of Science”, http://www.youtube.com/watch?v=_eC14GonZnU