[FOM] Cellular automata, Wolfram etc.

Martin Davis martin at eipye.com
Fri Sep 13 10:01:59 EDT 2002

Following is adapted from a proposed posting by V.Z.Nuri
Wrt the recent Wolfram/CA thread on these lists..

There is a very sophisticated MIT Phd thesis on CAs from the early 70s
by Banks that covers the topic of minimizing the size of the
CA while maintaining computational universality. The title: is "Information 
processing and transmission in cellular automata." Although it seems to be
mainly 2D oriented, there are some results relating to 1D CAs.
It may be related to the Cook-Wolfram proof of universality for CA110, and 
must be
one of the earliest papers on the subject of computational universality in CAs.

The site below seems to be a general way to get to many MIT PhD theses
online (via page scans). If I recall correctly, Banks edited Von Neumann's 
very complex
notes on CAs and published them after the latter's death.

For Wolfram's tour see:


                           Martin Davis
                    Visiting Scholar UC Berkeley
                      Professor Emeritus, NYU
                          martin at eipye.com
                          (Add 1 and get 0)

More information about the FOM mailing list