Wednesday, June 16, 2010

Cellular Automata

think this one deserves an own topic. Cellular Automata, a model one might say strongly supported by Stephen Wolfram (author of A New Kind of Science). The technique first saw the light of day the 1940s by the hands of Stanisław Ulam who was studeing the growth of crystals and at the same time collaborating with John von Neumann who was working on a problem with self-replicating systems, the cellular automata was born.

A cellular automaton is a collection of "colored" cells on a grid of specified shape that evolves through a number of discrete time steps according to a set of rules based on the states of neighboring cells. The rules are then applied iteratively for as many time steps as desired.
Well, that sais it all doesn't it? No I thought so. Cellular Automata does not have its foundation in mathematics or physics, it's more of a model based on rules and movements. A visual representation of calculations if you may, and the result is really not just a answer to lets say - an equation, it's more like a display colors, patterns and states for the eye to judge.

The most famous cellular automata is probably Game of Life, created by John H. Conway. Every cell in the grid applies three sets of rules which follows.
  1. Death: if the count is less than 2 or greater than 3, the current cell is switched off
  2. Survival: if (a) the count is exactly 2, or (b) the count is exactly 3 and the current cell is on, the current cell is left unchanged
  3. Birth: if the current cell is off and the count is exactly 3, the current cell is switched on
The result will look something like this, and no it's not a demo of a videogame from the 1970s.

Every cell only knows its closest neighbours, no predefined paths or patterns are followed. The result is totalt emergent, same as for the Boids model.

Amazingly, life is a universal cellular automaton, in the sense that it is effectively capable of emulating any cellular automaton, Turing machine, or any other system that can be translated into a system known to be universal
This basicly means that a cellular automata can reproduce any system which by definition is universal. This is pretty powerfull stuff, and I recall reading about cellular automata beeing used for reproducing fungus growth on a microscopic level. Though I've failed to find a reference for this, but I will add it as soon as I do find it.

If we take a step into the 2100 century a demonstration of the cellular automata looks like this.

If you ask me, this looks like life under a microscope. Well, parts of it anyway. I will return to the cellular automata, but for now I will leave it to you for further reading.

- Tobias


Post a Comment