there seemed to be an interest in the Game of Life section of my WL Programming Fundamentals tutoria (based on the number of people who viewed my discussion on it - or maybe people were interested in the tutorial itself no way to know) and so i've modified the final section of my tutorial on the Wolfram Progrmming Language Fundamentals (http://library.wolfram.com/infocenter/MathSource/5216/) to incude 2 new GoL programs (so there are now a total of 4 programs, each different in its underlying algorithm) and an improved (i hope) dissection of the aalgorithms used in the programs and finally brief notes (and relevant references) on its implifications for scientific modeling. i expect to post the new (and final) version of tutorial with the new GoL final section at the Wolfram Library Archives shortly but i thought i'd put up just the GoL section now.
since i don't know how to include an attachment to a discussion or if its even possible, i'm doing a 'copy and paste' of the section here:
note: i personally think that the GoL is the most significant of all of the CA's becuase it has (i think) all of the properteis of 1D CA's (such as being Turing Complete) and becuase i believe (perhaps because most of my research in the field of theoretical polymer physics dealt with random walks whose properties are dimensionally dependent) that dimensionality is a very important aspect of reality (we see this is the ongoing discussion of 9, 10, and 26 dimensions in string theory while we know that we actually experience 3 dimensions of space and one dimension of time (at least until the drugs kick in LOL) which modern physics seems to ignore - i think this is a major failing of the physics community which seems to have abandoned its purpose which (i think) is to describe the world we lve in (though multiverse supporters may disagree) and that it is not suffcient to study one-dimensional CAs as SW does (though his studies do reveal fundamental ideas and its easy to generate all 1D CAs while it's not possible to examine the entire 'universe' of 2D CAs since there are 1.34078*10^154 of them )
anyway, here's the section. i hope it comes across okay. if not, see the tutorial in the Wolfram Library archives in a few days when it should be there (you'll know if its there if the final section has four GoL programs, instad of two).
Examples of WL Programs
The Game of Life (GoL) is undoubtably, the most famous cellular automaton (CA) and watching the GoL program run offers deep insight into fundamental tenets concerning the modeling of natural phenomena. The GoL was created in 1969 by the mathematician John Conway and was published in Martin Gardner's Scientific American column (see http://www.maa.org/sites/default/files/pdf/pubs/focus/Gardner_GameofLife10-1970.pdf). The GoL can be described as follows:
On an 'n by n' two-dimensional square grid (aka 'checkerboard'), each of the n^2 cells (aka 'sites') can have two possible values, 0 (aka a 'dead' cell) or 1 (aka a 'live' cell). On each time step, the values of all of the cells are updated simultaneously, based on the value of a cell and the sum of the values of the cells adjacent to (i.e. touching) the cell being updated. The neighborhood' of a cell is comprised of the 8 nearest-neighbor (nn) cells, lying north, northeast, east, southeast, south, southwest, west, and northwest of the cell (these nn cells comprise what is known as the Moore neighborhood). The rules governing the updating are as follows
1) if a cell is alive and has exactly two living nn cell, the cell remains alive (if its value is 1, it remains 1).(2) if a cell has exactly three living nn sites, the cell remains alive (if its value is 1, it remains 1) or is 'born'and becomes alive (if its value is 0, it changes to 1).(3) any other cell either remains dead (if its value is 0, it remains 0) or 'dies' and becomes dead (if its value is 1, it changes to 0).
note: T.H. Huxley's statement that "The chess-board is the world; the pieces are the phenomena of the universe; the rules of the game are what we call the laws of Nature" is often used in conjunction with cellular automata; however, this is an incorrect, or at least imprecise, analogy because in a CA, it is the values of the cells themselves that we are conerned with.
Creating Four WL Programs for 'The Game of Life'
The LifeGame program is basically a straightforward implementation of GoL employing the rule-making, array-processing and pattern-matching capabilities of WL.
LifeGame[n_, steps_] := Module[{gameboard, liveNeighbors, update}, gameboard=Table[Random,{n},{n}]; liveNeighbors[mat_] := Apply[Plus, Map[RotateRight[mat, #]&, {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}}]]; update[1, 2] :=1; update[_, 3] :=1; update[_, _] :=0; SetAttributes[update, Listable]; Nest[update[#,liveNeighbors[#]]&,gameboard,steps]]
The bowlOfCherries program is a 'one-liner', employing a nested anonymous (aka pure) function which uses the shorthand notation (...)& and is comprised of three other anonymous functions which are written using Function with one formal parameter (Function[x, ...], Function[y, ...] and Function[z, ...]).The behaviors of the three anonymous functions nested within the outermost anonymous function, do can be readily discerned by referring to the LifeGame program
alues of the sum of each cell's eight nn cells (0 thru 8) are calculated by adding together the results of eight rotations of the gameboard matrix (the values of the sums are the same as the values determined using liveNeighbors in LifeGame). Ordered pairs are created, in each of which the first element is the value of a cell (0 or 1) and the second element is the sum of the values (0 thru 8) of the cell's eight nn cells (the two elements in each ordered pair are the same as the two arguments used in the update rules of LifeGame). Transformation rules are applied to each of the ordered pairs (the rules are analagous to the update rules of LifeGame).
bowlOfCherries[n_, steps_] := Nest[(MapThread[List, Function[x, {x, Function[y, Apply[Plus, Map[Function[z, RotateRight[y, z]], {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}}]]]}][#], 2] /. {{1, 2} -> 1, {_, 3} -> 1, {_, _} -> 0})&, Table[Random,{n},{n}], steps]
The OblaDeOblaDa program creates and then employs a lookup table comprised of 512 update rules, one for each of the 2^9 possible configurations of a cell and its eight nearest-neighbor cells.
OblaDeOblaDa[n_, steps_]:= Module[{gameboard, Moore, update, LiveConfigs, DieConfigs}, gameboard = Table[Random,{n},{n}];LiveConfigs = Join[Map[Join[{0}, #]&, Permutations[{1, 1, 1, 0, 0, 0, 0, 0}]], Map[Join[{1}, #]&, Permutations[{1, 1, 1, 0, 0, 0, 0, 0}]], Map[Join[{1}, #]&, Permutations[{1, 1, 0, 0, 0, 0, 0, 0}]] ]; DieConfigs = Complement[Flatten[Map[Permutations, Map[Join[Table[1, {#}], Table[0, {(9 - #)}] ]&, Range[0, 9]]], 1], LiveConfigs]; Apply[(update[##] = 1)&, LiveConfigs, 1]; Apply[(update[##] = 0)&, DieConfigs, 1]; Moore[func__, lat_] := MapThread[func, Map[RotateRight[lat, #]&, {{0, 0}, {1, 0}, {0, -1}, {-1, 0}, {0, 1}, {1, -1}, {-1, -1}, {-1, 1}, {1, 1}}], 2]; Nest[Moore[update, #]&, gameboard,steps] ]
note: The LifeGame and bowlOfCherries programs run about equally fast while the OblaDeOblaDa program runs about twice as fast (because of its use of more specific patterns consisting of 0's and 1's rather than of more general patterns consisting of blanks). An impressively faster GoL program in WL can be run by simply using WL's built-in CellularAutomaton function.
WLLife[n_, steps_] :=CellularAutomaton[{224,{2,{{2,2,2},{2,1,2},{2,2,2}}},{1,1}},Table[Random,{n},{n}],{{{steps}}}]
note: Unfortuntely, it is not clear (to me) what each of the arguments being used in the one-liner CellularAutomaton version of GoL represents, what algorithm is being used in CellularAutomaton, (the same situation occurs with other built-In WL functions - e.g. Sort) or even if the algorithm is implemented in WL rather than in another programming language such as C or Assembly Language. It would be interesting to compare the speed of running the GoL in WLLife with the speed of running the GoL in the blazingly fast 'Golly' app (see http://golly.sourceforge.net and also http://www.drdobbs.com/jvm/an-algorithm-for-compressing-space-and-t/184406478).
end notes on GoL:
The use of the built-in Compile function might speed up some of the GoL programs (e.g. bowlOfCherries).
GoL programs written in other programming languages can be found at http://rosettacode.org/wiki/Conway's_Game_of_Life.note: I share the view expressed by the creator of WL (see http://www.stephenwolfram.com/media/stephen-wolfram-strong-opinions/) that computer programs do not need [or should not need] to be Compiled or Parallelized. This is a task best left to the people who design and implement the programming language so that the user of the language, e.g. the scientist, can focus on the task of model development (which is difficult enough to do) without having any unnecessary additional burden when implementing it in a program (this is illustrated for the case of the forest fire CA in http://www.cs.berkeley.edu/~fateman/papers/cashort.pdf).
Finally, as an philosophical aside, the GoL is directly relevant to fundamental issues in the natural sciences, such as emergent phenomena, theoretical modeling of behavior in natural systems, and even, the nature of reality. For those individuals interested in this, see the book: "The Grand Design" by Stephen Hawking and Leonard Mlodinow (the relevant section in this book can also be found at http://aminotes.tumblr.com/post/27848853009/s-hawking-l-mlodinow-on-why-is-there-something), and the two articles by Israeli and Goldenfeld: "Computational Irreducibility and the predictability of complex physical systems" in Physical Review Letters, 92(7), 074105 (2004) (accessible at http://arxiv.org/abs/nlin/03090470) and "Coarse-graining of cellular automata, emergence, and the predictability of complex systems" in Physical Review E, 73, 026203 (2006) (accessible at http://arxiv.org/abs/nlin/0508033).