Cellular automata

Introduction

Arjen Markus (26 August 2002) A few years ago cellular automata were "in vogue": they formed a new type of mathematical objects that had rather interesting properties. Given a few simple rules, they could exhibit a wealth of structures. The most famous one of all: the Game of Life.

I recently came across them again and concocted this little script. If I remember the rules correctly, it is an implementation of the Game of Life.

Remark: as noted below by DKF the rules are definitely not those of Life. However, it is rather dynamic :)

The idea:

  • A cell gets a new state (0 or 1) depending on its own state and that of its neighbours.
  • In the case shown the rules are very simple: count the number of "live" neighbours.
  • If it is even, then the new state of the centre cell becomes 0. Otherwise it becomes 1.

The rules are found in the proc newCellState.

Note: I paid little attention to customisation or presentation. Just watch and be fascinated.

Program 1


 # cellular_automata --
 #    Implement simple two-dimensional cellular automata
 #

 package require Tk

 # displayState --
 #    Display the current state
 # Arguments:
 #    window   Window to update
 #    cells    Cells array
 #    state    State array
 #    nocols   Number of columns
 #    norows   Number of rows
 # Result:
 #    None
 # Side effects:
 #    Display the new state by chnaging the colour of the cells
 #
 proc displayState { window cells state nocols norows } {
    upvar #0 $cells cellId
    upvar #0 $state newState 

    for { set j 0 } { $j < $norows } { incr j } {
       for { set i 0 } { $i < $nocols } { incr i } {
          $window itemconfigure $cellId($i,$j) \
             -fill [lindex {white black} $newState($i,$j)]
       }
    }
 } 

 # calculateNewState --
 #    Calculate the new state
 # Arguments:
 #    window     Window for display
 #    cells      Cell IDs
 #    old_state  State array holding current state
 #    new_state  State array holding new state
 #    nocols     Number of columns
 #    norows     Number of rows
 # Result:
 #    None
 # Side effects:
 #    Set new values in the array new_state
 #
 proc calculateNewState { window cells old_state new_state nocols norows  } {
    upvar #0 $old_state state
    upvar #0 $new_state newState
 
    for { set j 0 } { $j < $norows } { incr j } {
       for { set i 0 } { $i < $nocols } { incr i } {
          set ie [expr {$i+1} ]
          set iw [expr {$i-1} ]
          set jn [expr {$j+1} ]
          set js [expr {$j-1} ]
          set ie [expr {($ie >= $nocols) ? 0           : $ie} ]
          set iw [expr {($iw <  0      ) ? ($nocols-1) : $iw} ]
          set jn [expr {($jn >= $norows) ? 0           : $jn} ]
          set js [expr {($js <  0      ) ? ($norows-1) : $js} ]
          set newState($i,$j) \
             [newCellState $state($i,$j)  $state($iw,$j) \
                           $state($ie,$j) $state($i,$jn) \
                           $state($i,$js) ]
       }
    } 

    displayState $window $cells $new_state $nocols $norows

    #
    # Schedule this routine again - reversed arrays!
    #
    after 100 [list \
       calculateNewState $window $cells $new_state $old_state $nocols $norows ]
 }

 # setUpDisplay --
 #    Initialise the display
 # Arguments:
 #    window     The window used to display the result
 #    cells      Array with cell IDs
 #    nocols     Number of columns
 #    norows     Number of rows
 # Result:
 #    None
 # Side effects:
 #    Set new values in the array cells
 #
 proc setUpDisplay { window cells nocols norows } {
    upvar #0 $cells cellId

    for { set j 0 } { $j < $norows } { incr j } {
       for { set i 0 } { $i < $nocols } { incr i } {
          set iw [expr {10*$i} ]
          set ie [expr {$iw+9} ]
          set js [expr {10*($norows-$j)} ]
          set jn [expr {$js-9} ]
          set cellId($i,$j) \
             [$window create rectangle $iw $jn $ie $js -outline "" -fill white]
       }
    }
 }

 # newCellState --
 #    Determine the new state of a cell
 # Arguments:
 #    state_c    State of the current cell
 #    state_w    State of the cell west of the current cell
 #    state_e    State of the cell east of the current cell
 #    state_n    State of the cell north of the current cell
 #    state_s    State of the cell south of the current cell
 # Result:
 #    New state
 #
 proc newCellState { state_c state_w state_e state_n state_s } {
    set sum [expr {$state_w+$state_e+$state_n+$state_s}]

    switch -- $sum {
    "0" { set result 0 }
    "1" { set result 1 }
    "2" { set result 0 }
    "3" { set result 1 }
    "4" { set result 0 }
    default { set result 0 ;# Should never happen though }
    }

    return $result
 }

 # main --
 #    Steer the application
 # Arguments:
 #    None
 # Result:
 #    None
 # Note:
 #    It is necessary to use global arrays - because of [after]
 #
 proc main {} {
    canvas .cnv
    pack .cnv -fill both

    set norows 30
    set nocols 29

    setUpDisplay .cnv ::cells $nocols $norows

    #
    # Initial condition
    #
    for { set j 0 } { $j < $norows } { incr j } {
       for { set i 0 } { $i < $nocols } { incr i } {
          set ::state($i,$j) 0
       }
    }
    set ::state(5,5) 1

    displayState .cnv ::cells ::state $nocols $norows

    after 100 [list \
       calculateNewState .cnv ::cells ::state newState $nocols $norows ]
 }

 #
 # Start the program
 #
 main

DKF - This is not the classic rules for Conway's Life. That uses the eight nearest neighbours (diagonal too), and states that a cell will remain in its current state when it is next to two living neighbours, become/remain alive when it is next to three living neighbours, and become/remain dead when it is next to any other number of neighbours ("overcrowding" and "loneliness", if you will.)

Please see later in this page for Conway in Tcl...

WireWorld

DKF - There are other interesting categories of cellular automata.
One of my favourites is "wires" where each cell can be in one of four states:

blank
Always remains blank.
wire
Becomes a head if-and-only-if next (using 8 neighbours rule) to one or two heads.
head
Becomes a tail.
tail
Becomes a wire.

This is not quite as dynamic as Life (the rules keep the overall form by-and-large static) but it is computationally complete (note that heads and tails combine to form pulse chains that travel in definite directions):

 "3-cycle Pulse Source"

  H############ ->
  T

 "OR Gate"
 -> #####
         #
        ############ ->
         #
 -> #####

 "INHIBIT Gate"
 -> ########## ####### ->
              #
             ###
              #
 -> ##########
 (The inhibit input)

It's possible to build complex "circuits" using this, though layout is tricky because you have to be very careful about the timing.


Langton's Ant

Langton's Ant is an automaton that wanders around blindly for a while, before getting its act together and heading off determinedly in a particular direction.

To make its life marginally more interesting, this Ant lives on a toroid, so it keeps tripping over its own tracks.

There is some background at [L1 ].

 # lant.tcl     Langton's Ant
 
 set size 400                   ;# pixels per canvas side
 set side 400                   ;# cells per canvas side
 set cell [expr $size/$side]    ;# pixels per cell
 set bgcol yellow
 set fgcol red
 set adir(0) {1 0};set adir(1) {0 1};set adir(2) {-1 0};set adir(3) {0 -1}
 
 catch {destroy .c}
 canvas .c -width [expr $size+1] -height [expr $size+1] -bg $bgcol
 bind .c <Button> {set run 0}
 pack .c
 
 set x [expr int(rand()*$side)];set y [expr int(rand()*$side)];set dir 0;set run 1
 while {$run} {
        set col [.c itemcget $x,$y -fill]       ;# read cell at ant position
        if {![string length $col]} {            ;# create new fg cells on demand
                .c create rectangle \
                        [set ax [expr $x*$cell+2]] [set ay [expr $y*$cell+2]] \
                        [expr $ax+$cell] [expr $ay+$cell] \
                        -outline $fgcol -fill $fgcol -tag $x,$y
                set dir [expr ($dir+1)%4]       ;# turn right
        } elseif {[string match $col $bgcol]} { ;# invert bg cell
                .c itemconfigure $x,$y -outline $fgcol -fill $fgcol
                set dir [expr ($dir+1)%4]       ;# turn right
        } else {                                ;# invert fg cell
                .c itemconfigure $x,$y -outline $bgcol -fill $bgcol
                set dir [expr ($dir+3)%4]       ;# turn left
        }
        set x [expr ($x+[lindex $adir($dir) 0])%$side]
        set y [expr ($y+[lindex $adir($dir) 1])%$side]
        update
 }

Bob Clark


Langton's Other Ants

While reading more about Langton's Ant above, I learned that there are infinitely more and more interesting Langton's Ants.

Langton's First Ant above is named "LR", because it turns Left when it encounters the background colour (turning it foreground), and turns Right when it encounters the foreground colour (turning it background). Langton's Second Ant is "RL", a very close relative that does the same thing in the opposite direction.

There are some redundant Ants, "L" and "R" - these just spin round turning the background to background.

But the other Ants from "LLL" to infinity all do something more or less interesting - some wander then head off like the First Ant, some make random amoebic blobs, some make complex space-filling patterns, others make intricate symmetrical traceries that shimmer with colours - there are definite families of Ants.

I particularly like the Ant called "LLLLLLLLLLLLRRRRRRRRRRRR" - it looks like a brain having thoughts. So does "LLLLRRRR" in fact, but less colourfully.

 #      lants2.tcl      Langton's Other Ants 2
 
 proc runworld {cell cycle directions colours} {                ;# track a lant and update the display
 global Config
        .lants.world delete all
        set x [expr {$Config(side)/2}]                  ;# starting position
        set y [expr {$Config(side)/2}]
        array set xdir {0 1 1 0 2 -1 3 0}                       ;# dx per direction
        array set ydir {0 0 1 1 2 0 3 -1}                       ;# dy per direction
        set dir 0                                               ;# 0=0 1=90 -1=3=270 -2=2=180 degrees
        set noofcols [llength $directions]                      ;# number of colours from palette
        while {$Config(.lants.startstop)} {                     ;# until stop button
                set inserts [list]                              ;# list of new cells
                array unset updates                             ;# array of distinct updated cells
                for {set t 0} {$t<$cycle} {incr t} {            ;# do a lot of lant cycles
                        if {[catch {set col $cells($x,$y)}]} {  ;# new cell required
                                set col 0                       ;# 0=background
                                lappend inserts $x $y           ;# list of new cells
                        }
                        set dir [expr {($dir+[lindex $directions $col]+4)%4}]
                        set col [expr {($col+1)%$noofcols}]     ;# change direction, update colour
                        set cells($x,$y) $col                   ;# array of current cell colour
                        set updates($x,$y) ""                   ;# array of distinct updated cells
                        set x [expr {$x+$xdir($dir)}]   ;# new x
                        set y [expr {$y+$ydir($dir)}]   ;# new y
                }
                foreach {x1 y1} $inserts {                      ;# create rectangles for inserts
                        .lants.world create rectangle \
                                        [set ax [expr {$x1*$cell+2}]] [set ay [expr {$y1*$cell+2}]] \
                                        [expr {$ax+$cell}] [expr {$ay+$cell}] -tag $x1,$y1
                }
                foreach xy [array names updates] {              ;# paint rectangles for inserts and updates
                        set col [lindex $colours $cells($xy)]
                        if {![string length $col]} {set col black}
                        .lants.world itemconfigure $xy -outline $col -fill $col
                }
                update
        }
 }
 
 proc checkname {} {    ;# tidy up the lant name and convert to Config(directions)
 global Config
        set Config(.lants.name) [string map {" " ""} [string toupper $Config(.lants.name)]]
        set Config(directions) [string map {L -1 R 1 F 0 B -2} [split $Config(.lants.name) ""]]
        if {[set l [llength $Config(directions)]]} {
                for {set x 0;set i 0} {$i<$l} {incr i} {
                        if {[catch {incr x [lindex $Config(directions) $i]}]} {
                                set Config(.lants.name) [string range $Config(.lants.name) 0 [expr {$i-1}]]?[string range $Config(.lants.name) [expr {$i+1}] end]
                                set Config(directions) [lreplace $Config(directions) $i $i 0]
                        }
                }
         } else {
                set Config(directions) [list 0]
         }
 }
 
 proc startstop {} {    ;# start or stop the lant
 global Config
        if {$Config(.lants.startstop)} {
                .lants.name configure -state normal
                .lants.startstop configure -text Start
                set Config(.lants.startstop) 0
        } else {
                checkname
                .lants.name configure -state disabled
                .lants.startstop configure -text Stop
                set Config(.lants.startstop) 1
                after 0 [list runworld $Config(cell) $Config(.lants.cycle) $Config(directions) $Config(colours)]
        }
 }
 
 array unset Config
 array set Config {
        size                    400     ;#      {pixels per canvas side}
        side                    200     ;#      {cells per canvas side}
        directions              {-1 1}  ;#      {initial =LR}
        colours                 {ivory red2 darkorange2 yellow2 chartreuse2 green2 springgreen2 
                                        turquoise2 dodgerblue2 blue2 blueviolet magenta2 deeppink2 
                                        red3 darkorange3 yellow3 chartreuse3 green3 springgreen3 
                                        turquoise3 dodgerblue3 blue3 darkviolet magenta3 deeppink3 
                                        red4 darkorange4 gold4 chartreuse4 green4 springgreen4 
                                        turquoise4 dodgerblue4 navy purple4 magenta4 deeppink4}         olours)]
                                        ;#      {spectral}
        .lants.name             LR      ;#      {initial =LR}
        .lants.cycle            1000    ;#      {cell cycles per canvas refresh}
        .lants.startstop        0       ;#      {0 when Stopped, 1 when Started}
 }
 set Config(cell)               [expr {$Config(size)/$Config(side)}]    ;# pixels per cell

 wm title . "Langton's Other Ants"
 catch {destroy .lants}
 frame  .lants                                  ize)/$Config(side)}]    ;# pixels per cell
 entry  .lants.name             -textvariable Config(.lants.name)       -width 40
 button .lants.startstop        -text Start     -command startstop
 canvas .lants.world      -width [expr {$Config(size)+1}] -height [expr {$Config(size)+1}] -bg [lindex $Config(colours) 0]
 pack .lants .lants.name .lants.startstop .lants.world

This is a slightly more readable update on the original version, and accepts the letters "F" for forward and "B" for back (directions +0 and -2) - which introduce whole new classes of ants to be exercised.

Bob Clark


Conway in Colour

One more cellular automaton - Conway's Game Of Life from the 1970's - the most-written program after Hello World apparently. There's a lot of background and a true explorer applet at [L2 ]. This is more of a cut-down version, although it does use colour to differentiate the states Birth (yellow), Living (green), Died Cold (blue) and Died Hot (dark red). Press the Start button to kick off a random population and watch it wind down, repeat to taste.

You can also paste an interesting initial pattern into the text box - there's a couple of examples after the program.

 #      conway.tcl      Conway's Life
 
 proc runworld {side cell freq colours toroid delay minb maxb minl maxl updates} {      ;# run the world
 global Config
        foreach xy $updates {set Updates($xy) 1}                                                ;# 1=newborn
        while {$Config(.main.startstop)} {                                                      ;# until Stop button
                array unset newNs                                                               ;# array of new Neighbour xys
                foreach {xy state} [array get Updates] {                                        ;# for each state change at xy
                        if {$state} {                                                           ;# if not 0=empty
                                foreach {x y} [split $xy ,] break
                                set newc [lindex $colours $state]                               ;# new colour
                                if {[catch {set World($xy)}]} {                         ;# if new cell
                                        .main.world create rectangle \
                                                [set ax [expr {$x*$cell+2}]] [set ay [expr {$y*$cell+2}]] \
                                                [expr $ax+$cell] [expr $ay+$cell] \
                                                -outline $newc -fill $newc -tag $xy
                                } else {                                                        ;# existing cell
                                        .main.world itemconfigure $xy -outline $newc -fill $newc
                                }
                                set World($xy) $state                                           ;# preserve state in World array
                                if {[set incr [lindex {0 1 0 -1 -1} $state]]} {         ;# if birth or death event, notify Neighbours (including self)
                                        foreach {dx dy dv} {-1 1 1  0 1 1  1 1 1  -1 0 1  0 0 0  1 0 1  -1 -1 1  0 -1 1  1 -1 1} {
                                                set nx [expr {$x+$dx}];set ny [expr {$y+$dy}];set ni [expr {$incr*$dv}]
                                                if {$toroid} {set nx [expr {($nx+$side)%$side}];set ny [expr {($ny+$side)%$side}]}
                                                if {[catch {incr Neighbours($nx,$ny) $ni}]} {set Neighbours($nx,$ny) $ni}
                                                set newNs($nx,$ny) ""
                                        }
                                }
                         } else {.main.world delete $xy;unset World($xy)}                       ;# empty cell, tidy canvas and World array
                }
                array unset Updates;update;after $delay
                foreach xy [array names newNs] {                                                ;# for each potential state change at xy
                        if {![set neighbours $Neighbours($xy)]} {unset Neighbours($xy)} ;# tidy Neighbours array
                        if {[catch {set state $World($xy)}]} {set state 0}
                        if {$state==0} {                                                        ;# 0=empty - may experience birth
                                if {($neighbours>=$minb)&&($neighbours<=$maxb)} {set Updates($xy) 1}
                        } elseif {$state==1} {                                          ;# 1=newborn - may experience death or continued life
                                if {$neighbours<$minl} {set Updates($xy) 3} elseif {$neighbours>$maxl} {set Updates($xy) 4} else {set Updates($xy) 2} 
                        } elseif {$state==2} {                                          ;# 2=living - may experience death
                                if {$neighbours<$minl} {set Updates($xy) 3} elseif {$neighbours>$maxl} {set Updates($xy) 4} 
                        } else {                                                                ;# 3/4=dead - may experience birth or be emptied
                                if {($neighbours>=$minb)&&($neighbours<=$maxb)} {set Updates($xy) 1} else {set Updates($xy) 0}
                        }
                } 
        }
 }
 
 proc populate {side freq toroid initial} {                                                     ;# return list of populated cell xys from text map, or at random
        if {[string length [string map [list " " "" \t "" \n ""] $initial]]} {
                set y 0;foreach line [split [string map [list \\n \n \\t \t] $initial] \n] {
                        set x 0;foreach char [split $line ""] {
                                if {$char=="\t"} {set x [expr {($x%8)+8}]} elseif {$char==" "} {incr x} else {set births($x,$y) "";incr x}
                                if {$toroid} {set x [expr {$x%$side}]}
                        }
                        if {$toroid} {set y [expr {($y+1)%$side}]} else {incr y}
                }
        } else {
                for {set i 0;set l [expr {int($side*$side*$freq)}]} {$i<$l} {incr i} {set births([expr {int(rand()*$side)}],[expr {int(rand()*$side)}]) ""}
        }
        return [array names births]
 }
 
 proc startstop {} {    ;# start or stop
 global Config
        if {$Config(.main.startstop)} {
                .main.startstop configure -text Start
                set Config(.main.startstop) 0
        } else {
                .main.startstop configure -text Stop
                set Config(.main.startstop) 1
                .main.world delete all
                after 0 [list runworld $Config(side) $Config(cell) $Config(freq) $Config(colours) $Config(.main.toroid) $Config(.main.delay) \
                                $Config(.main.minbirth) $Config(.main.maxbirth) $Config(.main.minlife) $Config(.main.maxlife) \
                                [populate $Config(side) $Config(freq) $Config(.main.toroid) [.main.initial get 0.0 end]]]
        }
 }
 
 array unset Config
 array set Config {
        size                    320                                     ;#      {pixels per canvas side}
        side                    80                                      ;#      {cells per canvas side}
        freq                    0.1                                     ;#      {fraction of random births}
        colours                 {black white white black black} ;#      {traditional}
        colours                 {white black black white white} ;#      {modern}
        colours                 {black yellow green blue darkred}       ;#      {technicolor}
        .main.delay             0                                       ;#      {mS delay per cycle}
        .main.toroid            1                                       ;#      {1 if toroidal world}
        .main.startstop 0                                       ;#      {0 when Stopped, 1 when Started}
        .main.minbirth          3                                       ;#      {operating params...}
        .main.maxbirth          3                                       ;#      {}
        .main.minlife           2                                       ;#      {}
        .main.maxlife           3                                       ;#      {}
 }
 set Config(cell)               [expr {$Config(size)/$Config(side)}]    ;# pixels per cell
 
 wm title . "Conway's Life"
 catch {destroy .main}
 frame  .main
 button .main.startstop -text Start     -command startstop
 canvas .main.world             -width [expr {$Config(size)+1}] -height [expr {$Config(size)+1}] -bg [lindex $Config(colours) 0]
 text .main.initial             -font -*-courier-medium-r-normal--*-80-* -width 60 -height 16 -wrap none
 pack .main .main.startstop .main.world .main.initial

Four Glider Guns - paste this into the text box and press Start:

 \n\n\n\n\n\n\n\n\n\n\n\n\n\n
                        ##                       ##                        
                        # #                     # #                        
            #            ###                   ###            #            
         ####   ##        ###      ## ##      ###        ##   ####         
        ####   ##        ###       ## ##       ###        ##   ####        
 ##     #  #   ## # ##  # #                     # #  ## # ##   #  #     ## 
 ##     ####    # # ##  ##                       ##  ## # #    ####     ## 
         ####   # ##                                   ## #   ####         
            #                                                 #            
 \n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
            #                                                 #            
         ####   # ##                                   ## #   ####         
 ##     ####    # # ##  ##                       ##  ## # #    ####     ## 
 ##     #  #   ## # ##  # #                     # #  ## # ##   #  #     ## 
        ####   ##        ###       ## ##       ###        ##   ####        
         ####   ##        ###      ## ##      ###        ##   ####         
            #            ###                   ###            #            
                        # #                     # #                        
                        ##                       ##                        

Wild Animals - paste this into the text box and press Start:

        # #
         ##
         #
 \n\n\n\n\n\n\n\n
         #
         #                      ##########                ###
         #
 \n\n\n\n\n
  #  #         ####
      #       #   #
  #   #           #
   ####       #  #
 \n\n\n\n\n\n
   #          #####
 #   #       #    #
      #           #
 #    #      #   # 
  #####        #
 \n\n\n\n\n\n
   ##        ######
 #    #     #     #
       #          #
 #     #    #    #
  ######      ##
 \n\n\n\n\n\n\n\n\n
                                         #
                                        ###                 #
        ###                             # #                 #
                                        ###                 #
                                         #
 \n\n\n\n\n\n\n\n\n\n\n
  #
  ##
 # #

Bob Clark


...

TV Scientific correctness dictates that the introduction be amended by making clear the idea is at least decades old, and never caught on very much as relevant science because there are more powerfull theoretical automaton constructions which existed long ago, and because it is not particularly useful.

It is fun, of course, that special case of 2 dimensional set transformation rules. Computers, for instance as von Neuman type of game, and turing machines as automatons are an example of longer existing more generally applicable automaton models, which of course can be programmed with the kind of image map tranformation rules.

Bob Clark - Theo, if you're suggesting cellular automata are uninteresting because all the work was done 30 years ago, then I think you're wrong. CAs gained their place in history as the proving ground for ideas about "emergent behaviour" (simple rules, complex outcomes) that have since had applications all over.

TV Not at all, it was just factually uncorrect to suggest or state they were invented recently, or that they are some mainstream fashion in serious main stream mathematics of the kind lets say quantum physics is in already a hundred years. When you know about that sort of math, you wouldn't suggest such things, not taking away that it can be fun, it's just not very important for anything, including simple rules, complex outcomes ideas. In that area probably one may want to refer to mandelbrot figures as good mathematidal example, or the computation of pi on a turing machine or something, the cellular automaton idea was more for visual feedback I'm sure, and in computer math as in computer graphics software/architecture, and maybe in the fields of neural net examples (emphasizing the term examples).

Probably it has very relevant proof or lets say 'make credible' applications, and maybe has more interesting sides to it than I am aware of, but not much in mainstream fundamental mathematics.

AM (3 november 2003) Cellular automata were also studied in the field of hydrodynamics (or fluid mechanics in general) to see whether they could serve as models for the patterns in turbulent flows that can be observed. The big problem was: how to make the conservation laws work (mass, impuls). And I think that certain chemical reactions (particularly reversible ones) are studied with CAs as well - but on this subject I am much less versed.

TV And were they useable?

AM Probably not. I have not seen much of them since then in that field :)

Bob Clark - One last attempt to rehabilitate CA :) - I think the ideas about Emergent Behaviour that CA helped to illustrate are still very much informing current technology. For examples, Google for:

 "emergent behaviour" network

EB does have applications, and I'm fond of these 2D automata because they visualise EB so brilliantly, they can turn sceptics into believers.

Larry Smith At this point, having seen this mentioned twice, that I must point out that cellular automata can have any number of dimensions, and that quite a few with three or four have been studied extensively.

At this point in our hardware evolution, cellular automata are interesting for demonstrating emergent behavior in complex systems using simple rules, but are not hugely useful as a computing paradigm. This is basically because we are still using the Von Neumann architecture. As systems grow more and more massively parallel, cellular automata and their derivatives may find new traction. In point of fact, it is now over 20 years since "Content Addressable Parallel Processors" was published which talked about an engine with no central CPU - just intelligent memory responding in arrays to instructions fed into the memory control. I am not aware that any commercial systems were ever built on it, but if there were (or if this idea should be retrieved from the dustbin of history to deal with some new issue) something like cellular automata may very well be the programming paradigm of such a system.

JK Cellular Automata turn up in the field of Computational Fluid Dynamics with the name of 'Lattice Gas' models. Essentially particles moving about on a lattice and colliding with each other. As long as the rules are implemented correctly they can be shown to behave as solutions of the Navier Stokes equations for fluid flow. If interested, I would also suggest looking up 'Lattice Boltzmann' methods. These are similar but instead of particles on lattices you deal with distributions of particles on the lattice.

TV Ah, sounds like a computer iterative solution aimed scheme, Bolzman equations are not like cellular automatons, unless you maybe call all partitioned problems such? I guess you take a logical map transformation which happens to deal with an iterative matrix solution in an attractive way. Or an image processing related technique applied to solver scheduling.

EKB -- JK explained the connection between lattice gases and cellular automomata: some CAs obey the Navier-Stokes equations (the equations for fluid flow), if you look at a large enough spatial scale (much larger than the lattice spacing). This offers a computationally efficient technique for modeling fluid flow, and is a contemporary application of CAs. A text describing the method was published in 2004, "Lattice-Gas Cellular Automata: Simple Models of Complex Hydrodynamics" [L3 ], so it's very au courant. Also, as Bob Clark pointed out, cellular automata were, indeed, important in giving rise to today's agent-based models, which have sparked interest because they are said to feature emergent behavior. In any case, the disclaimer at the start that, 'A few years ago cellular automata were "in vogue"' seems to convey the idea that CAs are not as "hot" as they once were.

AM What I meant with "in vogue" was that such constructs were discussed in popular magazines like Scientific American. They seem to have disappeared from such publications ... but I am glad there is a more serious interest in them (the site http://mathworld.wolfram.com has quite a lot of information on their behaviour and general characteristics.)