Cellular Automata

I have recently been reading all about cellular automata, most recently extolled by Stephen Wolfram (creator of Mathematica, a computer programming language) in his book 'A New Kind of Science'.

The basic idea is that you start simply with a long line of squares, or 'cells', across a page. A cell can be either black or white. At regular intervals of time a new line of cells is drawn on the page immediately below the first (like an old refreshing monitor). Whether a cell on this second line is black or white depends on a rule applied to its two nearest neighbours on the first line. All sorts of rules can be immediately thought of: 'If a cell on the first line has a white cell on its right then it must be black on the second line, otherwise white.' This quickly generates a pattern of some sort that may (or, amazingly, may not) stabilise into a static or repeating pattern.

To latch onto 'amazingly' in the above paragraph: Wolfram discovered a rule, number 30, which led to a totally random result: one that did not stabilise into a static or repeating pattern but which just threw out a totally random sequence.

However, far far more interesting was rule 110 (picture above, showing the most common result of this rule). This rule threw out a result that was neither totally random nor completely repetitive; localised structures are created which interact in very complicated looking ways. In fact, it turns out some of these structures (different results are obtained by an infinite variety of starting states) are rich enough to support 'universality' - in other words they can represent everything. This, in theory, paves the way for a Turing Machine, a computer capable of every type of calculation!

So, the obvious question becomes: is the universe the product of a cellular automaton?

Unfortunately, this would require some external 'clock', which doesn't seem compatible with anything we can presently point to... or maybe we just haven't found it yet...