Make it simpler- 1D cellular automata

The problem with two-dimensional CAs, like the one described above and like Life, is that they are just too complicated to analyse in detail.

The first important contribution that Wolfram made to the theory was to reduce the situation to the point where it could be analysed. He decided that a one-dimensional CA would be worth investigating.

The idea of a 1D CA is no different from a 2D one but we start off with a line of agents and at the next tick the line is replaced by a new line determined by the rule that is being followed.

As this is only a 1D arrangement we don’t actually have to replace the existing line, just display the new line underneath, so building up a complete pattern of the development of the CA. It’s also possible to specify the rule in terms of the color of the agent, its two neighbors and the color of the new cell just below.

For example the pattern:

specifies a rule that if an agent is white and has two black neighbors then the cell below should be black.

As there are only eight possible arrangements of neighbors a complete rule that specifies exactly what should happen in any situation only has to list if the result of each of the eight is black or white.

By thinking of black as 1 and white as 0 you can give each neighbor pattern a number between 0 and 7 and then read off the resulting black or white cell on the next row as a set of eight zeros or ones, i.e. a binary number. This can be used as an index to specify the rule.

This means you can refer to any of the 256 rules that are possible in a 1D CA by number. This in itself is something of a conceptual breakthrough because now you can begin to think about classifying the behavior of each of the possible rules.

This is exactly what a biologist would do when confronted by a new biosphere. Once you have classified what you are looking at you can start to see patterns and make theories up about what you are looking at.

Without classification you are simply looking at an undifferentiated mess, no matter how interesting it might appear.

Wolfram examined all 256 of the rules by simulating them and discovered that there were four classes of behavior.

• Class 1 behaviors were boring, just resulting in all on or all off states.
• Those in Class 2 were also fairly boring and resulted in stable states, only slightly more interesting than Class 1.
• Class 3 produced disordered behavior – random triangles and “video noise”.
• Finally Class 4 displayed complex behaviors that included “Life-like” patterns. Class 4 patterns demonstrate that even 1D CAs have enough complexity to produce interesting behavior.

Rule 90 looks to produce a nice regular pattern so its in Class 4.

Many of these 1D CAs produce interesting patterns and they are fun to play with. Not quite as impressive as fractals from a graphics point of view but given the amount you put in you seem to get a lot out – and of course this is the point!

You can generalise 1D CA so that their rules are more complex by allowing them to be more than just black and white. In the book Wolfram claims that a 2-state, 3-color CA is the simplest possible  universal Turing machine (it had already been proved that no 2-state, 2-color CA could be). That this is so was proved in 2007 by Alex Smith, an undergraduate at the University of Birmingham (UK), who won a $25,000 prize put up by Wolfram as part of the celbrations of the 5th anniversary of NKS, see The Prize Is Won; The Simplest Universal Turing Machine Is Proved

If you go back to the discussion about rules and theories you will see that this is exactly what should interest us. When a simple rule produces complex behavior then it could well be a theory of something, if not of everything!

<ASIN:1905986203>

<ASIN:981238183X>

<ASIN:0262200600>

<ASIN:0262581116>