From: rseymour@reed.edu (Robert Seymour)
Newsgroups: comp.theory.cell-automata
Subject: Re: what is in CA
Date: 11 Oct 92 03:39:59 GMT
Article-I.D.: reed.1992Oct11.033959.873
Reply-To: rseymour@reed.edu
Organization: Reed College, Portland, OR

In article <baljeual.718733208@uther> baljeual@uther.calvin.edu (Alan Baljeu)  
writes:
> I've watched this group for a while now, and I want to know what excactly CA
> entails.  The game of life is discussed regularly.  What other phenomena,
> theoretical constructs belong here?

	CA is Cellular Automata. CAs are an example of a complex system. It is  
implemented by creating a one or two dimensional grid (sometimes more) where  
each site on the grid may have on of two or more states (the original had 29  
states, more recent versions have usually had less). The grid begins in an  
arbitrary original position (i. e. some cells are put into certain states. The  
grid is the changed in discrete time steps by implementing a set of rules.
	CAs were invented by John von Neumann, the pioneer of artificial life  
and Stanislaw Ulam, an amazing mathematician, in or around 1929. von Neumann  
had earlier speculated on self reproducing automata, but ran into problems in  
that the design he presented needed a supply of ready made parts. Ulam  
suggested he take an approach similar to crystaline structure, and so CAs were  
born.
	von Neumann's original model was for an initial state of 200,000 cells  
each set to one of 29 possible states. The creature had 50,000 cells dedicated  
to the body, where work was done, and a 150,000 cell tail that held the  
instructions it was to carry out in order to reproduce and thrive.
	The game of Life was created by Cambridge mathemetician John Horton  
Conway. He speculated that von Neumann's model could be made much simpler and  
still qualify as a universal FSM (Finite State Machine). He developed a system  
on a go board where each cell had two states (denoted by a piece being present  
or missing). He used simple rules that stated:
	1.	If a cell is alive, it will survive the next time step if and
		only if  two or three of its neighbors are also alive.
	2.	If a cell is dead, it will remain dead unless exactly three of
		its neighbors are alive.
	By starting with an initial configuration and applying these rules for  
each time step (or generation), amazing things were born. Certain initial  
states developed configurations that moved (called gliders) or areas that  
produced gliders (glider guns). Sometimes a configuration that moved across the  
board and also left a trail formed (a puffer). Many complex things happened  
once Life was set up on a DEC PDP-6 at MIT.
	CA systems were developed that created certain structure and maintained  
them as if a living system. The gliders propagated and colonized more and more  
of the playing field. This led to much speculation on CAs as a form of life,  
and the possibility of artificial life.
	Later Stephen Wolfram developed one dimensional cellular automata.  
These are displayed as pyramids with each new line being the next generation.  
They mimic many patterns found in nature (particularly certain varieties of  
conch shells). Since then research has gone in all directions (Into the  
applications of CAs to computation; Looking for CA-like structures in nature;  
Studying the role of CAs in physical laws; and too many others to list)
	If you want to learn more about CAs or Life, a great book to read is  
_Artificial Life_ by Steven Levy. It discusses CAs and Life in the early part  
of the book and goes on to describe other artificial life projects. It is an  
excellent journalistic account of the foundations of artificial life, and even  
gets near some of the cutting edge work. If you want a more technical overview,  
read _Artificial Life_ and _Artificial Life II_ both edited by Langton. They  
are the proceedings of the conferences on artificial life held at LANRL (Los  
Alamos National Research Laboratory) and SFI (the Sante Fe Institute for study  
of complex systems) 

P.S.	For those of you in the Portland, OR area, Steven Levy will be speaking  
	at both Reed College and Powell's Technical Bookstore this week. If  
	your somewhere else, look out for him coming to your area.

--
Robert Seymour				rseymour@reed.edu
Departments of Physics and Philosophy
Artificial Life Project			Reed College
Reed Solar Energy Project (SolTrain)	Portland, OR
Newsgroups: comp.theory.cell-automata