[FOM] Cellular automata, Wolfram etc.

[Martin Davis]

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:

http://www.wolframscience.com/appearances



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