Lets consider linear cellular automata with Wolfram rule 90
Elementary cellular automata is essentially string of two symbols, lets call them 0 and 1, equipped with rules (and starting configuration, of course)
Rule takes symbol in the position, as well as left and right neighbors. Ie – when calculating symbol of the cell, we should consider 3 cells, cell to the left, cell itself and cell to the right.
Ie – suppose we have set of rules(*):<em>111 - 0</em><em>110 - 1</em><em>101 - 0</em><em>100 - 1</em><em>011 - 1</em><em>010 - 0</em><em>001 - 1</em><em>000 - 0</em>
Or graphically:
So if we have 10011 for starting configuration, calculation goes like this(from top to bottom):
| 1 | 0 | 0 | 1 | 1 |
| (0) | 1 | 1 | 1 | (1) |
| (1) | 1 | 0 | 0 | (1) |
(italics) means that we dont know which symbol is to the left and right to the starting configuration, for simplicity I consider here absent symbols to be 0s (ie …00000100110000…)
Now, what is 90, which is called Wolfram rule.
It is obvious, that 3 cells define state, and since we have two symbols, all possible combinations are , and since we have two possible symbols for each combination – rule of CA can be expressed as (0,2⁸=256) number.
90 in binary would be (*), which is enough to describe elementary ca behavior.