• Hyperlands
• 90 Degrees to reality
• Lightpath Gallery
• Digital Anthill
  • Cellular history
  • Automata types
  • My Automata
  • Links and Sources
• Code and Coding
• Miscellany
• World view
• Downloads

Types of Cellular Automata
Cellular automata can be classified in several different ways. On this page I'll explain the different systems for classification and how they relate to each other. This page, more than any other on this site, will get a little technical, but as the good book says 'Don't Panic'. Technical does not have to mean difficult to follow.
Each of the different ways of classification only classifies one particular feature of the automata, so each automata can belong to several different classes. The ways of classification I will discuss here are:-

Weather the automata is a series or parallel type
The number of dimensions the automata operates in
The level of complexity achieved

Series or Parallel
This is the most basic form of classification. And it's also probably the easiest to under stand. Basically a series automata is one where things happen in a serial form. The rules are applied to one (or perhaps many) squares and the 'state' of the universe is updated straight away. This is opposite to parallel types where the whole universe (every square on the grid) has the rules applied and then the whole lot is updated in one action, in other words in parallel.
Another way of looking at this is to say series automata are like ants (hence digital anthill), and only the squares that contain ants need updating. The ants look at the square it's in or around it and then uses this to decide weather to move and where to move to. A parallel automata could be looked as a single cell and each square in that cell is say a chemical that may react with chemicals around it. So the whole grid is the entity with a parallel automata where as a series automata can contain may entities.
Chris Langton called the series type of automata V-ants, hence my digital ants.

Number of Dimensions
This is not actually not quite as scary as it sounds. It merely tells us how 'far' around each square the rules 'look'. Automata could have any number of dimensions, but as you'll see things get very complicated once you get over 3 or 4.
You may recall form geometry lessons at school a 0 dimensional shape is a dot, no length, no width. And so a 0 dimensional automata looks no further than the square it's currently on. Langtons ants and Turks ants are examples of this type of automata. And despite the short-sightness of these ants, they can still display amazingly intricate behavior.
Next is, guess what, 1 dimensional automata. A one dimensional shape is a line, it has length but no width. So one dimensional automata can look either 'up' and 'down' or 'left' and 'right', but both.
This makes 1 dimensional automata particularly interesting to look at since you can have a line of them across the width of our screen and then use the height to show a history of the changes that have happened since the automata was started.This makes it much easier to see what is actually going on. There are also a much smaller subset of possible rules for this type. These two factors make 2 dimensional automata the most studied type. Stephen Wolffram has studied these extensively.
Moving up to the next higher dimension we come to 2 dimensional automata.As you may guess these are capable of looking both 'horizontally' and 'vertically'. The Game of Life and the Brain automata are examples of this type. With in this type there are serveral subtypes, the difference between the sub types being in what directions the automata can 'look' and just how far it can 'see'. These two factors give rise to what is called a neighborhood.
There are three types of neighborhood. Firstly we have the von Neumann neighborhood, named after the creator of the cellular automata John von Nenumann. In this neighborhood, they automata can look 'left' and 'right' as well as 'up' and 'down' to a distance of one square. This means that 4 neighboring squares effect each square (north, east, south and west). The Moore neighborhood extends this by allowing the automata to 'look' diagonally again to a distance of one square. This Moore neighborhood therefore has 8 squares in it (the von Nemann four plus north east, south east, south west and north west). The Extended Moore neighborhood, as it name suggests keeps the same basic Moore pattern, but extends it's range, so that an additional 16 squares are covered.
Next we come to 3 dimensional automata. These can now look 'above' and 'below'. And again, in theory at lest, could have neighborhood as described above. I say in theory because as far as I know no one has ever run any 3 dimensional automata. 3 dimension's need a bit bit more computing power to calculate, after all there could be up to 124 squares in an Extended Moore neighborhood. But it's not this that makes it so difficult to create a 3D automata. The main problem is that (so far at lest) all computer displays are basically 2 dimensional devices. Which makes it very much more difficult to see what is going on.
Since the automata is a theoretical construct, it need not be bound by the laws of our physical universe. So there is no need to stop at 3d automata. But the problems mentioned for 3d automata also effect these higher dimensions, but they are much, much greater. And again none of these higher dimensions have (yet) been explored.