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);

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

This entry was posted in Math. Bookmark the permalink.

One Response to Celular automata – generating chaos with simple rules

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s